Non-unidimensional community detection algorithm based on network representation learning

doi:10.11772/j.issn.1001-9081.2019061009

Abstract

Abstract: Focusing on the issue that it is difficult for the existing community detection algorithms to solve the multidimensionality problem of the network, a non-unidimensional community detection algorithm based on network representation learning was proposed. The algorithm considered the difference of nodes from the two dimensions of node attribute feature and network structure feature. Firstly, the node transition probability was calculated according to the node attribute similarity. The length of the random walk path of the network node was set according to the six-degree separation theory of the small world model. After obtaining the walking path of the node by selecting its neighbor nodes according to the transition probability, the walking path of the node was trained by the neural network model to achieve the network feature vectors. The similarity of the network feature vectors of the node was reset as the weight of the connected edge, and the community partition was completed based on the Louvain algorithm. Finally, experiments were conducted on two datasets, Facebook and Giraffe with the Louvain algorithm based on the initial network structure and the unidimensional community detection algorithm as comparison algorithms. Experimental results show that on the Giraffe dataset, compared to the Louvain algorithm, the community detection algorithm based on the node attribute has the modularity increased by 2.7%, the community detection algorithm based on the network structure has the modularity increased by 3.0%, and the proposed non-unidimensional community detection algorithm has the modularity increased by 3.7%. The proposed algorithm focuses on the multidimensionality of the network and improves the modularity of the community detection algorithm effectively.

Key words: node attribute, network structure, extensibility, community detection, network representation learning, node difference

摘要： 针对现有的社区发现算法难以解决网络的多维性问题的现象，提出一种基于网络表示学习的非单一维度的社区发现算法。该算法从节点属性特征和网络结构特征两个维度考虑节点的差异性，首先根据节点属性相似度计算得到节点转移概率，结合小世界模型的六度分离理论设置网络节点随机游走路径的长度。依据转移概率选择节点的邻居节点，得到节点的游走路径，然后用神经网络模型训练节点的游走路径得到节点的网络特征向量，将节点网络特征向量的相似度重置为节点连接边的权重，在Louvain算法的基础上完成社区划分。最后，在Facebook和Giraffe两个数据集上进行了实验，选用基于初始网络结构的Louvain算法和基于单一维度的社区发现算法作为对比算法。实验结果表明，在Giraffe数据集中，相比于Louvain算法，基于节点属性的社区发现算法的模块度指标提升了2.7%，基于网络结构的社区发现算法的模块度指标提升了3.0%，提出的非单一维度的社区发现算法的模块度指标提升了3.7%。所提算法聚焦于网络的多维性，有效提升了社区发现算法的模块度。

关键词: 节点属性, 网络结构, 可扩展性, 社区发现, 网络表示学习, 节点差异性

CLC Number:

TP391.4

CHEN Wanjie, SHENG Yiqiang. Non-unidimensional community detection algorithm based on network representation learning[J]. Journal of Computer Applications, 2019, 39(12): 3467-3475.

陈婉杰, 盛益强. 基于网络表示学习的非单一维度的社区发现算法[J]. 计算机应用, 2019, 39(12): 3467-3475.

References

