Methods of Detecting Communities with Certain Relationship Typesin Graphs using Billing Information

Currently, one of the urgent tasks of graph analysis is community detection. A large number of algorithms have been developed for detecting communities in graphs. Meanwhile, these communities have nothing to do with groups of people, i.e., family, colleagues, friends, and are used to simplify the graph representation. For a large number of tasks, it is useful to detect a group of people who closely communicate with each other. Many algorithms for detecting communities do not take into account that one participant can belong to several communities, and this is a prerequisite for detecting social circles. The paper overviews the main approaches to community detection, and among these emphasizes the approaches based on functionality optimization, clique problem, cluster analysis and label distribution. The approaches based on the analysis of ego-networks, i.e., considering the subgraph formed by the connections of one participant, are considered separately. The study gives the basic algorithms that are applicable for the selection of communities with certain relationship types based on billing information. Findings of research are useful for community detection depending on the task and available input data

References

[1] Fortunato S. Community detection in graphs. Phys. Rep., 2010, vol. 486, no. 3-5, pp. 75--174. DOI: https://doi.org/10.1016/j.physrep.2009.11.002

[2] Lehmann S. Community detection, current and future research trends. In: Encyclopedia of Social Network Analysis and Mining. New York, Springer, 2014, pp. 214--220.

[3] Brandes U., Erlebach T. Network analysis. Berlin, Springer, 2005.

[4] Lancichinetti A., Fortunato S. Community detection algorithms: a comparative analysis. Phys. Rev. E, 2009, vol. 80, no. 5, art. 056117. DOI: https://doi.org/10.1103/PhysRevE.80.056117

[5] Klyucharev P.G., Basarab M.A. Spectral analysis methods of social networks. Nauka i obrazovanie: nauchnoe izdanie MGTU im. N.E. Baumana [Science and Education: Scientific Publication], 2017, no. 5, pp. 168--177 (in Russ.). Available at: https://www.elibrary.ru/item.asp?id=30585833

[6] Xie J., Kelley S., Szymanski B.K. Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput. Surv., 2013, vol. 45, no. 4, art. 43. DOI: https://doi.org/10.1145/2501654.2501657

[7] Nanavati A.A., Singh R., Chakraborty D. Analyzing the structure and evolution of massive telecom graphs. IEEE Trans. Knowl. Data Eng., 2008, vol. 20, no. 5, pp. 703--718. DOI: https://doi.org/10.1109/TKDE.2007.190733

[8] Zheleva M., Schmitt P., Vigil M., et al. Community detection in cellular network traces. Proc. ICDT 13, 2013, vol. 2, pp. 183--186. DOI: https://doi.org/10.1145/2517899.2517932

[9] Basarab M.A., Ivanov I.P., Kolesnikov A.V., et al. Detection of illegal activities in cyberspace on the basis of the social networks analysis: algorithms, methods, and tools (a survey). Vopr. kiberbezop., 2016, no. 4, pp. 11--19 (in Russ.). DOI: https://doi.org/10.21681/2311-3456-2016-4-11-19

[10] Goldberg M., Kelley S., Magdon-Ismail M., et al. Finding overlapping communities in social networks. IEEE 2nd Int. Conf. Soc. Comput., 2010. DOI: https://doi.org/10.1109/SocialCom.2010.24

[11] Raad E., Chbeir R., Dipanda A. Discovering relationship types between users using profiles and shared photos in a social network. Multimed. Tools Appl., 2013, vol. 64, no. 1, pp. 141--170. DOI: https://doi.org/10.1007/s11042-011-0853-7

[12] Eynard D., Javarone M.A., Matteucci M. Clustering algorithms. In: Encyclopedia of Social Network Analysis and Mining. New York, Springer, 2014, pp. 101--114.

[13] Borgatti S.P., Everett M.G. A graph-theoretic perspective on centrality. Soc. Networks, 2006, vol. 28, no. 4, pp. 466--484. DOI: https://doi.org/10.1016/j.socnet.2005.11.005

[14] Everett M.G. Classical algorithms for social network analysis: future and current trends. In: Encyclopedia of Social Network Analysis and Mining. New York, Springer, 2014, pp. 88--94.

