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

• 学术论文 • 上一篇    下一篇

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

李青青1, 马慧芳1,2, 李举1, 李志欣3   

  1. 1.西北师范大学计算机科学与工程学院,甘肃 兰州 730070
    2.桂林电子科技大学广西可信软件重点实验室,广西 桂林 541004
    3.广西师范大学计算机科学与信息工程学院,广西 桂林 541004
  • 收稿日期:2020-05-06 修回日期:2021-04-07 出版日期:2021-11-25 发布日期: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

Qing-qing LI1, Hui-fang MA1,2, Ju LI1, Zhi-xin LI3   

  1. 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

摘要:

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

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

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

中图分类号: