一种保留社区结构信息的网络嵌入算法

doi:10.19678/j.issn.1000-3428.0059448

摘要/Abstract

摘要： 现有网络嵌入算法大多只保留了网络的微观结构信息，忽略了网络中普遍存在的社区结构信息，为了将社区结构信息融入到网络嵌入中，以提高网络表示的质量，本文提出了一种保留社区结构信息的网络嵌入算法 PCNE（Preserving Community information in Network Embedding）。首先通过最大化节点之间的一阶和二阶相似性对网络的微观结构进行建模，然后通过分解能够反映网络社区结构信息的社区结构嵌入矩阵对网络的社区结构信息进行建模，最后将二者融合到统一的联合非负矩阵分解框架中，通过微观结构的相似度矩阵和中观结构的社区隶属度矩阵的共同指导得到了融合社区结构信息的节点表示向量。本文在五个真实公开数据集上进行了节点分类实验，实验结果显示 PCNE 比其他现有五种算法分别提升了 Micro-F1 值 0.96%~13.1%，从而验证了本算法的有效性。

Abstract: Most existing network embedding algorithms only retain the micro-structure information of the network, but ignore the community structure information which is important in networks. In order to incorporate the community structure information into the network embedding to improve the quality of network representation, a network embedding algorithm PCNE (Preserving Community information in Network Embedding) that preserves community structure information was proposed. First, the micro-structure of the network is modeled by maximizing the first-order and second-order similarity between nodes, and then the community structure information of the network is modeled by factorizing the community structure embedding matrix which can reflect the community structure information of the network. Finally, under the joint supervision of the similarity matrix of the micro-structure and the community membership matrix of the meso-structure, PCNE obtains the node representation vectors that fused the community structure information by merging the both into a unified joint non-negative matrix factorization framework. We evaluate the performance of the PCNE algorithm by node classification experiments on five real public datasets and compared with other five state-of-the-art embedding models. Experimental results show that the proposed method improves the Micro-F1 by 0.96% ~ 13.1% compared with the other algorithms, thus verifying the effectiveness of PCNE.

吕少卿 , 赵雪莉 , 张潘 , 任新成 . 一种保留社区结构信息的网络嵌入算法[J]. 计算机工程, doi: 10.19678/j.issn.1000-3428.0059448.

LV Shaoqing , ZHAO Xueli , ZHANG Pan , REN Xincheng. A Network Embedding Algorithm with Preserving Community Information[J]. Computer Engineering, doi: 10.19678/j.issn.1000-3428.0059448.

参考文献

[1] Peng C , Xiao W , Jian P , et al. A survey on network embedding[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(5): 833-852
[2] Benson A R , Gleich D F , Leskovec J. Higher-order organization of complex networks[J]. Science, 2016, 353(6295): 163-166.
[3] Cai H, Zheng V W, Chang K C C. A comprehensive survey of graph embedding: problems, techniques, and applications[J]. IEEE Transactions on Knowledge andData Engineering, 2018, 30(9): 1616-1637.
[4] Tu C, Yang C, Liu Z, et al. Network representation learning: an overview[J]. SCIENCE China: Information, 2017, 47(8): 980-996. 涂存超, 杨成, 刘知远, 等. 网络表示学习综述［J］．中国科学: 信息科学, 2017, 47(8) : 980-996.
[5] Chen W, Zhang Y, Li X. Network representation learning[J]. Big Data, 2015,1(3): 8-22. 陈维政, 张岩, 李晓明. 网络表示学习[J]. 大数据, 2015, 1(3): 8-22.
[6] Bhagat S, Cormode G, Muthukrishnan S. Node classification in social networks[M]. Boston: Springer, 2011: 115-148.
[7] Lü L, Zhou T. Link prediction in complex networks: A survey[J]. Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 1150-1170.
[8] Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3-5): 75-174.
[9] Maaten L, Hinton G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research, 2008, 9(Nov): 2579-2605.
[10] Chen J, Wu Y, Fan L, et al. N2VSCDNNR: a local recommender system based on node2vec and rich information network[J]. IEEE Transactions on Computational Social Systems, 2019, 6(3): 456-466.
[11] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5500): 2323-2326.
[12] Belkin M, Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering[C]//Proceedings of Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2001: 585-591.
[13] Cao S, Lu W, Xu Q. Grarep: Learning graph representations with global structural information[C] //Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. New York: ACM, 2015: 891-900.
[14] Ou M, Cui P, Pei J, et al. Asymmetric transitivity preserving graph embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2016: 1105-1114.
[15] Yang C, Sun M, Liu Z, et al. Fast network embedding enhancement via high order proximity approximation[C]// International Joint Conference on Artificial Intelligence. Palo Alto, California: AAAI Press, 2017: 3894-3900.
[16] Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2014: 701-710.
[17] Grover A, Leskovec J. node2vec: Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2016: 855-864.
[18] Tang J, Qu M, Wang M, et al. Line: Large-scale information network embedding[C]//Proceedings of The 24th International Conference on World Wide Web. New York, USA: ACM, 2015: 1067-1077.
[19] Wang D, Cui P, Zhu W. Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2016: 1225-1234.
[20] Cao S, Lu W, Xu Q. Deep neural networks for learning graph representations[C]//Thirtieth AAAI Conference on Artificial Intelligence. Palo Alto, California: AAAI Press, 2016: 1145-1152.
[21] Girvan M, Newman M E J . Community structure in social and biological networks[J]. PNAS, 2001, 99: 7821-7826.
[22] Cherifi H, Palla G, Szymanski B, et al. On community structure in complex networks: challenges and opportunities[J]. Applied Network, 2019.
[23] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.
[24] Tu K, Cui P, Wang X, Wang F, Zhu W. Structural deep embedding for hyper-networks[C]//Thirty-Second AAAI Conference on Artificial Intelligence. 2018: 426-433.
[25] Wang F, Li T, Wang X, et al. Community discovery using nonnegative matrix factorization[J]. Data Mining and Knowledge Discovery, 2011, 22(3): 493-521.
[26] Li Y, Sha C, Huang X, et al. Community detection in attributed graphs: an embedding approach[C]// Thirty-Second AAAI Conference on Artificial Intelligence. New Orleans, USA: AAAI, 2018.
[27] Levy O, Goldberg Y. Neural word embedding as implicit matrix factorization[C]//Advances in neural information processing systems. Cambridge: MIT Press, 2014: 2177-2185.
[28] Lee D D, Seung H S. Algorithms for non-negative matrix factorization[C]//Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2000: 535-541.
[29] Zachary W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[30] Craven M, DiPasquo D, Freitag D, et al. Learning to Extract Symbolic Knowledge from the World Wide Web[C]//Fifteenth AAAI Conference on Artificial Intelligence. USA: AAAI, 1998: 1134-1142.