Tiles: Một Thuật Toán Trực Tuyến Để Khám Phá Cộng Đồng Trong Các Mạng Xã Hội Năng Động

Machine Learning - Tập 106 - Trang 1213-1241 - 2016
Giulio Rossetti1,2, Luca Pappalardo1,2, Dino Pedreschi1, Fosca Giannotti2
1KDD Lab, University of Pisa, Pisa, Italy
2KDD Lab, ISTI-CNR, Pisa, Italy

Tóm tắt

Khám phá cộng đồng đã nổi lên trong suốt thập kỷ qua như một trong những vấn đề thách thức nhất trong phân tích mạng xã hội. Nhiều thuật toán đã được đề xuất để tìm kiếm các cộng đồng trên các mạng tĩnh, tức là các mạng không thay đổi theo thời gian. Tuy nhiên, mạng xã hội là những thực thể năng động (ví dụ: đồ thị cuộc gọi, mạng xã hội trực tuyến): trong những kịch bản như vậy, việc khám phá cộng đồng tĩnh không thể xác định một phân vùng của đồ thị một cách nhất quán với thông tin tạm thời được biểu thị bởi dữ liệu. Trong công trình này, chúng tôi đề xuất Tiles, một thuật toán trích xuất các cộng đồng chồng chéo và theo dõi sự tiến hóa của chúng theo thời gian thông qua một quy trình lặp trực tuyến. Thuật toán của chúng tôi hoạt động theo chiến lược hiệu ứng domino, tái tính toán các thành viên cộng đồng của nút một cách động mỗi khi có một tương tác mới diễn ra. Chúng tôi so sánh Tiles với các thuật toán phát hiện cộng đồng tiên tiến trên cả mạng tổng hợp và mạng thực tế có cấu trúc cộng đồng đã được chú thích: các thí nghiệm của chúng tôi cho thấy phương pháp được đề xuất có khả năng đảm bảo thời gian thực hiện thấp hơn và sự tương ứng tốt hơn với các cộng đồng được xác định đúng hơn so với các đối thủ cạnh tranh. Hơn nữa, chúng tôi minh họa các đặc điểm cụ thể của phương pháp được đề xuất bằng cách thảo luận về các tính chất của các cộng đồng mà nó có thể xác định.

Từ khóa

#Khám phá cộng đồng #Mạng xã hội năng động #Thuật toán trực tuyến #Cộng đồng chồng chéo #Phân tích mạng xã hội

Tài liệu tham khảo

