灵活的属性社区搜索方法

Flexible community search approaches over attribute graph

社区搜索旨在搜索满足指定条件的紧凑社区,在现实世界中有广泛的应用场景.研究了在属性图中进行社区搜索的问题.考虑到在实际应用中,需要对社区中的顶点数量进行限制,提出了灵活的属性社区搜索问题,其目标是在包含查询结点且结点规模有限的连通子图中,寻找具有最大图属性得分的子图.与传统的社区搜索问题不同,研究采用无参数的社区模型来衡量社区的紧密度,从而避免了指定参数的困难,使查询更加灵活.同时提出了3个算法:精确算法EXACT、启发式算法FACH和优化算法FACH+.在FACH和FACH+中,文中设计了剪枝规则并在FACH+中适当修改了启发策略,可以快速有效地找到符合要求的子图.在多个真实社交网络数据集上的实验结果表明:文中提出的算法在准确性和效率上都具有显著的优势.

Community search aims to search for communities that satisfy specified conditions,and has a wide range of applications in the real world.The problem of community search in attribute graphs is studied.Considering the need to limit the number of vertices in a community in practical applications,a flexible attribute community search problem is proposed,whose goal is to find the subgraph with maximum graph attribute scores among connected subgraphs containing the query node with limited node sizes.Different from the traditional community search problem,a parameter-free community model is adpoted to measure the closeness of the community,thus avoiding the difficulty of specifying parameters and making the query more flexible.Three algorithms are proposed,i.e.,exact algorithm EXACT,heuristic algorithm FACH and optimization algorithm FACH+.In FACH and FACH+,the research designs the pruning rule and modifies the heuristic strategy appropriately in FACH+,which can find the subgraphs that meet the requirements quickly and efficiently.The results of experiments on several real social network datasets show that the algorithms proposed in this paper have significant advantages in both accuracy and efficiency.