Abnormal link detection algorithm based on semi-local structure

Haoran SHI; Lixin JI; Shuxin LIU; Gengrun WANG

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

您当前的位置：

首页 >

文章列表页 >

Abnormal link detection algorithm based on semi-local structure

Topic: Security Awareness and Detection Method | 更新时间：2024-06-03

- Abnormal link detection algorithm based on semi-local structure
- Chinese Journal of Network and Information Security Vol. 8, Issue 1, Pages: 63-72(2022)
- 作者机构：
  
  1. 信息工程大学，河南郑州 450001
  2. 国家数字交换系统工程技术研究中心，河南郑州 450002
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2021040
  CLC： TP393
- Online First：2022-02，
  
  Published：15 February 2022
- 稿件说明：
移动端阅览
Haoran SHI, Lixin JI, Shuxin LIU, et al. Abnormal link detection algorithm based on semi-local structure[J]. Chinese Journal of Network and Information Security, 2022, 8(1): 63-72.
DOI：

Haoran SHI, Lixin JI, Shuxin LIU, et al. Abnormal link detection algorithm based on semi-local structure[J]. Chinese Journal of Network and Information Security, 2022, 8(1): 63-72. DOI： 10.11959/j.issn.2096-109x.2021040.

摘要

随着网络科学领域研究的进展，所涉及的真实网络类型愈加广泛。复杂系统中存在的冗余错误关系，或出于异常目的刻意发生的行为，如网页错误点击、电信网刺探呼叫等，都对基于网络结构的分析工作造成了重大影响。复杂网络异常连边识别作为图异常检测重要分支，旨在识别网络结构中由于人为制造或数据收集错误所产生的异常连边。现有方法主要从结构相似性角度出发，利用节点间连通结构评估连边异常程度，易导致网络结构分解，且检测精度受网络类型影响较大。针对这一问题，提出了一种CNSCL算法，在半局部结构尺度下计算节点重要性，分析不同类型局部结构，在不同结构中根据半局部中心性量化连边对网络整体连通性贡献，结合节点结构相似性差异量化连边可信程度。由于计算过程中需去掉连边以衡量对网络整体连通性影响，存在节点重要性需重复计算问题。因此在计算过程中，所提算法还设计了一种动态更新方法以降低算法计算复杂度，降低了算法计算复杂度，使其可推广应用至大规模网络。在7种具有不同结构紧密程度的真实网络上与现有方法进行对比，实验结果表明，在 AUC 衡量标准下，该方法较基准方法具有更高的检测精度，且在网络稀疏或缺失条件下，仍能保持较为稳定的识别精度。

Abstract

With the research in network science

real networks involved are becoming more and more extensive.Redundant error relationships in complex systems

or behaviors that occur deliberately for unusual purposes

such as wrong clicks on webpages

telecommunication network spying calls

have a significant impact on the analysis work based on network structure.As an important branch of graph anomaly detection

anomalous edge recognition in complex networks aims to identify abnormal edges in network structures caused by human fabrication or data collection errors.Existing methods mainly start from the perspective of structural similarity

and use the connected structure between nodes to evaluate the abnormal degree of edge connection

which easily leads to the decomposition of the network structure

and the detection accuracy is greatly affected by the network type.In response to this problem

a CNSCL algorithm was proposed

which calculated the node importance at the semi-local structure scale

analyzed different types of local structures

and quantified the contribution of edges to the overall network connectivity according to the semi-local centrality in different structures

and quantified the reliability of the edge connection by combining with the difference of node structure similarity.Since the connected edges need to be removed in the calculation process to measure the impact on the overall connectivity of the network

there was a problem that the importance of nodes needed to be repeatedly calculated.Therefore

in the calculation process

the proposed algorithm also designs a dynamic update method to reduce the computational complexity of the algorithm

so that it could be applied to large-scale networks.Compared with the existing methods on 7 real networks with different structural tightness

the experimental results show that the method has higher detection accuracy than the benchmark method under the AUC measure

and under the condition of network sparse or missing

It can still maintain a relatively stable recognition accuracy.

关键词

Keywords

references

程晓涛 , 刘彩霞 , 刘树新 . 基于局域信息的社交网络信息传播模型 [J ] . 计算机应用 , 2015 , 35 ( 2 ): 322 - 331 .

CHENG X T , LIU C X , LIU S X . Information propagation model for social network based on local information [J ] . Journal of Computer Applications , 2015 , 35 ( 2 ): 322 - 331 .

刘树新 , 季新生 , 刘彩霞 , 等 . 一种信息传播促进网络增长的网络演化模型 [J ] . 物理学报 , 2014 , 63 ( 15 ): 429 - 439 .

LIU S X , JI X S , LIU C X , et al . A complex network evolution model for network growth promoted by information transmission [J ] . Journal of Physics , 2014 , 63 ( 15 ): 429 - 439 .

刘树新 , 季新生 , 刘彩霞 , 等 . 局部拓扑信息耦合促进网络演化 [J ] . 电子与信息学报 , 2016 , 38 ( 9 ): 2180 - 2187 .

LIU S X , JI X S , LIU C X , et al . Information coupling of local topology promoting the network evolution [J ] . Journal of Electronics＆ Information Technology , 2016 , 38 ( 9 ): 2180 - 2187 .

