Меню
Публикации
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор
НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры
doi: 10.17586/2226-1494-2022-22-5-941-950
УДК 51-78
Подход к обнаружению сообщества в динамических сетях, основанный на принудительной неотрицательной матричной факторизации
Читать статью полностью
Язык статьи - английский
Ссылка для цитирования:
Аннотация
Ссылка для цитирования:
Башир Ш., Чачу М.А. Подход к обнаружению сообщества в динамических сетях, основанный на принудительной неотрицательной матричной факторизации // Научно-технический вестник информационных технологий, механики и оптики. 2022. Т. 22, № 5. С. 941–950 (на англ. яз.). doi: 10.17586/2226-1494-2022-22-5-941-950
Аннотация
Выявление структур сообщества в сетевой динамике важно для анализа сети относительно: скрытой структуры, понимания функций, прогнозирования развития, обнаружения необычных событий. В рассмотренных научных исследованиях рекомендуется использовать различные подходы к динамическому обнаружению сообщества. Однако из-за сложности настройки параметров, высокой временной сложности и снижения точности обнаружения по мере увеличения временного интервала распознавание состава сообщества в динамических сетях усложняется. Рассмотрены основные схемы, принципы, свойства и методы моделей латентных факторов, а также их системные модификации, обобщения и расширения. Основное внимание уделено теоретическим и экспериментальным исследованиям моделей латентных факторов за последние десять лет. Скрытая факторная модель — неотрицательная матричная факторизация, считается одной из наиболее успешных для идентификации сообщества и направлена на раскрытие распределенного представления более низкого измерения с целью определения членства в узле сообщества. Модели основаны на реконструкции сети из представлений узлов при условии, чтобы представление обладало особыми желательными качествами (например, не отрицательностью). Цель работы — получить экспериментальный и теоретический сравнительные анализы подходов со скрытым фактором, используемых для обнаружения сообществ в динамических сетях. Разработана общая и улучшенная неотрицательные матричные модели, основанные на факторизации для получения надежных результатов обнаружения сообщества в динамических сетях. Полученные результаты рассчитаны на основе экспериментов, проведенных на языке программирования Python. Предложенная методология моделей сфокусирована на динамике информации, для количественной оценки распространения информации между задействованными узлами. Отличие предложенной модели от существующих состоит в получении топологической информации сети первого порядка, описываемой ее матрицей смежности, без учета распространения информации между узлами. Предложено создание единой современной структуры, предназначенной для концепции неотрицательной матричной факторизации, которая может быть полезна для будущих исследований.
Ключевые слова: обнаружение сообщества, анализ главных компонент, ортогональность, неотрицательная матричная факторизация, разложение по сингулярным числам, анализ социальных сетей
Список литературы
Список литературы
-
Girvan M., Newman M.E.J. Community structure in social and biological networks // Proceedings of the National Academy of Sciences of the United States of America. 2002. V. 99. N 12. P. 7821–7826. https://doi.org/10.1073/pnas.122653799
-
Wang Y., Zhang Y. Nonnegative Matrix Factorization: A comprehensive review // IEEE Transactions on Knowledge and Data Engineering. 2013. V. 25. N 6. P. 1336–1353. https://doi.org/10.1109/TKDE.2012.51
-
Yang J., Leskovec J. Overlapping community detection at scale: A nonnegative matrix factorization approach // Proc. of the 6th ACM International Conference on Web Search and Data Mining, WSDM. 2013. P. 587–596. https://doi.org/10.1145/2433396.2433471
-
Wang F., Li T., Wang X., Zhu S., Ding C. Community discovery using nonnegative matrix factorization // Data Mining and Knowledge Discovery. 2011. V. 22. N 3. P. 493–521. https://doi.org/10.1007/s10618-010-0181-y
-
Gao F., Yuan L., Wang W. Dynamic community detection using nonnegative matrix factorization // Proc. of the International Conference on Computing Intelligence and Information System (CIIS). 2017. P. 39–45. https://doi.org/10.1109/CIIS.2017.56
-
Ye Z., Zhang H., Feng L., Shan Z. CDCN: A new NMF-based community detection method with community structures and node attributes // Wireless Communications and Mobile Computing. 2021. P. 5517204. https://doi.org/10.1155/2021/5517204
-
Yang K., Guo Q., Liu J.Q. Community detection via measuring the strength between nodes for dynamic networks // Physica A: Statistical Mechanics and its Applications. 2018. V. 509. P. 256–264. https://doi.org/10.1016/j.physa.2018.06.038
-
Lin Y.R., Chi Y., Zhu S., Sundaram H., Tseng B.L. Facetnet: A framework for analyzing communities and their evolutions in dynamic networks // Proc. of the 17th International Conference on World Wide Web. 2008. P. 685–694. https://doi.org/10.1145/1367497.1367590
-
Lu H., Sang X., Zhao Q., Lu J. Community detection algorithm based on nonnegative matrix factorization and pairwise constraints // Physica A: Statistical Mechanics and its Applications. 2020. V. 545. P. 123491. https://doi.org/10.1016/j.physa.2019.123491
-
Lee D., Seung H.S. Learning the parts of objects with non-negative matrix factorization // Nature. 1999. V. 401. N 6755. P. 788–791. https://doi.org/10.1038/44565
-
Cai D., He X., Han J., Huang T.S. Graph regularized nonnegative matrix factorization for data representation // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2011. V. 33. N 8. P. 1548–1560. https://doi.org/10.1109/TPAMI.2010.231
-
Chung F.R.K. Spectral Graph Theory. Published for the Conference Board of the mathematical sciences by the American Mathematical Society, 1997. 108 p.
-
Yu W., Wu H., Jiao P., Wu H., Sun Y., Tang M. Modeling the local and global evolution pattern of community structures for dynamic networks analysis // IEEE Access. 2019. V. 7. P. 71350–71360. https://doi.org/10.1109/ACCESS.2019.2920237
-
Shafia, Chachoo M.A. Social network analysis based criminal community identification model with community structures and node attributes // Proc. of the 4th International Conference on Smart Systems and Inventive Technology (ICSSIT). 2022. P. 334–339. https://doi.org/10.1109/ICSSIT53264.2022.9716286
-
Ma X., Dong D. Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks // IEEE Transactions on Knowledge & Data Engineering. 2017. V. 29. N 5. P. 1045–1058. https://doi.org/10.1109/TKDE.2017.2657752
-
Jiao P., Yu W., Wang W., Li X., Sun Y. Exploring temporal community structure and constant evolutionary pattern hiding in dynamic networks // Neurocomputing. 2018. V. 314. P. 224–233. https://doi.org/10.1016/j.neucom.2018.03.065
-
Liu H.-F., Yuan L.-M.-Z. Community detection in temporal networks using triple nonnegative matrix factorization // DEStech Transactions on Computer Science and Engineering. 2017. https://doi.org/10.12783/dtcse/mmsta2017/19682
-
Wang T., Liu Y., Xi Y.-Y. Identifying community in bipartite networks using graph regularized-based non-negative matrix factorization // Journal of Electronics and Information Technology. 2015. V. 37. N 9. P. 2238–2245. (in Chinese). https://doi.org/10.11999/JEIT141649
-
Newman M.E.J. Modularity and community structure in networks // Proceedingsof the National Academy of Sciences of the United States of America. 2006. V. 103. N 23. P. 8577–8582. https://doi.org/10.1073/pnas.0601602103
-
Blondel V.D., Guillaume J.L., Lambiotte R., Lefebvre E. Fast unfolding of communities in large networks // Journal of Statistical Mechanics: Theory and Experiment. 2008. P. P10008. https://doi.org/10.1088/1742-5468/2008/10/P10008
-
Nguyen N.P., Dinh T.N., Tokala S., Thai M.T. Overlapping communities in dynamic networks: their detection and mobile applications // Proc. of the 17th Annual International Conference on Mobile Computing and Networking, MobiCom'11 and Co-Located Workshops. 2011. P. 85–95. https://doi.org/10.1145/2030613.2030624
-
He D., Jin D., Baquero C., Liu D. Link community detection using generative model and nonnegative matrix factorization // PLoS ONE. 2014. V. 9. N 1. P. e86899. https://doi.org/10.1371/journal.pone.0086899
-
Bashir S., Chachoo M.A. Community detection in online social networks: models and methods, a survey // Gedrag & Organisatie Review. 2020. V. 33. P. 1164–1175. https://doi.org/10.37896/gor33.03/498
-
Wang S., Li G., Hu G., Wei H., Pan Y., Pan Z. Community detection in dynamic networks using constraint non-negative matrix factorization // Intelligent Data Analysis. 2020. V. 24. N 1. P. 119–139. https://doi.org/10.3233/IDA-184432
-
Lu H., Zhao Q., Sang X., Lu J. Community detection in complex networks using nonnegative matrix factorization and density-based clustering algorithm // Neural Processing Letters. 2020. V. 51. N 2. P. 1731–1748. https://doi.org/10.1007/s11063-019-10170-1
-
Zachary W.W. An information flow model for conflict and fission in small groups // Journal of Anthropological Research. 1977. V. 33. N 4. P. 452–473. https://doi.org/10.1086/jar.33.4.3629752
-
Lusseau D., Schneider K., Boisseau O.J., Haase P., Slooten E., Dawson S.M. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations // Behavioral Ecology and Sociobiology. 2003. V. 54. N 4. P. 396–405. https://doi.org/10.1007/s00265-003-0651-y
-
McAuley J., Leskovec J. Learning to discover social circles in ego networks // Advances in Neural Information Processing Systems. 2012. V. 1. P. 539–547.