The increasing importance of Web 2.0 applications during the last years has created significant interest in tools for analyzing and describing collective user activities and emerging phenomena within the Web. Network structures have been widely employed in this context for modeling users, web resources and relations between them. However, the amount of data produced by modern web systems results in networks that are of unprecedented size and complexity, and are thus hard to interpret. To this end, community detection methods attempt to uncover natural groupings of web objects by analyzing the topology of their containing network. There are numerous techniques adopting a global perspective to the community detection problem, i.e. they operate on the complete network structure, thus being computationally expensive and hard to apply in a streaming manner. In order to add a local perspective to the study of the problem, we present Bridge Bounding, a local methodology for community detection, which explores the local network topology around a seed node in order to identify edges that act as boundaries to the local community. The proposed method can be integrated in an efficient global community detection scheme that compares favorably to the state of the art. As a case study, we apply the method to explore the topic structure of the LYCOS iQ collaborative question answering application by detecting communities in the networks created from the collective tagging activity of users.
@cite_14: 
@cite_16: The World Wide Web grows through a decentralized, almost anarchic process, and this has resulted in a large hyperlinked corpus without the kind of logical organization that can be built into more tradit,ionally-created hypermedia. To extract, meaningful structure under such circumstances, we develop a notion of hyperlinked communities on the www t,hrough an analysis of the link topology. By invoking a simple, mathematically clean method for defining and exposing the structure of these communities, we are able to derive a number of themes: The communities can be viewed as containing a core of central, “authoritative” pages linked togh and they exhibit a natural type of hierarchical topic generalization that can be inferred directly from the pat,t,ern of linkage. Our investigation shows that although the process by which users of the Web create pages and links is very difficult to understand at a “local” level, it results in a much greater degree of orderly high-level structure than has typically been assumed.
@cite_25: The Web harbors a large number of communities — groups of content-creators sharing a common interest — each of which manifests itself as a set of interlinked Web pages. Newgroups and commercial Web directories together contain of the order of 20,000 such communities; our particular interest here is on emerging communities — those that have little or no representation in such fora. The subject of this paper is the systematic enumeration of over 100,000 such emerging communities from a Web crawl: we call our process trawling. We motivate a graph-theoretic approach to locating such communities, and describe the algorithms, and the algorithmic engineering necessary to find structures that subscribe to this notion, the challenges in handling such a huge data set, and the results of our experiment. © 1999 Published by Elsevier Science B.V. All rights reserved.
@cite_12: 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.
The problem of community finding in large complex networks has attracted considerable research interest for some time now. Its origins can be traced back to the first studies of the hyperlink structure of the web, e.g. to the observation of @cite_16 that communities emerge spontaneously around authoritative web pages which are identified by means of hub pages. Then, the works by @cite_25 and @cite_12 formally defined and systematically tackled the problem of community detection. In the following, we provide a list of existing methods for community detection classified according to the approach they adopt. A more detailed discussion of existing community detection methods is contained in the survey by @cite_14 .