Research On K-connected Core Community Detection And Search Problem In Multilayer Network

In the Internet age,with the increasing popularity of Internet applications,more and more big data application problems use graphs to represent their data structures.Graph,also known as networks,is an important data structure.In the traditional graph model,the nodes are of a single type,for example,commodities,users,etc.;the edges are also of a single type,indicating the relationship between two nodes,such as a friend relationship.A community is a set of vertices in a graph,and its internal nodes are more closely connected than internal and external nodes.The k-core is a community type that is widely adopted for its concise definition and efficient algorithms.K-core community detection and search are two important types of graph-based problem.Previous studies of these two types of problems have been based on traditional graph models.With the complexity of application problems,some problems are difficult to express using traditional graph models.For example,in social networks,people want to find those users whose physical locations are cdose and at the same time are friends,and this problem can usually be modeled in multilayer network.Vertices are shared across layers of a multilayer network with different types of edges.Different layers represent different aspects of interaction between vertices in the system,enabling the expression of broader concepts and more complex problems.Therefore,in recent years,related research on multilayer networks has become a new research hotspot.The research on multilayer network is still in its infancy,and there are few related researches.This paper studies the problem of k-connected core community detection and search in multilayer networks.This paper proposes a new model:k-connected core.used to model the k-core community in a multilayer network.This paper mainly studies three types of problems:k-connected core community discovery problems,maximum k-connected core community detection problems and k-connected core community search problems.(1)K-connected core community detection problem refers to the given multilayer network G and vector k,finding all k-connected cores on a multilayer network.This paper proposes an approximate linear algorithm for computing all k-connected cores in G.(2)The maximum k-connected core community detection problem refers to finding all the largest k-connected cores on a multilayer network.The maximum k-connected core is the k-connected core with the largest threshold k of all k-connected cores in the graph.For the special case dual network of multilayer network,this paper proposes a bottom-up and a top-down algorithm for the maximum k-connected core detection,and finally proposes an efficient binary search algorithm.For the general multilayer network,this paper proposes an efficient algorithm for detecting the maximum k-connected core based on the breadth-first search strategy.(3)The problem of k-connected core community search is to find the problem of k-connected cores containing a given set of vertices in the graph.In a multilayer network,this paper designs an efficient index structure to search k-connected core containing a set of query vertices.Based on the proposed index structure,this paper presents an efficient query processing algorithm and polynomial time index construction algorithm.This paper evaluates the performance and effectiveness of the proposed algorithm in a large open real-word dataset including reference network,recommendation network,geographic social network,and social network and so on.At the same time,the large-scale synthetic data set was synthesized by the open random graph generator that satisfies the typical social network model,and the performance and scalability of tlhe algorithm were evaluated.The experimental results in this paper confirm that the proposed algorithm has good performance in all scenarios.When the dataset size increases,the algorithm still has good scalability and robustness,and there is no unacceptable time o-verhead.At the same time,the case study comparing the densest and connected subgraphs[28]on the Gowalla[7]Udataset confirms that the proposed k-connected core model has good properties,and each vertex in the k-connected core has higher degrees,no outliers with lower degrees,can better represent communities with cohesive atftributes in the network.