Asur, S., Parthasarathy, S., & Ucar, D. (2009). An event-based framework for characterizing the evolutionary behavior of interaction graphs. ACM Transactions on Knowledge Discovery from Data (TKDD), 3(4), 16. Bagrow, J. P., & Lin, Y.-R. (2012). Mesoscopic structure and social aspects of human mobility. PLoS ONE, 7(5), e37676. Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286.5439, 509–512. Bhat, S., & Abulaish, M. (Aug 2013). Overlapping social network communities and viral marketing. In International Symposium on Computational and Business Intelligence, pp. ( 243–246). Boden, B., Günnemann, S., Hoffmann, H., & Seidl, T. (2012). Mining coherent subgraphs in multi-layer graphs with edge labels. In ACM SIGKDD. Boldrini, C., Conti, M., & Passarella, A. (2011). From pareto inter-contact times to residuals. Communications Letters IEEE, 15(11), 1256–1258. Buehrer, G., & Chellapilla, K. (2008). A scalable pattern mining approach to web graph compression with communities. Proceedings of the 2008 International Conference on Web Search and Data Mining, WSDM ’08 (pp. 95–106). New York. Burt, R. S. (1987). Social contagion and innovation: Cohesion versus structural equivalence. American Journal of Sociology. Burt, R. S. (2000). Decay functions. Social Networks, 22(1), 1–28. Cazabet, R., Amblard, F., & Hanachi, C. (2010). Detection of overlapping communities in dynamical social networks. In SocialCom, (pp. 309–314). Chakrabarti, D., Kumar, R., & Tomkins, A. (2006). Evolutionary clustering. ACM SIGKDD. Clauset, A., Newman, M. E. J., & Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70(6), 066111. Coscia, M., Giannotti, F., & Pedreschi, D. (2011). A classification for community discovery methods in complex networks. Statistical Analysis and Data Mining, 4(5), 512–546. Coscia, M., Rossetti, G., Pedreschi, D., & Giannotti, F. (2012). Demon: a local-first discovery method for overlapping communities. In ACM SIGKDD. Dhouioui, Z., & Akaichi, J. (2014). Tracking dynamic community evolution in social networks. In ASONAM. Folino, F., & Pizzuti, C. (2014). An evolutionary multiobjective approach for community discovery in dynamic networks. IEEE Transactions on Knowledge and Data Engineering, 26(8), 1838–1852. Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3), 75–174. Goh, K.-I., & Barabási, A.-L. (2008). Burstiness and memory in complex systems. EPL (Europhysics Letters), 81(4), 48002. Goldberg, M., Magdon-Ismail, M., Nambirajan, S., & Thompson, J. (2011). Tracking and predicting evolution of social communities. PASSAT. Guo, C., Wang, J., & Zhang, Z. (2014). Evolutionary community structure discovery in dynamic weighted networks. Physica A: Statistical Mechanics and its Applications, 413, 565–576. Kostakos, V. (2009). Temporal graphs. In Physica A: Statistical Mechanics and its Applications. Lancichinetti, A., & Fortunato, S. (2009). Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 80(1), 016118. Lancichinetti, A., Fortunato, S., & Kertész, J. (2009). Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3), 033015. Lee, P., Lakshmanan, L., & Milios, E. (2014). Incremental cluster evolution tracking from highly dynamic network data. In ICDE. Leskovec, J., Kleinberg, J. M., & Faloutsos, C. (2005). Graphs over time: densification laws, shrinking diameters and possible explanations. In ACM SIGKDD. Lin, Y., Chi, Y., & Zhu, S. (2008). Facetnet: A framework for analyzing communities and their evolutions in dynamic networks. In WWW. Nguyen, M. V. (2012). Community evolution in a scientific collaboration network. CEC IEEE. Nguyen, N. P., Dinh, T. N., Xuan, Y., & Thai, M. T. (2011). Adaptive algorithms for detecting community structure in dynamic social networks. In IEEE INFOCOM, (pp. 2282–2290). Nowell, L., & Kleinberg, J. (2003). The link prediction problem for social networks. In CIKM. Palla, G., Barabási, A. L., & Vicsek, T. (2007). Quantifying social group evolution. Nature, 446(7136), 664–667. Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814–818. Passarella, A., Conti, M., Boldrini, C., & Dunbar, R.I. (2011). Modelling inter-contact times in social pervasive networks. In Proceedings of the 14th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems, (pp. 333–340). ACM. Qi, G., Aggarwal, C. C., & Huang, T. S. (2013). Online community detection in social sensing. WSDM. Rinzivillo, S., Mainardi, S., Pezzoni, F., Coscia, M., Giannotti, F., & Pedreschi, D. (2012). Discovering the geographical borders of human mobility. KI - Künstliche Intelligenz, 26(3), 253–260. Rossetti, G., Guidotti, R., Pennacchioli, D., Pedreschi, D., & Giannotti, F. (2015). Interaction prediction in dynamic networks exploiting community discovery. In Proceedings of the 2015 ACM/IEEE International Conference on Advances in Social Network Analysis and Mining. Rossetti, G., Pappalardo, L., & Rinzivillo, S. (2016). A novel approach to evaluate community detection algorithms on ground truth. In 7th Workshop on Complex Networks, Studies in Computational Intelligence. Springer-Verlag. Rossetti, G., Pappalardo, L., Kikas, R., Pedreschi, D., Giannotti, F., & Dumas, M. (2015). Community-centric analysis of user engagement in skype social network. In Proceedings of the 2015 ACM/IEEE International Conference on Advances in Social Network Analysis and Mining. Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4), 1118–1123. Rozenshtein, P., Tatti, N., & Gionis, A. (2014). Discovering dynamic communities in interaction networks. ECML PKDD. Shang, J., Liu, L., & Xie, F. (2012). A real-time detecting algorithm for tracking community structure of dynamic networks. 6th SNA-KDD. Sun, Y., Tang, J., Han, J., Gupta, M., & Zhao, B. (2010). Community evolution detection in dynamic heterogeneous information networks. MLG. Takaffoli, M., Rabbany, R., & Zaiane, O. R. (2014). Community evolution prediction in dynamic social networks. In ASONAM. Takaffoli, M., Sangi, F., Fagnan, J., & Zaïane O. (2011). Modec-modeling and detecting evolutions of communities. ICWSM. Viswanath, B., Mislove, A., Cha, M., & Gummadi, P. K. (2009). On the evolution of user interaction in facebook. WOSN. Wang, P., Gonzàlez, M. C., Hidalgo, C.A., & Barabási, A. L. (2009). Understanding the spreading patterns of mobile phone viruses. Science, 324(5930), 1071–1076. Wu, X., & Liu, Z. (2008). How community structure influences epidemic spread in social networks. Physica A Statistical Mechanics and its Applications, 387, 623–630. Xu, H., Wang, Z., & Xiao, W. (2013). Analyzing community core evolution in mobile social networks. In SocialCom. Zakreweska, A., & Bader, D. (2015). A dynamic algorithm for local community detection in graphs. In ASONAM.