基于马尔可夫随机场的大规模网络社团发现研究

Community detection is one of the most important tasks for modeling and analyzing networks. Markov Random Field (MRF) is a type of undirected probabilistic graphical models, which has been successfully used in image segmentation. The task of community detection has similarities with image segmentation, however MRF has been seldomly used in community detection. This may be because: MRF often takes pixel features as the dominant function in image segmentation, while the regular neighborhood relationship between pixels typically serves as an auxiliary factor. However, network topology is irregular. It is just this irregular network topology which mainly contains the community structure. The node attributes, even if they exist, are often diverse in the real world. In this proposal, we try to solve this problem, i.e. using MRF to effectively find community structures in large-scale networks (with or without attributes). It mainly includes: i) how to essentially make the most of topology structure which is the fundamental information in complex networks; ii) how to enable MRF to incorporate the diverse node attributes robustly; iii) how to make MRF effectively deal with large-scale networks. To solve these problems, we will mainly do research on: 1) we redesign the MRF pairwise potential functions, by introducing the random graph null models, which should be particularly suited for dealing with irregular network topologies. Based on this, we will propose a new type of network-oriented MRF models. 2) We design a new type of MRF unary potential functions, by introducing the hidden correlation between network communities and attributed clusters, which should be particularly suited for incorporating the diverse node attributes, making MFR robust and still effective when the community patterns of network topology and node attributes do not match well. 3) We study the efficient model optimization algorithms by utilizing network sparsity and MRF’s decomposable property, combined with the scalable model selections which concurrently evaluate model parameters and complexity, in order to deal with very large networks efficiently. It is our hope that this study will extend the application area of MRF, and lay the foundations for scholars in the future wishing to study community detection using MRF.

社团发现是重要网络分析任务。马尔可夫随机场MRF是无向概率图模型，常用于图像分割。社团发现与图像分割类似，MRF却难用于社团发现，主要由于：图像分割中MRF以像素属性为主导，像素间规则的邻域关系作辅助；但网络拓扑不规则，而正是这种不规则的拓扑中主要蕴含着社团结构，属性即使存在也具多样性。拟解决将MRF用于大规模网络社团发现之难题：i）本质上利用好网络中最基础的拓扑信息；ii）鲁棒融合多样化属性；iii）有效处理大数据。重点研究：1）引入随机图等、设计特别适用于不规则拓扑的成对势函数，提出网络型MRF新模型；2）引入社团与属性类簇间隐关系、设计特别适合于融入多样化属性的MRF单点势函数，当拓扑与属性的分类模式匹配不佳时仍有效；3）基于网络稀疏性与MRF可分解性设计模型优化、结合并行评估模型参数与复杂度的模型选择，以处理大网络。目的是拓展MRF应用领域，为后续基于MRF的社团发现研究打下基础。

社团发现是目前网络数据挖掘的研究热点，在舆情分析、电子商务等场景上有着广泛的应用。目前一些社团发现方法主要包括基于有向概率图模型的方法、基于网络表示学习的方法、基于图深度学习的方法等，然而基于无向概率图模型马尔可夫随机场的方法尚不多见，这主要是由于马尔可夫随机场难于有效刻画不规则的网络拓扑、因此难于从中有效建模网络社团结构特征；进一步，它也难于和其他类型的模型有效融合，以更好的进行社团检测。.针对该问题，项目组开展了一系列深入研究。提出单纯利用不规则网络拓扑的高效马尔可夫随机场社团发现方法、提出结合网络表示学习的增强型马尔可夫随机场社团发现方法、提出马尔可夫随机场分别结合有向概率图模型贝叶斯模型和图深度学习模型图神经网络的端到端社团发现模型，并在电商搜索场景开展应用，通过以上研究解决了马尔可夫随机场难于有效用于大规模网络社团发现真实场景的难题，拓展了其应用范围和前景，为后续采用马尔可夫随机场研究网络社团发现的学者打下基础与提供借鉴。.在本项目资助下，课题组发表相关论文36篇，其中JCR一区Trans和CCF A类论文（仅统计长文）24篇、中文A类期刊《计算机学报》论文1篇，获得了数据挖掘顶会ICDM 2021最佳学生论文奖亚军奖、全国社会媒体处理大会SMP 2022最佳论文奖，并首次“从统计建模到深度学习”的角度在数据挖掘顶刊TKDE上发表了社团发现综述文章，对上述研究成果与思路进行了总结与讨论，相关研究成果得到了国内外同行的广泛关注，具有重要国内外影响。.项目组将提出的方法在不同类型的网络型数据上开展实验，包括Web网络、引文网络、电商网络等，并与一些新方法进行比较，取得了更加优越的性能。相关数据描述和实验结果可参见发表的论文，数据及代码公布于GitHub上，给国内外同行做科学研究使用。