[15] Amelio A., Pizzuti C. Overlapping community discovery methods: a survey. In: Social Networks: Analysis and Case Studies. Vienna, Springer, 2014, pp. 105--125.

[16] Mateos P. Demographic, ethnic and socioeconomic community structure in social networks. In: Encyclopedia of Social Network Analysis and Mining. New York, Springer, 2014, pp. 342--346.

[17] Yang J., Leskovec J. Overlapping community detection at scale: a nonnegative matrix factorization approach. Proc. WSDM 13, 2013, pp. 587--596. DOI: https://doi.org/10.1145/2433396.2433471

[18] Baumes J., Goldberg M.K., Krishnamoorthy M.S., et al. Finding communities by clustering a graph into overlapping sub-graphs. Proc. IADIS Int. Conf. Appl. Comput., 2005, vol. 5, pp. 97--104.

[19] Lancichinetti A., Fortunato S., Kertesz J. Detecting the overlapping and hierarchical community structure of complex networks. New J. Phys., 2009, vol. 11, no. 3, art. 033015. DOI: https://doi.org/10.1088/1367-2630/11/3/033015

[20] Lancichinetti A., Radicchi F., Ramasco J.J., et al. Finding statistically significant communities in networks. PLoS ONE, 2011, vol. 6, no. 4, art. e18961. DOI: https://doi.org/10.1371/journal.pone.0018961

[21] Palla G., Derenyi I., Farkas I., et al. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, vol. 435, no. 7043, pp. 814--818. DOI: https://doi.org/10.1038/nature03607

[22] Derenyi I., Palla G., Vicsek T. Clique percolation in random networks. Phys. Rev. Lett., 2005, vol. 94, no. 16, art. 160202. DOI: https://doi.org/10.1103/PhysRevLett.94.160202

[23] Shen H., Cheng X., Cai K., et al. Detect overlapping and hierarchical community structure in networks. Physica A, 2009, vol. 388, no. 8, pp. 1706--1712. DOI: https://doi.org/10.1016/j.physa.2008.12.021

[24] Lee C., Reid F., McDaid A., et al. Detecting highly overlapping community structure by greedy clique expansion. Proc. 4th Workshop Soc. Netw. Mining Anal. Held in Conjunction with Int. Conf. Knowl. Discov. Data Mining, 2010, pp. 33--42.

[25] Ahn Y.Y., Bagrow J.P., Lehmann S. Link communities reveal multiscale complexity in networks. Nature, 2010, vol. 466, pp. 761--764. DOI: https://doi.org/10.1038/nature09182

[26] Coscia M., Giannotti F., Pedreschi D. Extracting and inferring communities via link analysis. In: Encyclopedia of Social Network Analysis and Mining. New York, Springer, 2014, pp. 517--525.

[27] Dickinson B., Valyou B., Hu W. A genetic algorithm for identifying overlapping communities in social networks using an optimized search space. Soc. Netw., 2013, vol. 2, no. 4. DOI: https://doi.org/10.4236/sn.2013.24019

[28] Ding Z., Zhang X., Sun D., et al. Overlapping community detection based on network decomposition. Sc. Rep., 2016, vol. 6, art. 24115. DOI: https://doi.org/10.1038/srep24115

[29] Gregory S. Finding overlapping communities in networks by label propagation. New J. Phys., 2010, vol. 12, no. 10, art. 103018. DOI: https://doi.org/10.1088/1367-2630/12/10/103018

[30] Yang J., Leskovec J. Community-affiliation graph model for overlapping network community detection. IEEE 12th Int. Conf. Data Mining, 2012, pp. 1170--1175. DOI: https://doi.org/10.1109/ICDM.2012.139

[31] Yang T., Jin R., Chi Y., et al. Combining link and content for community detection. In: Encyclopedia of Social Network Analysis and Mining. New York, Springer, 2014, pp. 190--201.

[32] McAuley J.J., Leskovec J. Learning to discover social circles in ego networks. In: Advances in Neural Information Processing Systems. NeurIPS, 2012, vol. 1, pp. 539--547.