Article

Effects of maximum flow algorithm on identifying web community

Authors:

Noriko Imafuji,

Masaru KitsuregawaAuthors Info & Claims

WIDM '02: Proceedings of the 4th international workshop on Web information and data management

Pages 43 - 48

https://doi.org/10.1145/584931.584941

Published: 08 November 2002 Publication History

Get Access

Abstract

In this paper, we describe the effects of using maximum flow algorithm on extracting web community from the web. A web community is a set of web pages having a common topic. Since the web can be recognized as a graph that consists of nodes and edges that represent web pages and hyperlinks respectively, so far various graph theoretical approaches have been proposed to extract web communities from the web graph. The method of finding a web community using maximum flow algorithm was proposed by NEC Research Institute in Princeton two years ago. However the properties of web communities derived by this method have been seldom known. To examine the effects of this method, we selected 30 topics randomly and experimented using Japanese web archives crawled in 2000. Through these experiments, it became clear that the method has both advantages and disadvantages. We will describe some strategies to use this method effectively. Moreover, by using same topics, we examined another method that is based on complete bipartite graphs. We compared the web communities obtained by those methods and analyzed those characteristics.

References

[1]

J. M. Kleinberg, "Authoritative Sources in a Hyperlinked Environment," In Proc. ACM-SIAM Symposium on Discrete Algorithms, 1998.

Digital Library

Google Scholar

[2]

D. Gibson, J. M. Kleinberg and P. Raghavan, "Inferring Web Communities from Link Topology," In Proc. HyperText98, 1998.

Digital Library

Google Scholar

[3]

S. Chakrabarti, B. Dom, P. Raghavan, S. Rajagopalan, D. Gibson and J. Kleinberg, "Automatic resource compilation by analyzing hyperlink structure and associated text," In Proc. 7th WWW Conference, 1998.

Digital Library

Google Scholar

[4]

M. Toyoda and M. Kitsuregawa, "Creating a Web Community Chart for Navigating Related Communities," In Proc. 8th WWW Conference, 1999.

Google Scholar

[5]

S. Brin and L. Page, "The anatomy of a large-scale hypertextual Web search engine," In Proc. 7th WWW Conference, 1998.

Digital Library

Google Scholar

[6]

R. Lempel and S. Moran, "The Stochastic Approach for Link-Structure Analysis (SALSA) and the TKC Effect," In Proc. 9th WWW Conference, 2000.

Digital Library

Google Scholar

[7]

J. Dean and M. R. Henzinger, "Finding related pages in the World Wide Web," In Proc. 8th WWW Conference, 1999.

Digital Library

Google Scholar

[8]

A. Borodin, G. O. Roberts, J. S. Rosenthal and P. Tsaparas, "Finding Authorities and Hubs From Link Structures on the World Wide Web," In Proc. 10th WWW Conference, 2000.

Digital Library

Google Scholar

[9]

G. W. Flake, S. Lawrence, and C. L. Giles, "Efficient Identification of Web Communities," In Proc. KDD 2000, 2000.

Digital Library

Google Scholar

[10]

G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee. "Self-Organization and Identification of Web Communities," IEEE Computer,35(3);66--71, 2002.

Digital Library

Google Scholar

[11]

R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, "Trawling the web for emerging cyber-communities," In Proc. 8th WWW Conference, 1999.

Digital Library

Google Scholar

[12]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, "Network Flows: Theory, Algorithms, and Applications," Prentice Hall, Englewood Cliffs, NJ, 1993.

Digital Library

Google Scholar

[13]

A. V. Goldberg and R. E. Tarjan, "A new approach to the maximal flow problem," In Proc. 18th Ann. ACM Symposium on Theory of Computing, 1986.

Digital Library

Google Scholar

[14]

L. R. Ford Jr. and D. R. Fulkerson, "Maximal flow through a network," Canadian J.Math.,8:399--404, 1956.

Crossref

Google Scholar

Cited By

View all

Wong PSun CLo EYiu MWu XZhao ZHubert Chan TKao B(2017)Finding k most influential edges on flow graphsInformation Systems10.5555/3050918.305096065:C(93-105)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.5555/3050918.3050960
Wong PSun CLo EYiu MWu XZhao ZHubert Chan TKao B(2017)Finding k most influential edges on flow graphsInformation Systems10.1016/j.is.2016.12.00265(93-105)Online publication date: Apr-2017
https://doi.org/10.1016/j.is.2016.12.002
Basaille-Gahitte IAbrouk LCullot NLeclercq ELadid LMontes ABruck PFerri FChbeir R(2013)Using social networks to enhance customer relationship managementProceedings of the Fifth International Conference on Management of Emergent Digital EcoSystems10.1145/2536146.2536163(169-176)Online publication date: 28-Oct-2013
https://dl.acm.org/doi/10.1145/2536146.2536163
Show More Cited By

