属性网络中相似性增强随机游走的多社区搜索

doi:10.12263/DZXB.20200422

电子学报 ›› 2021, Vol. 49 ›› Issue (11): 2096-2100.DOI: 10.12263/DZXB.20200422

属性网络中相似性增强随机游走的多社区搜索

李青青¹, 马慧芳¹^,², 李举¹, 李志欣³

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

收稿日期:2020-05-06 修回日期:2021-04-07 出版日期:2021-11-25
- 作者简介:
- 李青青女，1995年生，甘肃庆阳人.现硕士研究生就读于西北师范大学计算机科学与工程学院，主要研究方向为社区搜索.E-mail:2019211784@nwnu.edu.cn
  马慧芳（通信作者）女，1984年生，甘肃兰州人，现为西北师范大学计算机科学与工程学院教授，主要研究方向为人工智能、数据挖掘与机器学习.E-mail:mahuifang@yeah.net
- 基金资助:
- 国家自然科学基金 (61762078); 广西多源信息挖掘与安全重点实验室开放基金 (MIMS18-08); 西北师范大学2019年度青年教师科研能力提升计划重大项目 (NWNU-LKQN2019-2); 甘肃省自然科学基金 (21JR7RA114); 甘肃省教育厅优秀研究生“创新之星”项目 (2021CX2X-270)

Multi-Community Search Using Similarity Enhanced Random Walk in Attributed Networks

LI Qing-qing¹, MA Hui-fang¹^,², LI Ju¹, LI Zhi-xin³

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

Received:2020-05-06 Revised:2021-04-07 Online:2021-11-25 Published:2021-11-25
- Supported by:
- National Natural Science Foundation of China (61762078); Guangxi Key Laboratory Foundation for Multi-source Information Mining and Security (MIMS18-08); 2019 Key Project of Young Teachers Research Ability Enhancement Program of Northwest Normal University (NWNU-LKQN2019-2); Natural Science Foundation of Gansu Province (21JR7RA114); Innovation Star program for outstanding graduate students of Gansu Department of Education (2021CX2X-270)

摘要/Abstract

摘要：

社区搜索旨在寻找与给定查询节点高度相关的个性化社区.现有社区搜索方法多面向简单网络且处理单个查询节点或假定多个查询节点来自同一社区，这种严格的假设使得算法灵活性受限.据此，提出一种在属性网络中利用查询节点随机游走路径的相似性增强的多社区搜索方法，可以有效地定位查询节点所属的多个局部目标社区.具体地，有效融合网络中高阶结构与属性信息，利用重启随机游走计算各查询节点的重要性分数向量；计算查询节点随机游走路径的相似性并设计一种相似性增强策略，使得在无监督学习中相似路径游走者彼此增强关联从而定位不同查询节点所属的多个社区结构；基于结合结构和属性的并行电导值精准查询社区.真实数据集和人工数据集的实验验证了本文方法的有效性和效率.

关键词: 属性网络, 高阶结构, 相似性增强随机游走, 并行电导, 社区搜索

Abstract:

Community search aims to find personalized communities highly related to the given query nodes. Existing community search methods are applicable to simple networks, and always assume either a single query node is given or multiple query nodes are from the same community, which limits the flexibility of the algorithm. An attributed network oriented multi-community search method, which is designed via random walk path similarity enhancement of query nodes, is proposed to effectively locate multiple local communities that query node belongs. Attribute and high-order structure information in the network are effectively fused, and the importance score vector of each query node is calculated based on random walk with restart. The similarity between random walk paths of query nodes is calculated and the similarity enhancement strategy is designed to enhance the association of similar path walkers so as to locate multiple community structures of different query nodes. Based on the combination of structure and attribute, the parallel conductance is used to accurately find the community. The experiments on both real-world datasets and synthetic datasets verify the effectiveness and efficiency of the proposed method.

Key words: attributed networks, high-order structure, similarity-enhanced random walk, parallel conductance, community search

中图分类号:

O157.5

李青青, 马慧芳, 李举, 李志欣. 属性网络中相似性增强随机游走的多社区搜索[J]. 电子学报, 2021, 49(11): 2096-2100.

LI Qing-qing, MA Hui-fang, LI Ju, LI Zhi-xin. Multi-Community Search Using Similarity Enhanced Random Walk in Attributed Networks[J]. Acta Electronica Sinica, 2021, 49(11): 2096-2100.

图/表 3

参考文献 14

