• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2021, Vol. 43 ›› Issue (06): 1067-1075.

• 人工智能与数据挖掘 • 上一篇    下一篇

融合结构-属性交互二部图随机游走的社区搜索方法

李举1,马慧芳1,2,李青青1,宿云1   

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

  • 收稿日期:2020-04-03 修回日期:2020-06-22 接受日期:2021-06-25 出版日期:2021-06-25 发布日期:2021-06-22
  • 基金资助:
    国家自然科学基金(61762078,61363058,61802404);甘肃省自然科学基金(20JR10RA076);西北师范大学青年教师能力提升计划(NWNU-LKQN2019-2);广西可信软件重点实验室研究课题(kx202003)

Community search via random walk based on structure-attribute interaction bipartite graph

LI Ju1,MA Hui-fang1,2,LI Qing-qing1,SU Yun1   

  1. (1.College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070;

    2.Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China)

    Community search in attribute graph is a local community detection method, which is essentially based on the query nodes provided by users to return personalized subgraphs containing query nodes with similar attributes of attributes together with structural cohesion. This task helps users better understand how and why communities are formed. This paper proposes a random walk mechanism based on the structure-attribute interaction bipartite graph, which can effectively support the community search in the attribute graph. Specifically, this method first constructs the structure probability transfer matrix based on the network topology, then explores the bipartite graph formed by the interaction of structure and attribute to define the two-stage node-attribute-node probability transfer matrix, and effectively fuses it with the structure probability transfer matrix to obtain the probability transfer matrix of attribute graph. Finally, a random walk with restart method is designed, and the parallel conductance value based on fusion structure and attribute is used to accurately query the community. Experiments on real datasets and artificial data sets verify the effectiveness and efficiency of the proposed method. 

  • Received:2020-04-03 Revised:2020-06-22 Accepted:2021-06-25 Online:2021-06-25 Published:2021-06-22

摘要: 属性图中的社区搜索是一种局部社区发现方法,本质是基于用户提供的查询节点返回包含查询节点且在结构内聚的同时属性与查询属性相似的个性化子图。该任务有助于用户更好地理解社区是如何形成的以及社区形成的原因。提出了一种融合结构-属性交互二部图随机游走机制,有效地支持属性图中的社区搜索。具体地,首先基于网络拓扑结构构建结构概率转移矩阵;其次探索结构与属性交互形成的二部图定义2阶段的节点-属性-节点概率转移矩阵,将其与结构概率转移矩阵有效融合得到属性图的概率转移矩阵;最后设计重启随机游走方法,基于融合结构和属性的并行电导值精准查询社区。在真实数据集和人工数据集上的实验表明了本文方法的有效性。


关键词: 社区搜索, 随机游走, 属性图, 电导值, 转移矩阵

Abstract: Community search in attribute graph is a local community detection method, which is essentially based on the query nodes provided by users to return personalized subgraphs containing query nodes with similar attributes of attributes together with structural cohesion. This task helps users better understand how and why communities are formed. This paper proposes a random walk mechanism based on the structure-attribute interaction bipartite graph, which can effectively support the community search in the attribute graph. Specifically, this method first constructs the structure probability transfer matrix based on the network topology, then explores the bipartite graph formed by the interaction of structure and attribute to define the two-stage node-attribute-node probability transfer matrix, and effectively fuses it with the structure probability transfer matrix to obtain the probability transfer matrix of attribute graph. Finally, a random walk with restart method is designed, and the parallel conductance value based on fusion structure and attribute is used to accurately query the community. Experiments on real datasets and artificial data sets verify the effectiveness and efficiency of the proposed method. 

Key words: community search, random walk, attribute graph, conductance value, transition matrix