更精準的社區發現算法-結合網路預測之共同最佳化框架

真實的網路資料常常會因為抽樣方式、隱私考慮等原因而無法拿到完整的資料。在不完整的資料中辨別的社區勢必不比在完整的資料中辨別的社區來得有可信度。在這篇論文中，一個稱作「COPE」的共同最佳化框架被提出，利用同時學習不可見的邊的機率與成員的社區分類機率，來增進社區發現的品質。透過實驗，我們觀察到我們的共同最佳化框架能夠取得比二階段最佳化以及其他現存最優的社區算法還要更好的表現。

關鍵字

連結預測；社區發現；非負矩陣分解；機率；最佳化

並列摘要

Real world network data can be incomplete due to reasons such as data subsampling, privacy protection, etc. Consequently, communities identified based on such incomplete network information could be not as reliable as the ones identified based on the fully observed information. In this paper, a joint optimization framework COPE is proposed to improve community detection quality through learning the probability of unseen links and the probability of community affiliation of nodes simultaneously. Through the experiments, we have observed that our joint framework outperforms the interactive 2-stage approach as well as several state-of-the-art community detection algorithms.

並列關鍵字

Link Prediction ； Community Detection ； Non-negative Matrix Factorization ； Probability ； Optimization

參考文獻

[1] S. Fortunato, “Community detection in graphs,” Physics reports, vol. 486, no. 3, pp. 75–174, 2010.

[3] S. Soundarajan and J. Hopcroft, “Using community information to improve the precision of link prediction methods,” in Proceedings of the 21st International Conference on World Wide Web, pp. 607–608, ACM, 2012.

[4] M. Burgess, E. Adar, and M. Cafarella, “Link-prediction enhanced consensus clustering for complex networks,” PloS one, vol. 11, no. 5, p. e0153384, 2016.

[6] M. Rosvall and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” Proceedings of the National Academy of Sciences, vol. 105, no. 4, pp. 1118–1123, 2008.

[7] A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato, “Finding statistically significant communities in networks,” PloS one, vol. 6, no. 4, p. e18961, 2011.

國際替代計量

更精準的社區發現算法-結合網路預測之共同最佳化框架

全文下載

主題瀏覽