基于motif连通性的社区搜索方法

Community search method based on motif connectivity

社区搜索的目标是从数据图中得到包含查询顶点的紧密子图,在社会学、生物学等领域有着广泛应用。针对现有基于子图连通性的社区模型的基础连通结构都是完全连通图,无法满足实际应用中用户对社区结构多样性的需求的问题,提出一种基于motif连通性的社区搜索方法,其中包括基于motif连通性的社区(MCC)模型以及两个相应的社区搜索算法——MPCS(Motif-Processed Community Search)算法和基于MP-index的社区搜索算法。MCC模型可以协助用户自由指定社区的基础连通结构,MPCS算法可以用来解决MCC的搜索问题。此外,提出两个分别针对motif实例搜索过程及所属社区判断过程的剪枝优化技术。最后,设计了MP-index以避免社区搜索过程中的冗余遍历操作。在多个真实数据集上进行实验的结果表明:剪枝优化可以使MPCS算法的耗时减少60%~85%,而基于MP-index的社区搜索算法相较于加入剪枝优化的MPCS算法,效率提升普遍达到了2~3个数量级。可见,所提方法在商品推荐和社交网络等问题上有着实际应用价值。

The goal of community search is to obtain compact subgraphs containing query vertices from data graphs,and community search is widely used in sociology,biology,and other fields.In view of the fact that the basic connectivity structures of the existing community models based on subgraph connectivity are all completely connected graphs,which cannot meet the needs of users for the diversity of community structures in practical applications,a community search method based on motif connectivity was proposed,including Motif-Connective Community(MCC)model based on motif connectivity and two corresponding community search algorithms—MPCS(Motif-Processed Community Search)algorithm and MP-index based community search algorithm.MCC model was able to help users freely specify the basic connectivity structure of community,and MPCS algorithm was able to be used to solve the search problem of MCC.Furthermore,two pruning optimization techniques were proposed for the motif instance search process and the belonged community judgment process.Finally,the MP-index forest was designed to avoid redundant traversal operations in the process of community search.Experimental results on multiple real datasets show that the pruning optimization can reduce the running time of MPCS algorithm by 60%to 85%,and the efficiency of the community search algorithm based on MP-index forest is improved by two to three orders of magnitude compared with the efficiency of MPCS algorithm added with pruning optimization.It can be seen that the proposed method has practical application values in commodity recommendation,social network and other issues.