ABSTRACT
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.
- J. Abello, M. Resende, and S. Sudarsky. Massive quasi-clique detection. In 5th Latin American Symposium on Theoretical Informatics, pages 598--612, 2002. Google ScholarDigital Library
- C. Bron and J. Kerbosch. Finding all cliques of an undirected graph. Communications of the ACM, 16:575--577, 1973. Google ScholarDigital Library
- O. V. Burton. Computing in the Social Sciences and Humanities. University of Illinois Press, 2006.Google Scholar
- A. Clauset, M. Newman, and C. Moore. Finding community structure in very large networks. Physical Review E, 70(066111), 2004.Google Scholar
- A. Clauset, M. Newman, and C. Moore. Finding local community structure in networks. Physical Review E, 72(026132), 2004.Google Scholar
- L. Donetti and M. Miguel. Detecting network communities: a new systematic and efficient algorithm. Journal of Statistical Mechanics, pages 100--102, 2004.Google ScholarCross Ref
- N. Du, B. Wu, and B. Wang. A parallel algorithm for enumerating all maximal cliques in complex networks. In The 6th ICDM2006 Mining Complex Data Workshop, pages 320--324. IEEE CS, December 2006. Google ScholarDigital Library
- J. Duch and A. Arenas. Community detection in complex networks using extremal optimization. Physical Review E, 72(027104), August 2005.Google Scholar
- M. Girvan and M. Newman. Community structure in social and biological networks. PNAS, 99(12):7821--7826, June 2002.Google ScholarCross Ref
- M. Girvan and M. Newman. Finding and evaluating community structure in networks. Physical Review E, 69(026113), 2004.Google Scholar
- I. Gunes and H. Bingol. Community detection in complex networks using agents. In AAMAS2007, 2007.Google Scholar
- J. Han and M. Kamber. Data Mining: Concepts and Techniques, 2nd ed. Morgan Kaufmann Publishers, 2006. Google ScholarDigital Library
- R. Milo and S. Itzkovitz. Network motifs: Simple building blocks of complex networks. Science, 298:824--827, 2002.Google ScholarCross Ref
- M. Newman. Detecting community structure in networks. The European Physical Journal B-Condensed Matter, 38:321--330, 2004.Google ScholarCross Ref
- M. Newman. Modularity and community structure in networks. PNAS, 103(23):8577--8582, June 2006.Google ScholarCross Ref
- G. Palla, I. Dernyi, and I. Farkas. Uncovering the overlapping community structure of complex network in nature and society. Nature, 435:814--818, June 2005.Google ScholarCross Ref
- J. Pei, D. Jiang, and A. Zhang. On mining cross-graph quasi-cliques. In The 12th ACM SIGKDD, pages 228--237, 2006. Google ScholarDigital Library
- P. Pons and M. Latapy. Computing communities in large networks using random walks. In ISCIS2005, pages 284--293, 2005. Google ScholarDigital Library
- F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi. Defining and identifying communities in networks. PNAS, 101(9):2658--2663, March 2004.Google ScholarCross Ref
- M. Rosvall and C. T. Bergstrom. An information-theoretic framework for resolving community structure in complex networks. PNAS, 104(18):7327--7331, May 2007.Google ScholarCross Ref
- J. Scott. Social Network Analysis: A Handbook. Sage Publications, London, 2002.Google Scholar
- C. Song, M. Havlin, and H. Makse. A self-similarity of complex networks. Nature, 433(7024):392--395, 2005.Google ScholarCross Ref
- A. Vlczquez, R. Dobrin, S. Sergi, J. Eckmann, Z. Oltvai, and A. Barablcsi. The topological relationship between the large-scale attributes and local interaction patterns of complex networks. PNAS, 101(52):17940--17945, 2004.Google ScholarCross Ref
- S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, Cambridge, 1994.Google ScholarCross Ref
- B. Wu and X. Pei. A parallel algorithm for enumerating all the maximal k-plexes. In PAKDD07 Workshops, May 2007. Google ScholarDigital Library
- Z. Zeng, J. Wang, and G. Karypis. Coherent closed quasi-clique discovery from large dense graph databases. In The 12th ACM SIGKDD, pages 797--802, 2006. Google ScholarDigital Library
- http://www-personal.umich.edu/~mejn/Google Scholar
- http://vlado.fmf.unilj.si/pub/networks/pajek/data/gphs.htmGoogle Scholar
- V. Batagelj and A. Mrvar. Some Analyses of Erdos Collaboration Graph. http://vlado.fmf.unilj.si/pub/networks/doc/erdos/erdos.pdfGoogle Scholar
Index Terms
- Community detection in large-scale social networks
Recommendations
Generating high-quality synthetic graphs for community detection in social networks
SpringSim '20: Proceedings of the 2020 Spring Simulation ConferenceOne of the most significant attributes of networks is their community structure. One can define a quality criterion for a community of a network in such a way that a high-quality community refers to a group of vertices that contains more highly-...
Community-based delurking in social networks
ASONAM '16: Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and MiningThe participation inequality phenomenon in online social networks between the niche of super contributors and the crowd of silent users, a.k.a. lurkers, has been witnessed in many domains. Within this view, understanding the role that lurkers take in ...
Community detection in complex networks
With the rapidly growing evidence that various systems in nature and society can be modeled as complex networks, community detection in networks becomes a hot research topic in physics, sociology, computer society, etc. Although this investigation of ...
Comments