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

LI Qing-qing; MA Hui-fang; LI Ju; LI Zhi-xin

doi:10.12263/DZXB.20200422

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2025-12-08

- Multi-Community Search Using Similarity Enhanced Random Walk in Attributed Networks
- ACTA ELECTRONICA SINICA Vol. 49, Issue 11, Pages: 2096-2100(2021)
- 作者机构：
  
  1.西北师范大学计算机科学与工程学院，甘肃兰州 730070
  2.桂林电子科技大学广西可信软件重点实验室，广西桂林 541004
  3.广西师范大学计算机科学与信息工程学院，广西桂林 541004
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20200422
  CLC： O157.5;TP301.6
- Received：06 May 2020，
  
  Revised：2021-04-07，
  
  Published：25 November 2021
- 稿件说明：
移动端阅览
李青青,马慧芳,李举等.属性网络中相似性增强随机游走的多社区搜索[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

CS-ROMF:Efficient Community Search Based on Graph Combinatorial Optimization

Size-Constrained Influential Community Search

Incorporating User Preference for Community Search and Outlier Detection in Attributed Network

Related Author

LI Li-bo

ZHAO Yu-han

WANG Xing-fen

ZHANG An-ran

ZHOU Jun-feng

SONG Jia-yi

DU Ming

LI Zhi-xin

Related Institution

Beijing Information Science and Technology University

Hong Kong Baptist University, Hongkong

School of Computer Science and Technology， Donghua University

College of Computer Science and Engineering, Northwest Normal University

Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Science and Technology

⁰