Способы выделения сообществ с определенными типами отношений в графах на основе биллинговой информации

В настоящее время одной из актуальных задач анализа графов является выделение сообществ. Разработано большое число алгоритмов для выделения сообществ в графах. Часто такие сообщества не имеют ничего общего с группами людей (семьей, коллегами, друзьями), а используются для упрощения представления графа. Для большого числа задач полезным является выделение именно группы людей, плотно общающихся друг с другом. Многие алгоритмы выделения сообществ не учитывают того, что один участник может входить в несколько сообществ, а это является необходимым условием при выделении круга общения. Рассмотрены основные подходы к выделению сообществ, среди которых отмечены подходы, основанные на оптимизации функционала, поиске клик, кластеризации и распространении меток. Отдельно рассмотрены подходы, базирующиеся на анализе эго-сетей, т. е. рассматривающие подграф, образованный связями одного участника. Приведены основные алгоритмы, применяемые для выделения в графах сообществ с определенными типами отношений на основе биллинговой информации, и результаты анализа графов, построенных на основе этой информации, полезные для выделения сообществ

Литература

[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] Ключарев П.Г., Басараб М.А. Спектральные методы анализа социальных сетей. Наука и образование: научное издание МГТУ им. Н.Э. Баумана, 2017, № 5, с. 168--177. URL: 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] Басараб М.А., Иванов И.П., Колесников А.В. и др. Обнаружение противоправной деятельности в киберпространстве на основе анализа социальных сетей: алгоритмы, методы и средства (обзор). Вопросы кибербезопасности, 2016, № 4, с. 11--19. 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.