基于重叠社区划分和非回溯矩阵的社交网络多源点检测

doi:10.3778/j.issn.1002-8331.2310-0159

摘要/Abstract

摘要： 在线社交网络的发展为信息传播提供了极大的便利，但同时在一定程度上也成为谣言等信息的重要传播渠道。社交网络的信息源检测对于控制信息的传播起着重要作用。为了解决现有社交网络多源点检测方法准确度不够高的问题，提出了一种新颖的多源点同步检测方法SVT-BiasMSI。该方法将多源检测问题转化为若干单源检测问题，采用局部度中心节点及相邻节点的Jaccard系数选取种子节点，使用Voronoi方法对社交网络进行初步社区划分，通过tolerance neighborhood方法寻找分区之间重叠部分的节点并实现重叠社区划分，为了兼顾网络全局和局部信息，基于传染邻域偏差改进非回溯矩阵多源点检测方法，提高单源点检测精度。在多个社交网络数据集中的实验表明，所提的方法能够有效提高在线社交网络多源点检测和定位准确度。

关键词: 社交网络, 多源检测, 重叠社区划分, 非回溯矩阵, 传染邻域偏值

Abstract: The evolution of online social networks has greatly facilitated the dissemination of information. However, concurrently, it has become a significant channel for the spread of rumors and other false information. The detection of information sources within social networks plays a pivotal role in controlling information propagation. To solve the issue of insufficient accuracy in the existing methods of multi-source detection in social networks, a novel multi-source synchronous detection method, named SVT-BiasMSI, has been proposed. This approach transforms the complex task of multi-source detection into several simpler single-source detection tasks. It leverages the Jaccard coefficient of local degree central nodes and their neighboring nodes to select seed nodes. Following this, the Voronoi method is used for preliminary community partitioning within the social network. The tolerance neighborhood method is then implemented to identify nodes in the overlapping sections between partitions, thereby facilitating the division of overlapping communities. In order to balance the consideration of both global and local network information, the SVT-BiasMSI method integrates an improvement of the nonbacktracking matrix multi-source detection method based on contagion neighborhood bias, thereby enhancing the precision of single-source detection. Experiments conducted on various social network datasets demonstrate that the proposed method significantly improves the precision of multi-source detection and localization in online social networks.

Key words: social networks, multi-source detection, overlapping community partition, nonbacktracking matrix, contagion neighborhood bias

刘岗, 王炎, 张雪芹. 基于重叠社区划分和非回溯矩阵的社交网络多源点检测[J]. 计算机工程与应用, 2025, 61(1): 300-307.

LIU Gang, WANG Yan, ZHANG Xueqin. Multi-Source Detection Based on Overlapping Community Partition and Nonbacktracking Matrix MSI in Social Network[J]. Computer Engineering and Applications, 2025, 61(1): 300-307.

参考文献

[1] LUO W, TAY W P, LENG M. Identifying infection sources and regions in large networks[J]. IEEE Transactions on Signal Processing, 2013, 61(11): 2850-2865.
[2] JIANG J, SHENG W, SHUI Y, et al. K-Center: an approach on the multi-source identification of information diffusion[J]. IEEE Transactions on Information Forensics and Security, 2015, 10(12): 2616-2626.
[3] ZANG W, ZHANG P, ZHOU C, et al. Locating multiple sources in social networks under the SIR model: a divide-and-conquer approach[J]. Journal of Computational Science, 2015, 10(9): 278-287.
[4] WANG Z, SUN C, RUI X, et al. Localization of multiple diffusion sources based on overlapping community detection[J]. Knowledge-Based Systems, 2021, 226: 14.
[5] CHAI Y, WANG Y, ZHU L. Information sources estimation in time-varying networks[J]. IEEE Transactions on Information Forensics and Security, 2021, 16: 2621-2636.
[6] LIU Y X, LI W M, YANG C, et al. Multi-source detection based on neighborhood entropy in social networks[J]. Scientific Reports, 2022, 12(1): 1-12.
[7] ZHANG C, FU L, LONG F, et al. CLP: a community based label propagation framework for multiple source detection[C]/Proceedings of the IEEE Conference on Computer Communications, New York, NY, 2023: 1-10.
[8] SHAO Y, CHEN L, CHEN Y, et al. Identifying multiple influence sources in social networks based on latent space map[J]. Information Sciences, 2023, 635: 375-397.
[9] DONG M, ZHENG B, LI G, et al. Wavefront-based multiple rumor sources identification by multi-task learning[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2022, 6(5): 1068-1078.
[10] SHAO Y, CHEN L, CHEN Y, et al. Social influence source locating based on network sparsification and stratification[J]. Expert Systems with Applications, 2022, 208: 18087.
[11] LI W, GUO C, LIU Y, et al. Rumor source localization in social networks based on infection potential energy[J]. Information Sciences, 2023, 634: 172-188.
[12] SHELKE S, ATTER V. Source detection of rumor in social network—a review[J]. Online Social Networks and Media, 2019, 9: 30-42.
[13] GUO K, HE L, CHEN Y, et al. A local community detection algorithm based on internal force between nodes[J]. Applied Intelligence, 2020, 50(2): 328-340.
[14] TRIVEDI K, RAMANNA S. Overlapping community detection in social networks with Voronoi and tolerance neighborhood-based method[J]. Granular Computing, 2019, 6: 95-106.
[15] 于欢, 张孙贤, 刘子昂, 等. 基于先验估计的传播中心溯源算法[J]. 模式识别与人工智能, 2020, 33(1): 86-92.
YU H, ZHANG S X, LIU Z A, et al. Propagation source tracing algorithm based on priori estimation[J]. Pattern Recognition and Artificial Intelligence, 2020, 33(1): 86-92.
[16] MORONE F, MAKSE H. Influence maximization in complex networks through optimal percolation[J]. Nature, 2016, 524(7563): 65-68.
[17] ERDOS P, RENYI A. On the evolution of random graphs[J]. Publ Math Inst Hung Acad Sci, 1960, 5(1): 17-60.
[18] BARABSI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 2011, 286(5439): 509-512.
[19] PAN J, ZHANG W. Identifying rumor sources using dominant eigenvalue of nonbacktracking matrix[C]//Proceedings of the IEEE Global Conference on Signal & Information Processing, Anaheim, CA, 2018: 748-752.