Multi-query based key node mining algorithm for social networks

Guodong XIN; Tengwei ZHU; Junheng HUANG; Jiayang Wei; Runxuan Liu; Wei WANG

doi:10.11959/j.issn.2096-109x.2024013

您当前的位置：

首页 >

文章列表页 >

Multi-query based key node mining algorithm for social networks

Papers | 更新时间：2024-06-03

- Multi-query based key node mining algorithm for social networks
- Chinese Journal of Network and Information Security Vol. 10, Issue 1, Pages: 79-90(2024)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2024013
  CLC： TN92
- Online First：2024-02，
  
  Published：25 February 2024
- 稿件说明：
移动端阅览
Guodong XIN, Tengwei ZHU, Junheng HUANG, et al. Multi-query based key node mining algorithm for social networks[J]. Chinese Journal of Network and Information Security, 2024, 10(1): 79-90.
DOI：

Guodong XIN, Tengwei ZHU, Junheng HUANG, et al. Multi-query based key node mining algorithm for social networks[J]. Chinese Journal of Network and Information Security, 2024, 10(1): 79-90. DOI： 10.11959/j.issn.2096-109x.2024013.

摘要

关键节点挖掘是复杂网络领域的研究重点和热点。针对社交网络中关键嫌疑人挖掘问题，提出基于多查询的社交网络关键节点挖掘算法。该算法将已知嫌疑人作为查询节点，提取其所在的局部拓扑结构，并计算局部拓扑结构中非查询节点的关键程度，从中选择关键程度较高的节点进行推荐。针对现有方法中关键节点计算复杂度高、已知查询节点信息难以有效利用的问题，提出一个两阶段的基于多查询的社交网络关键节点挖掘算法，整合多查询节点的局部拓扑信息和全局节点聚合特征信息，将计算范围从全局缩减到局部，进而对相关节点的关键程度进行量化。具体而言，利用带重启策略的随机游走算法获得多个查询节点的局部拓扑结构；为了得到节点的嵌入向量，基于 graphsage 模型构建一种无监督的图神经网络模型，该模型结合节点的自身特征和邻居聚合特征来生成嵌入向量，从而为算法框架的相似度计算提供信息输入。基于与查询节点特征的相似性，衡量局部拓扑中节点的关键程度。实验结果显示，所提算法在时间效率和结果有效性方面均优于传统关键节点挖掘算法。

Abstract

Mining key nodes in complex networks has been a hotly debated topic as it played an important role in solving real-world problems.However

the existing key node mining algorithms focused on finding key nodes from a global perspective.This approach became problematic for large-scale social networks due to the unacceptable storage and computing resource overhead and the inability to utilize known query node information.A key node mining algorithm based on multiple query nodes was proposed to address the issue of key suspect mining.In this method

the known suspects were treated as query nodes

and the local topology was extracted.By calculating the critical degree of non-query nodes in the local topology

nodes with higher critical degrees were selected for recommendation.Aiming to overcome the high computational complexity of key node mining and the difficulty of effectively utilizing known query node information in existing methods

a two-stage key node mining algorithm based on multi-query was proposed to integrate the local topology information and the global node aggregation feature information of multiple query nodes.It reduced the calculation range from global to local and quantified the criticality of related nodes.Specifically

the local topology of multiple query nodes was obtained using the random walk algorithm with restart strategy.An unsupervised graph neural network model was constructed based on the graphsage model to obtain the embedding vector of nodes.The model combined the unique characteristics of nodes with the aggregation characteristics of neighbors to generate the embedding vector

providing input for similarity calculations in the algorithm framework.Finally

the criticality of nodes in the local topology was measured based on their similarity to the features of the query nodes.Experimental results demonstrated that the proposed algorithm outperformed traditional key node mining algorithms in terms of time efficiency and result effectiveness.

关键词

Keywords

references

任晓龙 , 吕琳媛 . 网络重要节点排序方法综述 [J ] . 科学通报 , 2014 , 59 ( 13 ): 1175 - 1197 .

REN X L , LYU L Y . Review of ranking nodes complex networks [J ] . Science Bulletin , 2014 , 59 ( 13 ): 1175 - 1197 .

LU P , DONG C . Ranking the spreading influence of nodes in complex networks based on mixing degree centrality and local structure [J ] . International Journal of Modern Physics B , 2019 , 33 ( 32 ): 1950395 .

FA N Y , ZHANG R , ZHAO Y , et al . Identifying the most influential spreaders in complex networks by an extended local K-shell sum [J ] . International Journal of Modern Physics C , 2017 , 28 ( 1 ): 925 - 214 .

SARA A , HASSAN B . Identification of influential spreaders in complex networks using HybridRank algorithm [J ] . Scientific Reports , 2018 , 8 ( 1 ): 11932 .

HAI J , QIAN C , YU D , et al . Parallel computation of hierarchical closeness centrality and applicationst [C ] // Proceedings of World Wide Web . 2018 : 3047 - 3064 .

NEWMAN M E J . A measure of betweenness centrality based on random walks [J ] . Social Networks , 2004 , 27 ( 1 ): 39 - 54 .