刘树新 , 李星 , 陈鸿昶 , 等 . 基于资源传输匹配度的复杂网络链路预测方法 [J ] . 通信学报 , 2020 , 41 ( 6 ): 70 - 79 .

LIU S X , LI X , CHEN H C , et al . Link prediction method based on matching degree of resource transmission for complex network [J ] . Journal of Communications , 2020 , 41 ( 6 ): 70 - 79 .

POURHABIBI T , ONG K L , KAM B H , et al . Fraud detection:a systematic literature review of graph-based anomaly detection approaches [J ] . Decision Support Systems , 2020 ,133:113303.

AKOGLU L , TONG H , KOUTRA D . Graph-based anomaly detection and description:a survey [J ] . Data Mining and Knowledge Discovery , 2015 , 29 ( 3 ): 626 - 688 .

AKOGLU L , MCGLOHON M , FALOUTSOS C . OddBall:spotting anomalies in weighted graphs [J ] . Lecture Notes in Computer Science , 2010 , 6119 ( 2 ): 410 - 421 .

LALEH N , CARMINATI B , FERRARI E . Graph based local risk estimation in large scale online social networks [C ] // IEEE International Conference on Smart City/Socialcom/Sustaincom . 2016 .

DINF Q , KATENKA N , BARFORD P , et al . Intrusion as (anti ) social communication:characterization and detection [C ] // Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . 2012 .

WU T , QIAO S J , XIAN X P , et al . Network reconstruction and controlling based on structural regularity analysis [J ] . IEEE Transactions on Knowledge and Data Engineering , 2018 , 29 : 1 - 14 .

TONG H , LIN C Y . Non-negative residual matrix factorization with application to graph anomaly detection [C ] // Proceedings of the Eleventh SIAM International Conference on Data Mining . 2011 .

MARTÍNEZ V , BERZAL F , CUBERO J C . A survey of link prediction in complex networks [J ] . ACM Computing Surveys . 2016 , 49 ( 4 ): 1 - 33 .

LORRAIN F , WHITE H C . Structural equivalence of individuals in social networks [J ] . The Journal of Mathematical Sociology , 1971 , 1 ( 1 ): 49 - 80 .

ZHOU T , LÜ L Y , ZHANG Y C . Predicting missing links via local information [J ] . The European Physical Journal B , 2009 , 71 ( 4 ): 623 - 630 .

KLEIN D J , RANDI Ć M , . Resistance distance [J ] . Journal of Mathematical Chemistry , 1993 , 12 ( 1 ): 81 - 95 .

LÜL Y , JIN C H , ZHOU T . Similarity index based on local paths for link prediction of complex networks [J ] . Physical Review E , 2009 , 80 ( 4 ): 046122 .

ZHANG P , WANG X , WANG F , et al . Measuring the robustness of link prediction algorithms under noisy environment [J ] . Scientific Reports , 2016 , 6 ( 1 ): 18881 .

ZENG A , CIMINI G . Removing spurious interactions in complex networks [J ] . Physical Review E , 2012 , 85 ( 3 ): 036101 .

CHEN D B , LYU L Y , SHANG M S , et al . Identifying influential nodes in complex networks [J ] . Physica A:Statistical Mechanics and its Applications , 2012 , 391 ( 4 ): 1777 - 1787 .

RAVASZ E , SOMERA A L , MONGRU D A , et al . Hierarchical organization of modularity in metabolic networks [J ] . Science , 2002 , 297 ( 5586 ): 1551 - 1555 .

XIE Y B , ZHOU T , WANG B H . Scale-free networks without growth [J ] . Physica A:Statistical Mechanics and its Applications , 2008 , 387 ( 7 ): 1683 .

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

REN X L , LYU L Y . Summary of the sorting methods of important network nodes [J ] . Chinese Science Bulletin , 2014 , 59 ( 13 ): 1175 - 1197 .

CHEN D B , LYU L Y , SHANG M S ,, et al .2012 Identifying influential nodes in complex networks [J ] . Physica A:Statistical Mechanics and its Applications , 2012 , 391 ( 4 ): 1777 - 1787 .

王翔 . 链路预测算法鲁棒性的研究 [D ] . 北京:北京邮电大学 , 2016 .

WANG X . Research on Robustness of Link Prediction Algorithm [D ] . Beijing:Beijing University of Posts and Telecommunications , 2016 .

ZHOU K , TOMASZ P M , MARCIN W , et al . Attacking similaritybased link prediction in social networks [C ] // Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems . 2019 : 305 - 313 .

Views

277

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Robust Schnorr-based subgroup multi-signature scheme

Robust deepfake detection method based on siamese network

Robust reinforcement learning algorithm based on pigeon-inspired optimization

Research on the robustness of convolutional neural networks in image recognition

Robustness evaluation of commercial liveness detection platform

Related Author

WANG Zhiwei

ZHU Qiuchi

ZHANG Zhenqi

LIN Shanhe

Mingying ZHANG

Bing HUA

Yuguang ZHANG

Haidong LI

Related Institution

School of Computer Science, Nanjing University of Posts and Telecommunications

Jiangsu Key Laboratory of Big Data Security and Intelligent Processing, Nanjing University of Posts and Telecommunications

Fujian Star-net Communication Company Limited

China Electronics Standardization Institute

College of Astronautics, Nanjing University of Aeronautics and Astronautics

⁰