基于弱社团定义的社团划分模型与算法
Model and Algorithm of Community Division Based on Weak Community Definition
DOI: 10.12677/AAM.2020.912250, PDF,    科研立项经费支持
作者: 李文静, 高彩霞*：内蒙古大学数学科学学院，内蒙古 呼和浩特
关键词: 复杂网络；社团结构；弱社团；块坐标下降算法；Complex Network； Community Structure； Weak Community； Block Coordinate Descent Algorithm
摘要: 社团结构是复杂网络的重要特征之一。为了得到更合理的网络社团结构的划分结果，文中给出了一种基于弱社团定义的整数优化模型。由于该模型是组合优化问题，因而较难快速求解。文中基于该模型将其转化为连续优化近似模型，提出一个高效的块坐标下降算法。实验结果证明了基于弱社团定义的优化模型与算法的有效性。
Abstract: Community structure is one of the important characteristics of complex networks. In order to obtain a more reasonable division of the network community structure, this paper considers an integer optimization model that based on the definition of weak community. This problem is often formulated as combinatorial optimization model. Consequently, to solve it efficiently is difficult. Based on this model, this paper transforms it into a continuous optimization approximate model, and proposes an efficient block coordinate descent algorithm. The experimental results prove the effectiveness of the optimization model and algorithm based on the definition of weak communities.
文章引用：李文静, 高彩霞. 基于弱社团定义的社团划分模型与算法[J]. 应用数学进展, 2020, 9(12): 2153-2160. https://doi.org/10.12677/AAM.2020.912250

参考文献

[1] Newman, M.E.J. (2003) The Structure and Function of Complex Networks. SIAM Review, 45, 167-256. [Google Scholar] [CrossRef] 
[2] Shen, H.W. and Cheng, X.Q. (2010) Spectral Methods for the Detection of Network Community Structure: A Comparative Analysis. Journal of Statistical Mechanics: Theory and Experiment, 2010, Article ID: 10020. [Google Scholar] [CrossRef] 
[3] Luxburg, U.V. (2007) A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395-416. [Google Scholar] [CrossRef] 
[4] Wang, X., Qian, B. and Davidson, I. (2014) On Constrained Spectral Clustering and Its Applications. Data Mining and Knowledge Discovery, 28, 1-30. [Google Scholar] [CrossRef] 
[5] Wang, T.S., Lin, H.T. and Wang, P. (2016) Weighted-Spectral Clustering Algorithm for Detecting Community Structures in Complex Networks. Artificial Intelligence Review, 47, 1-21. [Google Scholar] [CrossRef] 
[6] Newman, M.E.J. (2006) Finding Community Structure in Networks Using the Eigenvectors of Matrices. Physical Review E, 74, Article ID: 036104. [Google Scholar] [CrossRef] 
[7] Newman, M.E.J. (2006) Modularity and Community Structure in Networks. Proceedings of the National Academy of Sciences of the United States of America, 103, 8577-8582. [Google Scholar] [CrossRef] [PubMed]
[8] Fortunato, S. and Barthelemy, M. (2007) Resolution Limit in Community Detection. Proceedings of the National Academy of Sciences, 104, 36-41. [Google Scholar] [CrossRef] [PubMed]
[9] Zhang, X., Zhang, S., Wang, R., et al. (2008) Quantitative Function for Community Detection. Physical Review E Statistical Nonlinear and Soft Matter Physics, 77, Article ID: 036109.
[10] Zhang, X.S., Li, Z., Wang, R.S., et al. (2012) A Combinatorial Model and Algorithm for Globally Searching Community Structure in Complex Networks. Journal of Combinatorial Optimization, 23, 425-442. [Google Scholar] [CrossRef] 
[11] Zhang, J., Liu, H., Wen, Z., et al. (2018) A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection. SIAM Journal on Scientific Computing, 40, A3091-A3120. [Google Scholar] [CrossRef] 
[12] Zachary, W.W. (1976) An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research, 33, 452-473. [Google Scholar] [CrossRef] 

为你推荐