ID: 1606.02319

Community detection in networks: Modularity optimization and maximum likelihood are equivalent

June 7, 2016

View on ArXiv

Similar papers 2

Consistency of community structure in complex networks

August 26, 2019

90% Match
Maria A. Riolo, M. E. J. Newman
Social and Information Netwo...
Physics and Society

The most widely used techniques for community detection in networks, including methods based on modularity, statistical inference, and information theoretic arguments, all work by optimizing objective functions that measure the quality of network partitions. There is a good case to be made, however, that one should not look solely at the single optimal community structure under such an objective function, but rather at a selection of high-scoring structures. If one does this ...

Find SimilarView on arXiv

Modularity and community structure in networks

February 17, 2006

90% Match
M. E. J. Newman
Data Analysis, Statistics an...
Statistical Mechanics
Physics and Society

Many networks of interest in the sciences, including a variety of social and biological networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure has attracted considerable recent attention. One of the most sensitive detection methods is optimization of the quality function known as "modularity" over the possible divisions of a network, but direct application of this method using, for instance, si...

Find SimilarView on arXiv

An efficient and principled method for detecting communities in networks

April 18, 2011

90% Match
Brian Ball, Brian Karrer, M. E. J. Newman
Social and Information Netwo...
Statistical Mechanics
Physics and Society

A fundamental problem in the analysis of network data is the detection of network communities, groups of densely interconnected nodes, which may be overlapping or disjoint. Here we describe a method for finding overlapping communities based on a principled statistical approach using generative network models. We show how the method can be implemented using a fast, closed-form expectation-maximization algorithm that allows us to analyze networks of millions of nodes in reasona...

Find SimilarView on arXiv

Combinatorial approach to Modularity

April 29, 2010

90% Match
Filippo Radicchi, Andrea Lancichinetti, José J. Ramasco
Physics and Society
Statistical Mechanics

Communities are clusters of nodes with a higher than average density of internal connections. Their detection is of great relevance to better understand the structure and hierarchies present in a network. Modularity has become a standard tool in the area of community detection, providing at the same time a way to evaluate partitions and, by maximizing it, a method to find communities. In this work, we study the modularity from a combinatorial point of view. Our analysis (as t...

Find SimilarView on arXiv

Optimality Of Community Structure In Complex Networks

December 14, 2017

90% Match
Stanislav Sobolevsky, Alexander Belyi, Carlo Ratti
Social and Information Netwo...
Data Analysis, Statistics an...
Physics and Society

Community detection is one of the pivotal tools for discovering the structure of complex networks. Majority of community detection methods rely on optimization of certain quality functions characterizing the proposed community structure. Perhaps, the most commonly used of those quality functions is modularity. Many heuristics are claimed to be efficient in modularity maximization, which is usually justified in relative terms through comparison of their outcomes with those pro...

Find SimilarView on arXiv

Quality functions in community detection

May 30, 2007

90% Match
Santo Fortunato
Physics and Society

Community structure represents the local organization of complex networks and the single most important feature to extract functional relationships between nodes. In the last years, the problem of community detection has been reformulated in terms of the optimization of a function, the Newman-Girvan modularity, that is supposed to express the quality of the partitions of a network into communities. Starting from a recent critical survey on modularity optimization, pointing ou...

Find SimilarView on arXiv

A New Metric for Quality of Network Community Structure

July 15, 2015

90% Match
Mingming Chen, Tommy Nguyen, Boleslaw K. Szymanski
Social and Information Netwo...
Physics and Society

Modularity is widely used to effectively measure the strength of the community structure found by community detection algorithms. However, modularity maximization suffers from two opposite yet coexisting problems: in some cases, it tends to favor small communities over large ones while in others, large communities over small ones. The latter tendency is known in the literature as the resolution limit problem. To address them, we propose to modify modularity by subtracting fro...

Find SimilarView on arXiv

An upper bound on community size in scalable community detection

March 29, 2011

90% Match
Gautier Krings, Vincent D. Blondel
Physics and Society
Social and Information Netwo...

It is well-known that community detection methods based on modularity optimization often fails to discover small communities. Several objective functions used for community detection therefore involve a resolution parameter that allows the detection of communities at different scales. We provide an explicit upper bound on the community size of communities resulting from the optimization of several of these functions. We also show with a simple example that the use of the reso...

Find SimilarView on arXiv

A General Optimization Technique for High Quality Community Detection in Complex Networks

August 15, 2013

90% Match
Stanislav Sobolevsky, Riccardo Campari, ... , Ratti Carlo
Social and Information Netwo...
Physics and Society

Recent years have witnessed the development of a large body of algorithms for community detection in complex networks. Most of them are based upon the optimization of objective functions, among which modularity is the most common, though a number of alternatives have been suggested in the scientific literature. We present here an effective general search strategy for the optimization of various objective functions for community detection purposes. When applied to modularity, ...

Find SimilarView on arXiv

Spectral methods for network community detection and graph partitioning

July 29, 2013

90% Match
M. E. J. Newman
Physics and Society
Statistical Mechanics
Social and Information Netwo...
Data Analysis, Statistics an...

We consider three distinct and well studied problems concerning network structure: community detection by modularity maximization, community detection by statistical inference, and normalized-cut graph partitioning. Each of these problems can be tackled using spectral algorithms that make use of the eigenvectors of matrix representations of the network. We show that with certain choices of the free parameters appearing in these spectral algorithms the algorithms for all three...

Find SimilarView on arXiv