Efficient identification of Web communities

By Gary William Flake, Steve Lawrence, C. Giles. Knowledge Discovery and Data Mining, 2000

405 citations recorded by the source corpus.

We de ne a communit y on the web as a set of sites that have more links (in either direction) to members of the community than to non-members. Members of such a community can be eAEciently iden ti ed in a maximum ow / minim um cut framework, where the source is composed of known members, and the sink consists of well-kno wn non-members. A focused crawler that crawls to a xed depth can approximate community membership by augmenting the graph induced by the cra wl with links to a virtual sink node.The effectiveness of the approximation algorithm is demonstrated with several crawl results that iden tify hubs, authorities, w eb rings, and other link topologies that are useful but not easily categorized. Applications of our approach include focused cra wlers and search engines, automatic population of portal categories, and improved ltering.

Subfields: Information Systems, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/e7b7458b78a373f9f8af4aabf6c2b66ee2f30e59

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Statistical and Nonlinear Physics

Citations in the corpus

Curvature of co-links uncovers hidden thematic layers in the World Wide Web (2001, background): “Based on these ideas the successful search engine Google was designed; it also lead to the notion of “Community” (22, 23).”
The community-search problem and how to plan a successful cocktail party (2010, methodology): “Other approaches to community detection include algorithms based on max-flows [12, 13], finding dense subgraphs [9, 15], as well as graph-partitioning”
Community Discovery in Dynamic Networks (2017, neutral): “• Maximum/Average ODF (Flake et al., 2000) (outdegree fraction), i.”
Community Detection and Mining in Social Media (2010, background): “The first line focuses on scaling up community detection methods to handle networks of colossal sizes (Flake et al., 2000; Gibson et al., 2005; Dourisboure et al., 2007; Andersen and Lang, 2006).”
Social influence analysis in large-scale networks (2009, methodology): “[12] propose a method based on maximum flow/minmum cut to identify Web communities.”
Detecting communities and their evolutions in dynamic social networks—a Bayesian approach (2011, background): “Based on this graph representation, there exists a large body of work on analyzing communities in static social networks, ranging from well-established social network analysis (Wasserman and Faust 1994) to recent successful applications such as Web community discovery (Flake et al. 2000).”
Graph Clustering and Minimum Cut Trees (2004, methodology): “In Section 3, we focus on the previous work of Flake et al. [Flake et al. 00], and then describe our cut-clustering algorithm and analyze it in terms of upper and lower bounds.”
Understanding the requirements for developing open source software systems (2002, neutral): “6 An alternative scheme for automatically discovering the membership of a Web-based community uses graph traversal (crawling linked web pages) and s-t maximum flow network algorithms [13].”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, background): “[67, 68] defined a community as a set of nodes that has more intra-edges than inter-edges.”
Facetnet: a framework for analyzing communities and their evolutions in dynamic networks (2008, methodology): “[6] defined Web communities as “a set of sites that have more links to members of the community than to non-members”, and proposed algorithms to identify Web communities based on a maximum flow/minmum cut framework.”
Community discovery using nonnegative matrix factorization (2011, methodology): “More recently, the graph based partitioning methods (von Luxburg 2007; Weiss 1999) have aroused considerable interests in machine learning and data mining fields, and these methods have also been successfully applied to community discovery (Flake et al. 2000; Ino et al. 2005; Miao et al. 2008; Ruan ”
Neighborhood formation and anomaly detection in bipartite graphs (2005, methodology): “Graph Partitioning: Popular methods for partitioning graphs include the METIS algorithm [11], spectral partitioning techniques [10], flow-based methods [6] information-theoretic methods [5], and methods based on the “betweenness” of edges [7], among others.”
Fast Random Walk with Restart and Its Applications (2006, methodology): “METIS [19], spectral clustering [20], flow simulation [8], co-clustering [6], and the betweenness based method [11].”
Mining the network value of customers (2001, background): “[13] provide a potential way of doing this.”