Local Community Detection On Multi-Layer Graphs

Complex systems can be represented abstractly using complex networks.The study of the relationship between objects in complex systems can be transformed into the study of complex network topology,which provides a new solution for the study of complex systems in the real world.Community structure characteristics are one of the important characteristics in complex networks.A community is a subgraph,which internal nodes are relatively closely connected,while inter-community nodes are relatively sparsely connected.Local community detection not only has important theoretical significance,but also has certain application value.The results of community detection can be used in application scenarios such as recommendation systems and public opinion warnings.Compared with the community detection algorithm that requires the global information of the network,local community detection only needs to use the local information near the query node.On the basis of meeting the actual application requirements,it greatly reduces the time and space cost of the algorithm,which has attracted extensive attention from scholars in recent years.Local community detection on a multi-layer graph can not only use information from multiple data sources to make the discovered community more robust.If the graph node related to attributes,we can also discover the similarity of users in the community in more dimensions.This paper studies the local community detection problem on the multi-layer simple graph and the local community detection problem on the multi-layer attributed graph.The main works are as follows:(1)Aiming at the local community detection problem on the multi-layer simple graph,analyze the algorithm based on the local expansion,divide the local community detection into three stages,and define different dynamic membership functions for each stage.In the community core discovery phase,the skeleton of the community is discovered by defining the local core of the node and the fuzzy relationship between the node and its local core;in the community expansion phase,the local Motif modularity on the multi-layer graph is defined based on the higher-order structure on the graph.By optimizing this measure of the community,a relatively complete community structure is gradually discovered;in the closing phase,the boundaries of the community are sorted,and nodes that may still belong to the community are added to the community.Experiments show that the algorithm proposed in this paper can find high-quality communities within a reasonable time.(2)Aiming at the local community detection problem on the multi-layer attributed graph,two flexible attribute local community definitions are proposed:minimum attribute similarity constrained local community and average attribute similarity constrained local community.Speed up the search of local communities by designing corresponding pruning strategies on the DFS and BFS search frameworks.A large number of experiments are performed on datasets from the real world to compare the performance of different algorithms,and different applicable scenarios under the two community definitions are given based on the experimental results.