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_5: Recent years have seen that WWW is becoming a flourishing social media which enables individuals to easily share opinions, experiences and expertise at the push of a single button. With the pervasive usage of instant messaging systems and the fundamental shift in the ease of publishing content, social network researchers and graph theory researchers are now concerned with inferring community structures by analyzing the linkage patterns among individuals and web pages. Although the investigation of community structures has motivated many diverse algorithms, most of them are unsuitable for large-scale social networks because of the computational cost. Moreover, in addition to identify the possible community structures, how to define and explain the discovered communities is also significant in many practical scenarios. In this paper, we present the algorithm ComTector(Community DeTector) which is more efficient for the community detection in large-scale social networks based on the nature of overlapping communities in the real world. This algorithm does not require any priori knowledge about the number or the original division of the communities. Because real networks are often large sparse graphs, its running time is thus O(C × Tri2), where C is the number of the detected communities and Tri is the number of the triangles in the given network for the worst case. Then we propose a general naming method by combining the topological information with the entity attributes to define the discovered communities. With respected to practical applications, ComTector is challenged with several real life networks including the Zachary Karate Club, American College Football, Scientific Collaboration, and Telecommunications Call networks. Experimental results show that this algorithm can extract meaningful communities that are agreed with both of the objective facts and our intuitions.
A combined strategy for community detection is provided by @cite_5 . The authors consider a three-step community detection process: (a) detection of maximal cliques (subgraph enumeration), (b) initial network partition by progressive expansion of the maximal cliques (flooding) and (c) adjustment of the original partition in order to maximize modularity.