BRIN S , PAGE L , MOTWAMI R , et al . The PageRank citation ranking:bringing order to the Web [Z ] . Stanford Digital Libraries Working Paper , 1998 ( 6 ): 102 - 107 .

XU S , WANG P . Identifying important nodes by adaptive LeaderRank [J ] . Physica A:Statistical Mechanics and its Applications , 2017 , 469 : 654 - 664 .

陈勇 , 胡爱群 , 胡啸 . 通信网中节点重要性的评价方法 [J ] . 通信学报 , 2004 , 25 ( 8 ): 129 - 134 .

CHEN Y , HU A Q , HU X . Evaluation method of node importance in communication network [J ] . Journal on Communications , 2004 , 25 ( 8 ): 129 - 134 .

谭跃进 , 吴俊 , 邓宏钟 . 复杂网络中节点重要度评估的节点收缩方法 [J ] . 系统工程理论与实践 , 2006 ,( 11 ): 79 - 83 .

TAN Y J , WU J , DENG H Z . Node importance in complex networks [J ] . Systems Engineering Theory and Practice , 2006 ,( 11 ): 79 - 83 .

RASHID Y , BHAT J I . OlapGN:a multi-layered graph convolution network-based model for locating influential nodes in graph networks [J ] . Knowledge-Based Systems , 2024 ,( 283 ).

BOUYER A , BENI H A , ARASTEH B , et al . FIP:A fast overlapping community-based influence maximization algorithm using probability coefficient of global diffusion in social networks [J ] . Expert Systems with Applications , 2023 ,( 213 ).

AGHAALIZADEH S , AFSHORD S T , BOUYER A , et al . A three-stage algorithm for local community detection based on the high node importance ranking in social networks [J ] . Physica A:Statistical Mechanics and its Applications , 2021 , 63 ( 25420 ).

WATTS D J , STROGATZ S H . Collective dynamics of small world network [J ] . Nature , 1998 , 393 ( 4 ): 440 - 442 .

BAHADORI S , MORADI P , ZARE H . An improved limited random walk approach for identification of overlapping communities in complex networks [J ] . Applied Intelligence , 2020 , 51 : 3561 - 3580 .

LIU J , ONG G P , CHEN X M . GraphSAGE-based traffic speed forecasting for segment network with sparse data [J ] . IEEE Transactions on Intelligent Transportation Systems , 2020 , 23 ( 3 ): 1755 - 1766 .

YAN Y , LUO D , NI J , et al . Local graph clustering by multi-network random walk with restart [C ] // Proceedings of Pacific-asia Conference on Knowledge Discovery ＆ Data Mining . 2018 : 490 - 501 .

SEIDMAN S B . Network structure and minimum degree [J ] . Social Networks , 1983 , 5 ( 3 ): 269 - 287 .

SOZIO M , GIONIS A . The community-search problem and how to plan a successful cocktail party [C ] // Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data mining , 2010 : 939 - 948 .

ROSSI R A , AHMED N K . An interactive data repository with visual analytics [J ] . ACM SIGKDD Explorations Newsletter , 2016 , 17 ( 2 ): 37 - 41 .

ARASTEH M , ALIZADEH S . A fast divisive community detection algorithm based on edge degree betweenness centrality [J ] . Applied Intelligence , 2019 , 49 ( 2 ): 689 - 702 .

KERMARREC A M , MERRER E L , SERICOLA B , et al . Second order centrality:Distributed assessment of nodes criticity in complex networks [J ] . Computer Communications , 2010 , 34 ( 5 ): 619 - 628 .

TSALOUCHIDOU I , BAEZA-YATES R , BONCHI F , et al . Temporal betweenness centrality in dynamic graphs [J ] . International Journal of Data Science and Analytics , 2020 , 9 ( 3 ): 257 - 272 .

ZHANG J X , CHEN D B , DONG Q , et al . Identifying a set of influential spreaders in complex networks [J ] . Scientific Reports , 2016 , 6 ( 1 ): 27823 .

SONG YANG. . Networks:an Introduction by M.E.J.Newman [J ] . The Journal of Mathematical Sociology , 2013 , 37 ( 4 ): 250 - 251 .

BEINEKE L W , OELLERMANN O R , PIPPERT R E . The average connectivity of a graph [J ] . Discrete Mathematics , 2002 , 252 ( 1-3 ): 31 - 45 .

LUO D S , BIAN Y C , YAN Y W , et al . Local community detection in multiple networks [C ] // Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data mining , 2020 : 266 - 274 .

Views

157

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Gate-level hardware trojan detection method based on graph Transformer

Research progress on detection of software vulnerabilities based on code similarity

Data augmentation based multi-view contrastive learning graph anomaly detection

Evolutionary game model of information management mechanism for public opinion governance

Sarcasm detection method based on fusion of text semantics and social behavior information

Related Author

Zheng Rui

Yu Hong

Xu Yuhang

DONG Weiyu

TANG Yonghe

LIU Chunling

LI Qinghao

XU Li

Related Institution

Information Engineering University

College of Computer and Information Engineering, Nanjing University of Technology

Fujian Provincial Key Laboratory of Network Security and Cryptology

College of Computer and Cyber Security, Fujian Normal University

Shanghai Municipal Key Lab of Integrated Management Technology for Information Security

⁰