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

李青青; 马慧芳; 李举; 李志欣

doi:10.12263/DZXB.20200422

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-12-08

- 属性网络中相似性增强随机游走的多社区搜索
- Multi-Community Search Using Similarity Enhanced Random Walk in Attributed Networks
- 电子学报 2021年49卷第11期页码：2096-2100
- 作者机构：
  
  1.西北师范大学计算机科学与工程学院，甘肃兰州 730070
  2.桂林电子科技大学广西可信软件重点实验室，广西桂林 541004
  3.广西师范大学计算机科学与信息工程学院，广西桂林 541004
- 作者简介：
  
  [ "李青青女，1995年生，甘肃庆阳人.现硕士研究生就读于西北师范大学计算机科学与工程学院，主要研究方向为社区搜索.E-mail:2019211784@nwnu.edu.cn" ]
  [ "马慧芳（通信作者）女，1984年生，甘肃兰州人，现为西北师范大学计算机科学与工程学院教授，主要研究方向为人工智能、数据挖掘与机器学习.E-mail:mahuifang@yeah.net" ]
- 基金信息：
  
  国家自然科学基金(61762078;61363058;6196604);广西多源信息挖掘与安全重点实验室开放基金(MIMS18-08);西北师范大学2019年度青年教师科研能力提升计划重大项目(NWNU-LKQN2019-2);甘肃省自然科学基金(21JR7RA114);甘肃省教育厅优秀研究生“创新之星”项目(2021CX2X-270)
- DOI：10.12263/DZXB.20200422
  中图分类号： O157.5;TP301.6
- 收稿：2020-05-06，
  
  修回：2021-04-07，
  
  纸质出版：2021-11-25
- 稿件说明：
移动端阅览
李青青,马慧芳,李举等.属性网络中相似性增强随机游走的多社区搜索[J].电子学报,2021,49(11):2096-2100.

LI Qing-qing,MA Hui-fang,LI Ju,et al.Multi-Community Search Using Similarity Enhanced Random Walk in Attributed Networks[J].ACTA ELECTRONICA SINICA,2021,49(11):2096-2100.
李青青,马慧芳,李举等.属性网络中相似性增强随机游走的多社区搜索[J].电子学报,2021,49(11):2096-2100. DOI： 10.12263/DZXB.20200422.

LI Qing-qing,MA Hui-fang,LI Ju,et al.Multi-Community Search Using Similarity Enhanced Random Walk in Attributed Networks[J].ACTA ELECTRONICA SINICA,2021,49(11):2096-2100. DOI： 10.12263/DZXB.20200422.

摘要

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

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.

关键词

Keywords

references

竺俊超 , 王朝坤 . 复杂条件下的社区搜索方法 [J]. 软件学报 , 2019 , 30 ( 3 ): 552 - 572 .

ZHU Jun-chao , WANG Chao-kun . Approaches to community search under complex conditions [J]. Journal of Software , 2019 , 30 ( 3 ): 552 - 572 . (in Chinese)

潘剑飞 , 董一鸿 , 陈华辉 , 等 . 基于结构紧密性的重叠社区发现算法 [J]. 电子学报 , 2019 , 47 ( 1 ): 145 - 152 .

PAN Jian-fei , DONG Yi-hong , CHEN Hua-hui , et al . The overlapping community discovery algorithm based on compact structure [J]. Acta Electronica Sinica , 2019 , 47 ( 1 ): 145 - 152 . (in Chinese)

Wang Z Z , Yuan Y , Zhou X 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 .

Liu S , Xia Z . 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 .

Andersen R , Chung F , Lang K . 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 .

Bian Y , Luo D , Yan Y , et al . Memory-based random walk for multi-query local community detection [J]. Knowledge and Information Systems , 2020 , 62 ( 5 ): 2067 - 2101 .

Hsu C C , Lai Y A , Chen W 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 .

Freitas S , Cao N , Xia Y 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 .

Lancichinetti A , Fortunato S , Radicchi F . Benchmark graphs for testing community detection algorithms [J]. Physical review E , 2008 , 78 ( 4 ): 046110 .

刘海姣 , 马慧芳 , 赵琪琪 , 李志欣 . 融合用户兴趣偏好与影响力的目标社区发现 [J]. 计算机研究与发展 , 2021 , 58 ( 1 ): 70 - 82 .

LIU Hai-jiao , MA Hui-fang , ZHAO Qi-qi , LI Zhi-xin . Target community detection with user interest influence [J]. Journal of Computer Research and Development , 2021 , 58 ( 1 ): 70 - 82 . (in Chinese)

Bian Y , Ni J , Cheng W , Zhang X . The multi-walker chain and its application in local community detection [J]. Knowledge and Information Systems , 2019 , 60 ( 3 ): 1663 - 1691 .

Ye W , Mautz D , 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 http://dx.doi.org/10.1109/TKDE.2020.2976063 .

Kamuhanda D , Wang M , He K . Sparse nonnegative matrix factorization for multiple-local-community detection [J]. IEEE Transactions on Computational Social Systems , 2020 , 7 ( 5 ): 1220 - 1233 .

Ding X , Zhang J , Yang J . A robust two-stage algorithm for local community detection [J]. Knowledge-Based Systems , 2018 , 152 : 188 - 199 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于图组合优化的高效社区搜索

规模受限的影响力社区搜索

属性网络中结合用户偏好的社区搜索和离群点检测