[1] MCPHERSON M, SMITH-LOVIN L, COOK J M. Birds of a feather:homophily in social networks[J]. Annual Review of Sociology, 2001, 27:415-444.
[2] AIELLO L M, BARRAT A, SCHIFANELLA R, et al. Friendship prediction and homophily in social media[J]. ACM Transactions on the Web, 2012, 6(2):373-382.
[3] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.
[4] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(2 Pt 2):Article No. 026113.
[5] KERNIGHAN B W, LIN S. A efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49(2):291-307.
[6] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(6 Pt 2):Article No. 066133.
[7] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics:Theory and Experiment, 2008, 2008:Article No. P10008.
[8] PEROZZI B, AL-RFOU R, SKIENA S. Deepwalk:online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York:ACM, 2014:701-710.
[9] MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality[C]//Proceedings of the 2013 International Conference on Neural Information Processing Systems. New York:Curran Associates Inc., 2013:3111-3119.
[10] MIKOLOV T, CHEN K, CORRADO G, et al. Efficient estimation of word representations in vector space[EB/OL].[2019-05-20]. https://arxiv.org/abs/1301.3781.
[11] GROVER A, LESKOVEC J. Node2vec:scalable feature learning for networks[C]//Proceeding of the 22nd ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York:ACM, 2016:855-864.
[12] YANG J, LESKOVEC J. Overlapping community detection at scale:a nonnegative matrix factorization approach[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining. New York:ACM, 2013:587-596.
[13] WANG D, CUI P, ZHU W. Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York:ACM, 2016:1225-1234.
[14] LIAO L, HE X, ZHANG H, et al. Attributed social network embedding[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(2):2257-2270.
[15] ZHANG D, YIN J, ZHU X, et al. User profile preserving social network embedding[C]//Proceedings of the 26th International Joint Conference on Artificial Intelligence. Menlo Park:AAAI, 2017:3378-3384.
[16] RAHIMI A, RECHT B. Random features for large-scale kernel machines[C]//Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. New York:Curran Associates Inc., 2008:1177-1184.
[17] 温雯,黄家明,蔡瑞初,等.一种融合节点先验信息的图表示学习方法[J].软件学报,2018,29(3):786-798.(WEN W, HUANG J M, CAI R C, et al. Graph embedding by incorporating prior knowledge on vertex information[J]. Journal of Software, 2018,29(3):786-798.)
[18] YANG C, LIU Z, ZHAO D, et al. Network representation learning with rich text information[C]//Proceeding of the 24th International Joint Conference on Artificial Intelligence. Menlo Park:AAAI, 2015:2111-2117.
[19] HUANG X, LI J, HU X. Accelerated attributed network embedding[C]//Proceedings of the 2017 SIAM International Conference on Data Mining. Philadelphia:SIAM, 2017:633-641.
[20] YANG Z, COHEN W W, SALAKHUTDINOV R. Revisiting semi-supervised learning with graph embeddings[C]//Proceeding of the 33rd International Conference on Machine Learning. New York:JMLR, 2016:40-48.
[21] TU C, LIU H, LIU Z, et al. CANE:context-aware network embedding for relation modeling[C]//Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics. Stroudsburg:Association for Computational Linguistics, 2017:1722-1731.
[22] YANG H W, HSU H C, YANG C K, et al. Differentiating between morphologically similar species in genus Cinnamomum (Lauraceae) using deep convolutional neural networks[J]. Computers and Electronics in Agriculture, 2019, 162:739-748.
[23] CHANG J, BLEI D M. Relational topic models for document networks[C]//Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. Florida:PMLR, 2009:81-88.
[24] GYAMFI K S, BRUSEY J, HUNT A, et al. A dynamic linear model for heteroscedastic LDA under class imbalance[J]. Neurocomputing, 2019, 343:65-75.
[25] LE T M V, LAUW H W. Probabilistic latent document network embedding[C]//Proceedings of the 2014 IEEE International Conference on Data Mining. Piscataway:IEEE, 2014:270-279.
[26] LI H, WANG H, YANG Z, et al. Variation autoencoder based network representation learning for classification[C]//Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, Student Research Workshop. Stroudsburg:Association for Computational Linguistics, 2017:56-61.
[27] 李南星,盛益强,倪宏.基于LM算法的MLP模型及其应用[J].网络新媒体技术,2018,7(1):59-63.(LI N X, SHENG Y Q, NI H. A multilayer perceptron model based on Levenberg-Marquardt algorithm with its applications[J]. Journal of Network New Media, 2018, 7(1):59-63.)
[28] LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations:can geographic isolation explain this unique trait?[J]. Behavioral Ecology and Sociobiology, 2003, 54(4):396-405.