融合节点属性与结构信息的子空间异常社区检测方法

doi:10.19678/j.issn.1000-3428.0054210

计算机工程 ›› 2020, Vol. 46 ›› Issue (6): 94-102. doi: 10.19678/j.issn.1000-3428.0054210

融合节点属性与结构信息的子空间异常社区检测方法

赵琪琪¹, 马慧芳^1,2, 刘海姣¹, 贾俊杰¹

1. 西北师范大学计算机科学与工程学院, 兰州 730070;
2. 桂林电子科技大学广西可信软件重点实验室, 广西桂林 541004

收稿日期:2019-03-13 修回日期:2019-05-24 发布日期:2019-07-12
作者简介:赵琪琪(1994-),女,硕士研究生,主研方向为异常社区检测、数据挖掘;马慧芳(通信作者),教授、博士;刘海姣,硕士研究生;贾俊杰,副教授、博士。
基金资助:
国家自然科学基金（61762078，61363058）；广西可信软件重点实验室研究课题（kx202003）；西北师范大学2019年青年教师科研能力提升计划重大项目（NWNU-LKQN2019-2）；广西多源信息挖掘与安全重点实验室开放基金（MIMS18-08）。

Anomaly Community Detection Method via Subspace Combining Node Attribute and Structure Information

ZHAO Qiqi¹, MA Huifang^1,2, LIU Haijiao¹, JIA Junjie¹

1. College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China;
2. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China

Received:2019-03-13 Revised:2019-05-24 Published:2019-07-12

摘要/Abstract

摘要： 结合社区中的节点属性与结构信息，提出一种子空间异常社区检测方法。在待检测社区集合中，设计基于属性平均距离的子空间求解策略、基于负熵加权的子空间推断策略及子空间融合求解策略，挖掘每个社区的属性权重子空间，并根据社区结构关系定义社区质量评估模型量化社区质量分数，从而获得质量分数较低的异常社区集合。实验结果表明，该方法可以准确地发现异常社区，并且在人工网络和真实网络数据集上相比AMEN、SODA等检测方法具有更好的鲁棒性和可扩展性。

关键词: 社区集合, 属性信息, 结构信息, 异常社区检测, 子空间, 质量评估函数

Abstract: This paper proposes an anomaly community detection method via subspace by combining node attributes with structure information.First,in the given set of to-be-tested communities,the subspace solution strategy based on the average distance of attributes,the subspace inference strategy based on negative entropy weighting and the subspace fusion solution strategy are designed to excavate the attribute weight subspace of each community.Second,the quality assessment model is defined based on the community structure relationships to quantify the community quality scores.Finally,the set of anomaly communities with a low quality score is obtained.Experimental results show that the proposed method can accurately detect anomaly communities,and has better robustness and scalability than AMEN,SODA and other detection methods in artificial network and real network datasets.

Key words: community set, attribute information, structure information, anomaly community detection, subspace, quality assessment function

中图分类号:

TP311

赵琪琪, 马慧芳, 刘海姣, 贾俊杰. 融合节点属性与结构信息的子空间异常社区检测方法[J]. 计算机工程, 2020, 46(6): 94-102.

ZHAO Qiqi, MA Huifang, LIU Haijiao, JIA Junjie. Anomaly Community Detection Method via Subspace Combining Node Attribute and Structure Information[J]. Computer Engineering, 2020, 46(6): 94-102.

https://www.ecice06.com/CN/Y2020/V46/I6/94

图/表 7

20200617085726

20200617085729

20200617085732

20200617085735

20200617085738

20200617085742

20200617085745

参考文献