Index Terms

Effects of maximum flow algorithm on identifying web community
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Extract and rank web communities
WIMS '13: Proceedings of the 3rd International Conference on Web Intelligence, Mining and Semantics

A web community is a pattern in the WWW which is understood as a set of related web pages. In this paper, we propose an efficient algorithm to find the web communities on a given specific topic. Instead of working on the whole web graph, we work on a web ...
Creating a Web community chart for navigating related communities
HYPERTEXT '01: Proceedings of the 12th ACM conference on Hypertext and Hypermedia

Recent research on link analysis has shown the existence of numerous web communities on the Web. A web community is a collection of web pages created by individuals or any kind of associations that have a common interest on a specific topic. In this ...
Mining the Community Structure of a Web Site
BCI '09: Proceedings of the 2009 Fourth Balkan Conference in Informatics

Most approaches for mining the community structure of a graph are based on the assumption that each member of a community has more links within than outside its community. We argue that this delimitation of a community is not appropriate for graphs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

WIDM '02: Proceedings of the 4th international workshop on Web information and data management

November 2002

116 pages

ISBN:1581135939

DOI:10.1145/584931

Program Chairs:
Roger Chiang
University of Cincinnati, USA
,
Ee-Peng Lim
Chinese University of Hong Kong, Hong Kong, China

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 November 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM02

Sponsor:

CIKM02: Eleventh ACM International Conference on Information and Knowledge Management

November 8, 2002

Virginia, McLean, USA

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
766
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wong PSun CLo EYiu MWu XZhao ZHubert Chan TKao B(2017)Finding k most influential edges on flow graphsInformation Systems10.5555/3050918.305096065:C(93-105)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.5555/3050918.3050960
Wong PSun CLo EYiu MWu XZhao ZHubert Chan TKao B(2017)Finding k most influential edges on flow graphsInformation Systems10.1016/j.is.2016.12.00265(93-105)Online publication date: Apr-2017
https://doi.org/10.1016/j.is.2016.12.002
Basaille-Gahitte IAbrouk LCullot NLeclercq ELadid LMontes ABruck PFerri FChbeir R(2013)Using social networks to enhance customer relationship managementProceedings of the Fifth International Conference on Management of Emergent Digital EcoSystems10.1145/2536146.2536163(169-176)Online publication date: 28-Oct-2013
https://dl.acm.org/doi/10.1145/2536146.2536163
Leprovost DAbrouk LGross-Amblard D(2012)Community DiscoverySocial Network Mining, Analysis, and Research Trends10.4018/978-1-61350-513-7.ch004(56-64)Online publication date: 2012
https://doi.org/10.4018/978-1-61350-513-7.ch004
Nakamura YHoriike TKuboyama TSakamoto H(2012)Extracting research communities from bibliographic dataInternational Journal of Knowledge-based and Intelligent Engineering Systems10.3233/KES-2012-023016:1(25-34)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.3233/KES-2012-0230
Yoon SShin JKim SPark SLee J(2012)Subject-based extraction of a latent blog communityInformation Sciences: an International Journal10.1016/j.ins.2011.08.004184:1(215-229)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.ins.2011.08.004
Nakamura YHoriike TTaira YSakamoto H(2010)An improved algorithm for extracting research communities from bibliographic dataProceedings of the 15th international conference on Database systems for advanced applications10.5555/1880853.1880892(338-345)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.5555/1880853.1880892
Nakamura YHoriike TTaira YSakamoto H(2010)An Improved Algorithm for Extracting Research Communities from Bibliographic DataDatabase Systems for Advanced Applications10.1007/978-3-642-14589-6_34(338-345)Online publication date: 2010
https://doi.org/10.1007/978-3-642-14589-6_34
Horiike TTakahashi YKuboyama TSakamoto H(2009)Extracting Research Communities by Improved Maximum Flow AlgorithmProceedings of the 13th International Conference on Knowledge-Based and Intelligent Information and Engineering Systems: Part II10.1007/978-3-642-04592-9_59(472-479)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1007/978-3-642-04592-9_59
Nayak LDe R(2007)An algorithm for modularization of MAPK and calcium signaling pathwaysJournal of Biomedical Informatics10.1016/j.jbi.2007.05.00740:6(726-749)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1016/j.jbi.2007.05.007
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Extract and rank web communities

Creating a Web community chart for navigating related communities

Mining the Community Structure of a Web Site