1	竺俊超, 王朝坤. 复杂条件下的社区搜索方法[J]. 软件学报, 2019, 30(3): 552 - 572.
	ZHUJun-chao, WANGChao-kun. Approaches to community search under complex conditions[J]. Journal of Software, 2019, 30(3): 552 - 572. (in Chinese)
2	潘剑飞, 董一鸿, 陈华辉, 等. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145 - 152.
	PANJian-fei,DONGYi-hong,CHENHua-hui,et al. The overlapping community discovery algorithm based on compact structure [J]. Acta Electronica Sinica, 2019, 47(1): 145 - 152. (in Chinese)
3	WangZ Z, YuanY, ZhouX M, et al. Effective and efficient community search in directed graphs across heterogeneous social networks[A]. Proceedings of the 31st Australasian Database Conference[C]. Melbourne, Australia: Springer, 2020. 161 - 172.
4	LiuS, XiaZ. A two-stage BFS local community detection algorithm based on node transfer similarity and local clustering coefficient[J]. Physica A: Statistical Mechanics and its Applications, 2020, 537: 122717.
5	AndersenR, ChungF, LangK. Local graph partitioning using pagerank vectors[A]. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science[C]. Berkeley, CA, USA: IEEE, 2006. 475 - 486.
6	BianY, LuoD, YanY, et al. Memory-based random walk for multi-query local community detection[J]. Knowledge and Information Systems, 2020, 62(5): 2067 - 2101.
7	HsuC C, LaiY A, ChenW H, et al. Unsupervised ranking using graph structures and node attributes[A]. Proceedings of the 10th International Conference on Web Search and Data Mining[C]. Cambridge, UK: ACM, 2017. 771 - 779.
8	FreitasS, CaoN, XiaY L, et al. Local partition in rich graphs[A]. Proceedings of the 2018 IEEE International Conference on Big Data[C]. Seattle, USA: IEEE, 2018. 1001 - 1008.
9	LancichinettiA, FortunatoS, RadicchiF. Benchmark graphs for testing community detection algorithms[J]. Physical review E, 2008, 78(4): 046110.
10	刘海姣, 马慧芳, 赵琪琪, 李志欣. 融合用户兴趣偏好与影响力的目标社区发现[J]. 计算机研究与发展, 2021, 58(1): 70 - 82.
	LIUHai-jiao, MAHui-fang, ZHAOQi-qi, LIZhi-xin. Target community detection with user interest influence[J]. Journal of Computer Research and Development, 2021, 58(1): 70 - 82. (in Chinese)
11	BianY, NiJ, ChengW, ZhangX. The multi-walker chain and its application in local community detection[J]. Knowledge and Information Systems, 2019, 60(3): 1663 - 1691.
12	YeW, MautzD, et al. Incorporating user’s preference into attributed graph clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2020. DOI:10.1109/TKDE.2020.2976063.
13	KamuhandaD, WangM, HeK. Sparse nonnegative matrix factorization for multiple-local-community detection[J]. IEEE Transactions on Computational Social Systems, 2020, 7(5): 1220 - 1233.
14	DingX, ZhangJ, YangJ. A robust two-stage algorithm for local community detection[J]. Knowledge-Based Systems, 2018, 152: 188 - 199.

	方法	Amazon	DBLP	Cora	Synth 1
单社区	MWC	0.919	0.581	0.913	0.927
	LOCLU	0.745	0.767	0.861	0.882
	SERWA-sc	0.893	0.904	0.914	0.926
多社区	MRW	0.895	0.531	0.884	0.910
	S-MLC	0.693	0.631	0.910	0.911
	SERWA	0.911	0.930	0.961	0.968

	方法	Amazon	DBLP	Cora	Synth 1
单社区	MWC	0.919	0.581	0.913	0.927
	LOCLU	0.745	0.767	0.861	0.882
	SERWA-sc	0.893	0.904	0.914	0.926
多社区	MRW	0.895	0.531	0.884	0.910
	S-MLC	0.693	0.631	0.910	0.911
	SERWA	0.911	0.930	0.961	0.968

属性网络中相似性增强随机游走的多社区搜索

Multi-Community Search Using Similarity Enhanced Random Walk in Attributed Networks

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 14

相关文章 1

编辑推荐

Metrics

	方法	Amazon	DBLP	Cora	Synth 1
简单网络	MRW	92	91	72	67
简单网络	S-MLC	116	107	79	68
属性网络	LOCLU	147	135	101	92
属性网络	MWC	91	89	71	64
变体方法	SERWA-noAttri	79	70	49	47
本文方法	SERWA	91	83	69	64