How to cite this WIREs title:
WIREs Data Mining Knowl Discov

Impact Factor: 7.250

Leader‐based community detection algorithm for social networks

Focus Article

Mostafa G. M. Mostafa, Nagwa L. Badr, Rasha M. Ismail, Nivin A. Helal

Published Online: Aug 02 2017

DOI: 10.1002/widm.1213

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Community detection has become a crucial task in social network mining. Detecting communities summarizes interactions between members for gaining deep understanding of interesting characteristics shared between members of the same community. In this research, we propose a novel community detection algorithm for the purpose of revealing and analyzing hidden similar behavior of online users. The proposed algorithm is based mainly on similar members’ actions rather than the structure similarity only for the aim of detecting communities that are closely mapped to the underlying behavioral communities in real social networks. First, leaders of the social network are discovered, then, communities are detected based on those leaders. The idea is grounded on the assumption that communities could be formed around people with great influence. Extensive experiments and analysis show the ability of the proposed algorithm to successfully detect real‐world communities with improved accuracy. WIREs Data Mining Knowl Discov 2017, 7:e1213. doi: 10.1002/widm.1213 This article is categorized under: Technologies > Structure Discovery and Clustering

Illustrative example of social network graph.

[ Normal View | Magnified View ]

Comparing separability for proposed leader‐based community detection (LBCD) algorithm and the hierarchical diffusion algorithm (HDA).

[ Normal View | Magnified View ]

Comparing conductance for proposed leader‐based community detection (LBCD) algorithm and the hierarchical diffusion algorithm (HDA).

[ Normal View | Magnified View ]

(a) No. of leaders at T = 10, 20, 30, 60 days and α = 3 Flixster dataset. (b) No. of leaders at T = 10, 20, 30, 60 days and μ = 3 Flixster dataset.

[ Normal View | Magnified View ]

Comparing adjusted rand index (ARI) for the proposed leader‐based community detection (LBCD) and the hierarchical diffusion algorithm (HDA).

[ Normal View | Magnified View ]

Comparing accuracy for the proposed leader‐based community detection (LBCD) and the hierarchical diffusion algorithm (HDA).

[ Normal View | Magnified View ]

(a) No. of leaders at T = 1, 2, 3, 4 weeks and α = 2. (b) No. of leaders at T = 1, 2, 3, 4 weeks and α = 3.

[ Normal View | Magnified View ]

(a) No. of leaders at T = 1, 2, 3, 4 weeks and μ = 2. (b) No. of leaders at T = 1, 2, 3, 4 weeks and μ = 3.

[ Normal View | Magnified View ]

(a) Node degree distribution for the real social network dataset and (b) Flixster dataset.

[ Normal View | Magnified View ]

The proposed community detection algorithm.

[ Normal View | Magnified View ]

References

