Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMultislice Modularity Optimization in Community Detection and Image Segmentation
135
0
0.0
(
0
)
Added by
Huiyi Hu
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Because networks can be used to represent many complex systems, they have attracted considerable attention in physics, computer science, sociology, and many other disciplines. One of the most important areas of network science is the algorithmic detection of cohesive groups (i.e., communities) of nodes. In this paper, we algorithmically detect communities in social networks and image data by optimizing multislice modularity. A key advantage of modularity optimization is that it does not require prior knowledge of the number or sizes of communities, and it is capable of finding network partitions that are composed of communities of different sizes. By optimizing multislice modularity and subsequently calculating diagnostics on the resulting network partitions, it is thereby possible to obtain information about network structure across multiple system scales. We illustrate this method on data from both social networks and images, and we find that optimization of multislice modularity performs well on these two tasks without the need for extensive problem-specific adaptation. However, improving the computational speed of this method remains a challenging open problem.
rate research
Read More
Heterogeneous networks are networks consisting of different types of nodes and multiple types of edges linking such nodes. While community detection has been extensively developed as a useful technique for analyzing networks that contain only one type of nodes, very few community detection techniques have been developed for heterogeneous networks. In this paper, we propose a modularity based community detection framework for heterogeneous networks. Unlike existing methods, the proposed approach has the flexibility to treat the number of communities as an unknown quantity. We describe a Louvain type maximization method for finding the community structure that maximizes the modularity function. Our simulation results show the advantages of the proposed method over existing methods. Moreover, the proposed modularity function is shown to be consistent under a heterogeneous stochastic blockmodel framework. Analyses of the DBLP four-area dataset and a MovieLens dataset demonstrate the usefulness of the proposed method.
The maximization of generalized modularity performs well on networks in which the members of all communities are statistically indistinguishable from each other. However, there is no theory bounding the maximization performance in more realistic networks where edges are heterogeneously distributed within and between communities. Using the random graph properties, we establish asymptotic theoretical bounds on the resolution parameter for which the generalized modularity maximization performs well. From this new perspective on random graph model, we find the resolution limit of modularity maximization can be explained in a surprisingly simple and straightforward way. Given a network produced by the stochastic block models, the communities for which the resolution parameter is larger than their densities are likely to be spread among multiple clusters, while communities for which the resolution parameter is smaller than their background inter-community edge density will be merged into one large component. Therefore, no suitable resolution parameter exits when the intra-community edge density in a subgraph is lower than the inter-community edge density in some other subgraph. For such networks, we propose a progressive agglomerative heuristic algorithm to detect practically significant communities at multiple scales.
Community detection is a significant and challenging task in network research. Nowadays, plenty of attention has been focused on local methods of community detection. Among them, community detection with a greedy algorithm typically starts from the identification of local essential nodes called central nodes of the network; communities expand later from these central nodes by optimizing a modularity function. In this paper, we propose a new central node indicator and a new modularity function. Our central node indicator, which we call local centrality indicator (LCI), is as efficient as the well-known global maximal degree indicator and local maximal degree indicator; on certain special network structure, LCI performs even better. On the other hand, our modularity function F2 overcomes certain disadvantages,such as the resolution limit problem,of the modularity functions raised in previous literature. Combined with a greedy algorithm, LCI and F2 enable us to identify the right community structures for both the real world networks and the simulated benchmark network. Evaluation based on the normalized mutual information (NMI) suggests that our community detection method with a greedy algorithm based on LCI and F2 performs superior to many other methods. Therefore, the method we proposed in this paper is potentially noteworthy.
Community detection is crucial for analyzing social and biological networks, and comprehensive approaches have been proposed in the last two decades. Nevertheless, finding all overlapping communities in large networks that could accurately approximate the ground-truth communities remains challenging. In this work, we present the QOCE (Quadratic Optimization based Clique Expansion), an overlapping community detection algorithm that could scale to large networks with hundreds of thousands of nodes and millions of edges. QOCE follows the popular seed set expansion strategy, regarding each high-quality maximal clique as the initial seed set and applying quadratic optimization for the expansion. We extensively evaluate our algorithm on 28 synthetic LFR networks and six real-world networks of various domains and scales, and compare QOCE with four state-of-the-art overlapping community detection algorithms. Empirical results demonstrate the competitive performance of the proposed approach in terms of detection accuracy, efficiency, and scalability.
Modularity based community detection encompasses a number of widely used, efficient heuristics for identification of structure in networks. Recently, a belief propagation approach to modularity optimization provided a useful guide for identifying non-trivial structure in single-layer networks in a way that other optimization heuristics have not. In this paper, we extend modularity belief propagation to multilayer networks. As part of this development, we also directly incorporate a resolution parameter. We show that adjusting the resolution parameter affects the convergence properties of the algorithm and yields different community structures than the baseline. We compare our approach with a widely used community detection tool, GenLouvain, across a range of synthetic, multilayer benchmark networks, demonstrating that our method performs comparably to the state of the art. Finally, we demonstrate the practical advantages of the additional information provided by our tool by way of two real-world network examples. We show how the convergence properties of the algorithm can be used in selecting the appropriate resolution and coupling parameters and how the node-level marginals provide an interpretation for the strength of attachment to the identified communities. We have released our tool as a Python package for convenient use.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
