Аннотації

МЕТОДИ КЛАСТЕРИЗАЦІЇ МЕРЕЖІ УЧАСНИКІВ РЕАЛІЗАЦІЇ ПРОЄКТУ

Автор(и):
Бушуєв С. Д., Трач Р. В.
Автор(и) (англ)
Bushuyev Sergiy, Trach Roman
Дата публікації:

05.09.2020

Анотація (укр):

Одним з найбільш затребуваних завдань аналізу мережі учасників проєкту, що представлені у формі графа, є кластеризація множини вузлів, тобто виокремлення таких підмножин, в кожній з яких вузли пов’язані між собою більшою мірою, ніж з вузлами поза цією підмножиною. Для оцінювання якості алгоритму кластеризації використовується функціонал модулярності, яка являє собою скалярну величину на відрізку [-1, 1] та кількісно описує неформальне визначення структури спільнот. Розглянуто класифікацію методів, що використовують для кластеризації графів: жадібні алгоритми; методи переміщень; методи оптимізації, які застосовуються для визначення оптимальної кластеризації мереж. Проаналізовано два алгоритми для кластеризації графів, в основу яких покладено функціонал модулярності. Перший алгоритм – метод Girvan-Newman, який грунтується на аналізі графа за допомогою методів ієрархічної кластеризації і забезпечує виявлення природного поділу мереж на групи залежно від мір подібності або сили зв’язків між вузлами. Кожен крок алгоритму починається з обчислення значення посередництва для кожного ребра в графі, а потім ребро з найбільшим значенням цієї міри видаляється. Так мережа розбивається на незв’язні компоненти, кожна з яких своєю чергою, піддається тій же процедурі. Розбиття може проводитися допоки в графі не залишиться ребер або поки модулярність результуючого розбиття не досягне максимуму. Другий алгоритм – метод Louvain, який належить до жадібної агломеративної ієрархічної кластеризації і являє собою багатоетапну процедуру, яка передбачає локальну оптимізацію модулярності по відношенню до сусідів кожного вузла. Алгоритм Louvain можна розділити на два етапи. На першому етапі кожному вузлу мережі призначається окрема спільнота, потім для кожного вузла вивчаються варіанти зміни модулярності, при можливому переміщенні вузла між спільнотами. Вузол переміщається в ту спільноту, в якій значення модулярності є максимальним. Другий етап алгоритму полягає в тому, що на підставі поділів, отриманих після виконання локальної оптимізації, відбувається побудова нового графа, вузлами якої є спільноти, знайдені на першому етапі. Наведено приклади застосування обох алгоритмів для кластеризації мережі дружби між людьми в «The karate club study of Zachary».

Анотація (рус):

Анотація (англ):

One of the most popular tasks for analyzing the project participants network presented, in the graph form, is the clustering of set nodes. Clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters). Assess the quality of clustering algorithm, the modularity functional is used, which is a scalar value on the interval [-1, 1] and quantitatively describes an informal definition of the community structure. The classification of methods used for clustering graphs is considered: greedy; displacement methods; optimization methods that are used to find the optimal clustering of networks. Two graph clustering algorithms are analyzed, which are based on the modularity functional. The first algorithm is the Girvan-Newman method, which is based on the analysis of the graph using hierarchical clustering methods and provides detection of separation network of links into groups, depending on measures of similarity or strength of links between nodes. Each step of algorithm begins by calculating value of betweeness for each edge in the graph, and then edge with the highest value of this measure is deleted. The network is divided into disconnected components, each of which, in turn, undergoes the same procedure. A breakdown can be carried out until there are no edges in graph or until resulting modularity the split reaches a maximum. The second algorithm, Louvain method, refers to greedy agglomerative hierarchical clustering. The algorithm is a multi-stage procedure, which provides for local modularity optimization with relationship to the neighbors of each node. The Louvain algorithm can be divided into two stages. At the first stage, a separate community is assigned to each node of network, options for modularity change are studied for each node, with the possible node movement between communities. The node moves to community in which modularity value is maximum. The second algorithm stage is that, based on division obtained after performing local optimization, a new graph is constructed, nodes of which are the communities found in the first stage. Examples of using both algorithms for clustering a network of friendship between people in "The karate club study of Zachary" are given.

Література:

  1. Garey, M.R. & Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness Freeman, San Francisco.
  2. Scott, J. (2000). Social Network Analysis: A Handbook, 2nd ed. Sage Publications, London.
  3. Everitt, B. S., Landau, S. & Leese, M. (2011). Cluster analysis. 5th ed. Arnold.
  4. Newman, M. E., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical review E, 69(2), 026113.
  5. Pons, P., & Latapy, M. (2005). Computing communities in large networks using random walks. In International symposium on computer and information sciences, 284-293, Springer, Berlin, Heidelberg.
  6. Wu, F. & Huberman, B. A. (2004). Finding communities in linear time: a physics approach. The European Physical Journal B, 38(2), 331-338.
  7. Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271.
  8. Scott, J. (1988). Social network analysis. Sociology, 22(1), 109-127.
  9. Thomas, S.L.(2000). Ties that Bind: A Social Network Approach to Understanding Student Integration and Persistence. Journal of Higher Education, 71(5), 591 – 615.
  10. Xu, R. & Wunsch, D. (2005). Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16(3):645–678.
  11. Newman, M.E. (2003). Mixing patterns in networks. Physical Review E, 67(2), 026126.
  12. Newman, M.E. (2004). Analysis of weighted networks. Physical review E, 70(5), 056131.
  13. Girvan, M., & Newman, M.E. (2001). Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA, 99 (cond-mat/0112110), 8271-8276.
  14. Leskovec, J., Lang, K.J. & Mahoney, M. (2010). Empirical comparison of algorithms for network community detection. Proceedings of the 19th international conference on World wide web. ACM, 631-640. https://doi.org/10.1145/1772690.1772755
  15. Zachary, W.W. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33, 452–473
  16. Brath, R. & Jonker, D. (2015). Graph analysis and visualization: discovering business opportunity in linked data. John Wiley & Sons.
  17. Tang, L., & Liu, H. (2010). Community detection and mining in social media. Synthesis lectures on data mining and knowledge discovery, 2(1), 1-137. https://doi.org/10.2200/S00298ED1V01Y201009DMK003
  18. Blondel, V.D., Guillaume, J.L., Lambiotte, R. & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 10, P10008.