[1] AKOGLU L,MCGLOHON M,FALOUTSOS C.OddBall:spotting anomalies in weighted graphs[C]//Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining.Berlin,Germany:Springer,2010:410-421.
[2] TSOURAKAKIS C E,BONCHI F,GIONIS A,et al.Denser than the densest subgraph:extracting optimal quasi-cliques with quality guarantees[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2013:104-112.
[3] HE Chaobo,TANG Yong,LIU Hai,et al.Method for community mining integrating link and attribute information[J].Chinese Journal of Computers,2017,40(3):601-616.(in Chinese)贺超波,汤庸,刘海,等.一种集成链接和属性信息的社区挖掘方法[J].计算机学报,2017,40(3):601-616.
[4] ZHOU Y,CHENG H,YU J X.Graph clustering based on structural/attribute similarities[J].Proceedings of the VLDB Endowment,2009,2(1):718-729.
[5] HUANGX,CHENG H,YU J X.Dense community detection in multi-valued attributed networks[J].Information Sciences,2015,314:77-99.
[6] XU Sen,LU Zhimao,GU Guochang.Two spectral algorithms for ensembling document clusters[J].Acta Automatica Sinica,2009,35(7):997-1002.(in Chinese)徐森,卢志茂,顾国昌.解决文本聚类集成问题的两个谱算法[J].自动化学报,2009,35(7):997-1002.
[7] NEWMAN M E.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.
[8] LEMAN A,TONG H H,BRENDAN M,et al.PICS:parameter-free identification of cohesive subgroups in large attributed graphs[C]//Proceedings of 2012 SIAM International Conference on Data Mining.[S.l.]:SIAM,2012:439-450.
[9] MA Huifang,CHEN Haibo,ZHAO Weizhong,et al.Leveraging tag mean partition distance and social structure for overlapping microblog user community detection[J].Acta Electronica Sinica,2018,46(11):2612-2618.(in Chinese)马慧芳,陈海波,赵卫中,等.融合标签平均划分距离和结构关系的微博用户可重叠社区发现[J].电子学报,2018,46(11):2612-2618.
[10] PEROZZI B,AKOGLU L,SÁNCHEZ P I.Focused clustering and outlier detection in large attributed graphs[C]//Proceedings of ACM International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2014:1346-1355.
[11] BRYAN P,LEMAN A.Scalable anomaly ranking of attributed neighborhoods[C]//Proceedings of 2016 SIAM International Conference on Data Mining.[S.l.]:SIAM,2016:1-10.
[12] LESKOVEC J,LANG K J,DASGUPTA A,et al.Statistical properties of community structure in large social and information networks[C]//Proceedings of the 17th International Conference on World Wide Web.New York,USA:ACM Press,2008:695-704.
[13] GLEICH D F,SESHADHRI C.Vertex neighborhoods,low conductance cuts,and good seeds for local community methods[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2012:597-605.
[14] ARNABOLDI V,CONTI M,PASSARELLA A,et al.Analysis of ego network structure in online social networks[C]//Proceedings of ASE/IEEE International Conference on Social Computing and ASE/IEEE International Conference on Privacy.Washington D.C.,USA:IEEE Press,2012:31-40.
[15] LESKOVEC J,KLEINBERG J,FALOUTSOS C.Graphs over time:densification laws,shrinking diameters and possible explanations[C]//Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.New York,USA:ACM Press,2005:177-187.
[16] MCGLOHON M,AKOGLU L,FALOUTSOS C.Weighted graphs and disconnected components:patterns and a generator[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2008:524-532.
[17] YANG J,LESKOVEC J.Defining and evaluating network communities based on ground-truth[C]//Proceedings of ICDM'12.Washington D.C.,USA:IEEE Press,2012:745-754.
[18] SILVA A,ZAKI M J.Mining attribute-structure correlated patterns in large attributed graphs[J].Proceedings of the VLDB Endowment,2012,5(5):466-477.
[19] JIANG Shengyi,YANG Bohong,WANG Lianxi.An adaptive dynamic community detection algorithm based on incremental spectral clustering[J].Acta Automatica Sinica,2015,41(12):2017-2025.(in Chinese)蒋盛益,杨博泓,王连喜.一种基于增量式谱聚类的动态社区自适应发现算法[J].自动化学报,2015,41(12):2017-2025.
[20] CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):66-111.
[21] KARPIS G,KUMAR V.A fast and high quality multilevel scheme for partitioning irregular graphs[J].SIAM Journal on Scientific Computing,1998,20(1):359-392.
[22] YANG J,LESKOVEC J.Community-affiliation graph model for overlapping network community detection[C]//Proceedings of the 12th International Conference on Data Mining.Washington D.C.,USA:IEEE Press,2012:1170-1175.
[23] ANDERSEN R,LANG K J.Communities from seed sets[C]//Proceedings of WWW'06.New York,USA:ACM Press,2006:223-232.
[24] PAN Jianfei,DONG Yihong,CHEN Huahui,et al.The overlapping community discovery algorithm based on compact structure[J].Acta Electronica Sinica,2019,47(1):145-152.(in Chinese)潘剑飞,董一鸿,陈华辉,等.基于结构紧密性的重叠社区发现算法[J].电子学报,2019,47(1):147-154.
[25] COSCIA M,ROSSETTI G,GIANNOTTI F,et al.DEMON:a local-first discovery method for overlapping communities[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2012:615-623.
[26] NOBLE C C,VCOOK D J.Graph-based anomaly detection[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2003:631-636.
[27] GAO J,LIANG F,FAN W,et al.On community outliers and their efficient detection in information networks[C]//Proceedings of KDD'10.New York,USA:ACM Press,2010:813-822.
[28] WU P,PAN L.Mining target attribute subspace and set of target communities in large attributed networks[EB/OL].[2019-02-04].https://arxiv.org/abs/1705.03590.
[29] BROWN J N,BREWER H M,NICORA C D,at al.Protein and microRNA biomarkers from lavage,urine,and serum in military personnel evaluated for dyspnea[J].BMC Medical Genomics,2014,7(1):1-18.
[30] DANON L,DUCH J,ARENAS A,et al.Community structure identification[M].[S.l.]:Mendeley,2005.

选择文件类型/文献管理软件名称

选择包含的内容

融合节点属性与结构信息的子空间异常社区检测方法

Anomaly Community Detection Method via Subspace Combining Node Attribute and Structure Information

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	秦灏, 戚志东, 于灵芝, 童新. 基于IECSDE算法的PEMFC改进分数阶子空间辨识模型[J]. 计算机工程, 2024, 50(6): 346-357.
[2]	江雨燕, 陶承凤, 李平. 数据增强和自适应自步学习的深度子空间聚类算法[J]. 计算机工程, 2023, 49(8): 96-103, 110.
[3]	胡慧旗, 张维强, 徐晨. 判别性增强的稀疏子空间聚类[J]. 计算机工程, 2023, 49(2): 98-104.
[4]	王帅坤, 周志勇, 胡冀苏, 钱旭升, 耿辰, 陈光强, 纪建松, 戴亚康. 基于深度学习的肝脏CT-MR图像无监督配准[J]. 计算机工程, 2023, 49(1): 223-233.
[5]	车超, 刘迪. 基于双向对齐与属性信息的跨语言实体对齐[J]. 计算机工程, 2022, 48(3): 74-80.
[6]	刘鹏飞, 朱健晨, 万良易, 江波. 低功耗异构计算架构的高光谱遥感图像分类研究[J]. 计算机工程, 2022, 48(12): 9-15,23.
[7]	贾思宇, 路茗, 丁华泽, 陈明, 赵鲁阳. 一种改进的信号子空间聚焦宽带DOA估计算法[J]. 计算机工程, 2022, 48(1): 175-181.
[8]	刘峰, 王宝亮, 邹荣宇, 赵浩淳. 基于随机游走的网络表示学习推荐算法[J]. 计算机工程, 2021, 47(9): 90-96,105.
[9]	陶洋, 鲍灵浪, 胡昊. 结构约束的对称低秩表示子空间聚类算法[J]. 计算机工程, 2021, 47(4): 56-61,67.
[10]	许柏炎, 蔡瑞初, 梁智豪. 一种用于代码注释自动生成的语法辅助复制机制[J]. 计算机工程, 2021, 47(4): 92-99.
[11]	孙登第, 凌媛, 丁转莲, 罗斌. 基于稀疏子空间聚类的多层网络社团检测[J]. 计算机工程, 2021, 47(10): 52-60.
[12]	陈会伟, 刘树美, 刘培学, 公茂法. 超尺度自导注意力网络的遥感船舶识别[J]. 计算机工程, 2021, 47(10): 314-320.
[13]	刘宇航, 马慧芳, 刘海姣, 余丽. 一种可重叠子空间K-Means聚类算法[J]. 计算机工程, 2020, 46(8): 58-63,71.
[14]	马喆康, 迪力亚尔·帕尔哈提, 早克热·卡德尔, 吐尔根·依布拉音, 西尔艾力·色提, 艾山·吾买尔. 一种集成深度学习模型的旅游问句文本分类算法[J]. 计算机工程, 2020, 46(11): 70-76.
[15]	王少波, 郭英, 眭萍, 李红光, 杨鑫. 欠定条件下同步组网跳频信号盲源分离方法[J]. 计算机工程, 2020, 46(10): 166-172,181.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

融合节点属性与结构信息的子空间异常社区检测方法

Anomaly Community Detection Method via Subspace Combining Node Attribute and Structure Information

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 15

编辑推荐

Metrics

本文评价