Leskovec, J, Lang, KJ, Mahoney, M. Empirical comparison of algorithms for network community detection. In: Conference on World Wide Web {WWW}, 631–640, 2010.
Girvan, M, Newman, MEJ. Community structure in social and biological networks. Proc Natl Acad Sci U S A 2002, 99:7821–7826.
Radicchi, F, Castellano, C, Cecconi, F, Loreto, V, Parisi, D. Defining and identifying communities in networks. Proc Natl Acad Sci U S A 2004, 101:2658–2663.
Yakoubi, Z, Kanawati, R. Leader‐driven approach for community detection in complex networks. Vietnam J Comput Sci 2014, 1:241–256.
Aggarwal, CC. Social Network Data Analytics. London: Kluwer Academic Publishers; 2012, 2–14.
Girvan, M, Newman, MEJ. Finding and evaluating community structure in networks. Phys Rev E 2004, 69:026113.
Donetti, L, Muñoz, MA. Detecting network communities: a new systematic and efficient algorithm. J Stat Mech Theory Exp 2004, 10:8.
Khorasgani, RR, Chen, J, Zaïane, OR. Top leaders community detection approach in information networks. In: Proceedings of the 4th Workshop on Social Network Mining and Analysis, July 2010, 1–9.
Fortunato, S. Community detection in graphs. Phys Rep 2010, 486:75–174.
Newman, MEJ. Fast algorithm for detecting community structure in networks. Phys Rev E Stat Nonlinear Soft Matter Phys 2004, 69:1–5.
Clauset, A, Newman, MEJ, Moore, C. Finding community structure in very large networks. Phys Rev E 2004, 70(6):66111.
Guimera, R, Sales‐Pardo, M, Amaral, LAN. Modularity from fluctuations in random graphs and complex networks. Phys Rev E Stat Nonlinear Soft Matter Phys 2004, 70:1–4.
Duch, J, Arenas, A. Community detection in complex networks using extremal optimization. Phys Rev E 2005, 72:027104.
Lancichinetti, A, Fortunato, S. Community detection algorithms: a comparative analysis. Phys Rev E Stat Nonlinear Soft Matter Phys 2009, 80:1–11.
Pan, L, Dai, C, Wang, C, Xie, J, Liu, M. Overlapping community detection via leader‐based local expansion in social networks. Proc Int Conf Tools Artif Intell 2012, 1:397–404.
Shen, K, Song, L, Yang, X, Zhang, W. A hierarchical diffusion algorithm for community detection in social networks. In: Proceedings of the 2010 International Conference on Cyber‐Enabled Distributed Computing and Knowledge Discovery, CyberC 2010, 276–283, 2010.
Zhang, S, Wang, R‐S, Zhang, X‐S. Identification of overlapping community structure in complex networks using fuzzy‐means clustering. Phys A Stat Mech Appl 2007, 374:483–490.
Palla, G, Derenyi, I, Farhas, I, Vicsek, T. Uncovering the overlapping community structure of complex networks in nature and society. Nature 2005, 435:814–818.
Wei, F, Wang, C, Ma, L, Zhou, A. Detecting overlapping community structures in networks with global partition and local, expansion. Asia‐Pacific Web Conference. Berlin Heidelberg: Springer; 2008, 43–55.
Chen, W, Liu, Z, Sun, X, Wang, Y. A game‐theoretic framework to identify overlapping communities in social networks. WIREs Data Mining Knowl Discov 2010, 21:224–240.
Alvari, H, Hashemi, S, Hamzeh, A. Detecting overlapping communities in social networks by game theory and structural equivalence concept. In: Artificial Intelligence and Computational Intelligence, vol. LNAI 7003. Berlin Heidelberg: Springer‐Verlag; 2011, 620–630.
Xing, Y, Meng, F, Zhou, Y, Zhou, R. Overlapping community detection by local community expansion. J Inform Sci Eng 2015, 31:1213–1232.
Bhat, SY, Abulaish, M. OCMiner: a density‐based overlapping community detection method for social networks. Intell Data Anal 2015, 19:1–31.
Bedi, P, Sharma, C. Community detection in social networks. WIREs Data Mining Knowl Discov 2016, 6:115–135. DOI: https://doi.org/10.1002/widm.1178.
Goyal, A, Bonchi, F, Lakshmanan, L. Discovering leaders from community actions. In: CIKM ’08, 499–508, 2008.
Han, J, Kamber, M. Data Mining: Concepts and Techniques, vol. 54. 2nd ed. Amsterdam: Morgan‐Kaufman; 2006.
Steinhaeuser, K, Chawla, NV. Identifying and evaluating community structure in complex networks. Pattern Recogn Lett 2010, 31:413–421.
Santos, JM, Embrechts, M. On the use of the adjusted rand index as a metric for evaluating supervised classification. Artificial neural networks–ICANN 2009 (2009): 175–184.
Kannan, R. On clusterings: good, bad and spectral. J ACM 2004, 51:497–515.
Yang, J, Leskovec, J. Defining and evaluating network communities based on ground‐truth. Knowledge and Information Systems 2012, 42(1):181–213.
Helal, NA, Ismail, RM, Badr, NL, Mostafa, MGM. A novel social network mining approach for customer segmentation and viral marketing. WIREs Data Mining Knowl Discov 2016, 6:177–189.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts