Abstract
Surprising insights in community structures of complex networks have raised tremendous interest in develo** various kinds of community detection algorithms. Considering the growing size of existing networks, local community detection methods have gained attention in contrast to global methods that impose a top-down view of global network information. Current local community detection algorithms are mainly aimed to discover local communities around a given node. Besides, their performance is influenced by the quality of the source node. In this paper, we propose a community detection algorithm that outputs all the communities of a network benefiting from a set of local principles and a self-defining source node selection. Each node in our algorithm progressively adjusts its community label based on an even more restrictive level of locality, considering its neighbours local information solely. Our algorithm offers a computational complexity of linear order with respect to the network size. Experiments on both artificial and real networks show that our algorithm gains more over networks with weak community structures compared to networks with strong community structures. Additionally, we provide experiments to demonstrate the ability of the self-defining source node of our algorithm by implementing various source node selection methods from the literature.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bagrow, J.P., Bollt, E.M.: Local method for detecting communities. Phys. Rev. E 72(4), 046108 (2005)
Berahmand, K., Bouyer, A., Vasighi, M.: Community detection in complex networksby detecting and expanding core nodes through extended local similarity ofnodes. IEEE Trans. Comput. Soc. Syst. 5(4), 1021–1033 (2018)
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech.
Brust, M.R., Frey, H., Rothkugel, S.: Adaptive multi-hop clustering in mobile networks. In: Proceedings of the 4th International Conference on Mobile Technology, Applications (2007)
Chen, Y., Zhao, P., Li, P., Zhang, K., Zhang, J.: Finding communities by their centers. Sci. Rep. 6, 24017 (2016)
Clauset, A.: Finding local community structure in networks. Phys. Rev. E72(2), 026132 (2005)
Clauset, A., Newman, M.E., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70(6), 066111 (2004)
Comin, C.H., da Fontoura Costa, L.: Identifying the starting point of a spreading process in complex networks. Phys. Rev. E 84(5), 056105 (2011)
Coscia, M., Rossetti, G., Giannotti, F., Pedreschi, D.: DEMON: a local-first discovery method for overlap** communities. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2012)
Dilmaghani, S., Brust, M.R., Piyatumrong, A., Danoy, G., Bouvry, P.: Link definition ameliorating community detection in collaboration networks. Front. Big Data 2, 22 (2019)
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010)
Girvan, M., Newman, M.E.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821–7826 (2002)
Lancichinetti, A., Fortunato, S., Kertész, J.: Detecting the overlap** and hierarchical community structure in complex networks. J. phys. 11(3), 033015 (2009)
Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)
Li, S., Huang, J., Zhang, Z., Liu, J., Huang, T., Chen, H.: Similarity-based future common neighbors model for link prediction in complex networks. Sci. Rep. 8(1), 1–11 (2018)
Luo, F., Wang, J.Z., Promislow, E.: Exploring local community structures in large networks. In: 2006 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2006) (2006)
Porter, M.A., Onnela, J.P., Mucha, P.J.: Communities in networks. Not. AMS 56(9), 1082–1097 (2009)
Stegehuis, C., Van Der Hofstad, R., Van Leeuwaarden, J.S.: Epidemic spreadingon complex networks with community structures. Sci. Rep. 6(1), 1–7 (2016)
Stein, M., Fischer, M., Schweizer, I., Mühlhäuser, M.: A classification of locality in network research. ACM Comput. Surv. (CSUR) 50(4), 1–37 (2017)
Yang, Z., Algesheimer, R., Tessone, C.J.: A comparative analysis of community detection algorithms on artificial networks. Sci. Rep. 6, 30750 (2016)
Acknowledgment
This work has been partially funded by the joint research programme University of Luxembourg/SnT-ILNAS on Digital Trust for Smart-ICT.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dilmaghani, S., Brust, M.R., Danoy, G., Bouvry, P. (2021). Local Community Detection Algorithm with Self-defining Source Nodes. In: Benito, R.M., Cherifi, C., Cherifi, H., Moro, E., Rocha, L.M., Sales-Pardo, M. (eds) Complex Networks & Their Applications IX. COMPLEX NETWORKS 2020 2020. Studies in Computational Intelligence, vol 943. Springer, Cham. https://doi.org/10.1007/978-3-030-65347-7_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-65347-7_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-65346-0
Online ISBN: 978-3-030-65347-7
eBook Packages: EngineeringEngineering (R0)