МЕТОДИ КЛАСТЕРИЗАЦІЇ МЕРЕЖІ УЧАСНИКІВ РЕАЛІЗАЦІЇ ПРОЄКТУ
DOI:
https://doi.org/10.32347/2412-9933.2020.43.19-25Ключові слова:
кластеризація, проєкт, алгоритм, графи, виокремлення спільнот, мережаАнотація
Одним з найбільш затребуваних завдань аналізу мережі учасників проєкту, що представлені у формі графа, є кластеризація множини вузлів, тобто виокремлення таких підмножин, в кожній з яких вузли пов’язані між собою більшою мірою, ніж з вузлами поза цією підмножиною. Для оцінювання якості алгоритму кластеризації використовується функціонал модулярності, яка являє собою скалярну величину на відрізку [-1, 1] та кількісно описує неформальне визначення структури спільнот. Розглянуто класифікацію методів, що використовують для кластеризації графів: жадібні алгоритми; методи переміщень; методи оптимізації, які застосовуються для визначення оптимальної кластеризації мереж. Проаналізовано два алгоритми для кластеризації графів, в основу яких покладено функціонал модулярності. Перший алгоритм – метод Girvan-Newman, який грунтується на аналізі графа за допомогою методів ієрархічної кластеризації і забезпечує виявлення природного поділу мереж на групи залежно від мір подібності або сили зв’язків між вузлами. Кожен крок алгоритму починається з обчислення значення посередництва для кожного ребра в графі, а потім ребро з найбільшим значенням цієї міри видаляється. Так мережа розбивається на незв’язні компоненти, кожна з яких своєю чергою, піддається тій же процедурі. Розбиття може проводитися допоки в графі не залишиться ребер або поки модулярність результуючого розбиття не досягне максимуму. Другий алгоритм – метод Louvain, який належить до жадібної агломеративної ієрархічної кластеризації і являє собою багатоетапну процедуру, яка передбачає локальну оптимізацію модулярності по відношенню до сусідів кожного вузла. Алгоритм Louvain можна розділити на два етапи. На першому етапі кожному вузлу мережі призначається окрема спільнота, потім для кожного вузла вивчаються варіанти зміни модулярності, при можливому переміщенні вузла між спільнотами. Вузол переміщається в ту спільноту, в якій значення модулярності є максимальним. Другий етап алгоритму полягає в тому, що на підставі поділів, отриманих після виконання локальної оптимізації, відбувається побудова нового графа, вузлами якої є спільноти, знайдені на першому етапі. Наведено приклади застосування обох алгоритмів для кластеризації мережі дружби між людьми в «The karate club study of Zachary».
Посилання
Garey, M.R. & Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness Freeman, San Francisco.
Scott, J. (2000). Social Network Analysis: A Handbook, 2nd ed. Sage Publications, London.
Everitt, B. S., Landau, S. & Leese, M. (2011). Cluster analysis. 5th ed. Arnold.
Newman, M. E., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical review E, 69(2), 026113.
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.
Wu, F. & Huberman, B. A. (2004). Finding communities in linear time: a physics approach. The European Physical Journal B, 38(2), 331-338.
Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271.
Scott, J. (1988). Social network analysis. Sociology, 22(1), 109-127.
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.
Xu, R. & Wunsch, D. (2005). Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16(3):645–678.
Newman, M.E. (2003). Mixing patterns in networks. Physical Review E, 67(2), 026126.
Newman, M.E. (2004). Analysis of weighted networks. Physical review E, 70(5), 056131.
Girvan, M., & Newman, M.E. (2001). Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA, 99 (cond-mat/0112110), 8271-8276.
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
Zachary, W.W. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33, 452–473
Brath, R. & Jonker, D. (2015). Graph analysis and visualization: discovering business opportunity in linked data. John Wiley & Sons.
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
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.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Sergiy Bushuyev, Roman Trach
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
