基于属性图的社区搜索模式及其分类体系  

Community search schemata and their classification systems based on attribute graphs

作　　者：赵丹枫[1] 孔万仔 黄冬梅 刘国华[3] ZHAO Danfeng;KONG Wanzai;HUANG Dongmei;LIU Guohua(School of Information,Shanghai Ocean University,Shanghai 201306,China;Shanghai University of Electric Power,Shanghai 200090,China;School of Computer Science and Technology,Donghua University,Shanghai 201620,China)

机构地区：[1]上海海洋大学信息学院,上海201306 [2]上海电力大学,上海200090 [3]东华大学计算机科学与技术学院,上海201620

出　　处：《智能系统学报》2024年第4期791-806,共16页CAAI Transactions on Intelligent Systems

基　　金：国家自然科学青年基金项目(42106190);国家自然科学基金面上项目(61972241).

摘　　要：当前在属性图中的社区搜索方法较多、类型繁杂,没有系统的分类方式,约束了社区搜索的应用。为明确属性图社区搜索的类别,对属性图社区搜索分类方法进行研究。首先,首次提出属性图社区搜索模式的概念,深入分析属性图社区搜索模式之间存在的联系,提出属性图社区搜索模式的等价、从属、交叉、全异4种关系;其次,以搜索模式的输入图属性、输出图拓扑结构和各属性图社区搜索模式的实际意义为基础,构建两层分类体系,第1层是由输入属性图相同的模式集合构成的集族,这里的输入属性图包括时序、空间、关键字、权值、空属性图,第2层是由输出图拓扑结构及实际意义定位到的每一个具体的属性图社区搜索模式;然后,针对第2层中每一种模式,给出对应社区搜索算法的对比分析结果;最后,对所有属性图社区搜索模式的特性集中分析。总体而言,属性图社区搜索模式不仅为理解和分析复杂网络结构提供有力工具,也为解决实际问题提供新的视角和方法。At present,there are many community search methods in the attribute graph,and there is no systematic classification method,which restricts the application of community search.In order to clarify the category of community search in attribute graph,the classification method of attribute community search is studied.Firstly,the concept of attribute community search schema is proposed to analyze the relationship between attribute community search schemata in depth,proposing four relationships of community search mode of attribute graph:equivalence,affiliation,intersected and exclusion.Secondly,a two-layer classification system is constructed based on the input graph attributes of the search mode,the topology of the output graph and the practical significance of the search mode of each attribute community.The first layer is a family of sets composed of the same set of schemata in the input attribute graph.The input attribute graph here includes sequence,space,keyword,weight,and empty attribute graph.The second layer is each specific community search schema located by the topology and practical meaning of the output graph.Then,the comparative analysis result of corresponding community search algorithm is given for each schema in the second layer.Finally,the characteristics of all the community search modes of attribute graphs are analyzed centrally.Overall,the attribute graph community search pattern not only provides a powerful tool for understanding and analyzing complex network structures,but also provides a new perspective and method for solving practical problems.

关 键 词：图论 属性图 社区搜索 模式 内聚性 拓扑结构 关系 社区搜索算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]