ML p(r)ior | Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits

Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits

2016-02-02
1602.01016 | cs.SI
Many social networks and complex systems are found to be naturally divided into clusters of densely connected nodes, known as community structure (CS). Finding CS is one of fundamental yet challenging topics in network science. One of the most popular classes of methods for this problem is to maximize Newman's modularity. However, there is a little understood on how well we can approximate the maximum modularity as well as the implications of finding community structure with provable guarantees. In this paper, we settle definitely the approximability of modularity clustering, proving that approximating the problem within any (multiplicative) positive factor is intractable, unless P = NP. Yet we propose the first additive approximation algorithm for modularity clustering with a constant factor. Moreover, we provide a rigorous proof that a CS with modularity arbitrary close to maximum modularity QOPT might bear no similarity to the optimal CS of maximum modularity. Thus even when CS with near-optimal modularity are found, other verification methods are needed to confirm the significance of the structure.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2018-12-14

Discovering community structure in complex networks is a mature field since a tremendous number of c… show more
PDF

Highlights - Most important sentences from the article

2017-10-18
1710.06611 | stat.AP

Community structure is a commonly observed feature of real networks. The term refers to the presence… show more
PDF

Highlights - Most important sentences from the article

2019-04-09

Mining community structures from the complex network is an important problem across a variety of fie… show more
PDF

Highlights - Most important sentences from the article

2017-12-15
1712.05825 | cs.DS

Graph clustering, or community detection, is the task of identifying groups of closely related objec… show more
PDF

Highlights - Most important sentences from the article

2018-01-23
1801.07783 | cs.SI

Network structures, consisting of nodes and edges, have applications in almost all subjects. A set o… show more
PDF

Highlights - Most important sentences from the article

2017-08-18

Revealing a community structure in a network or dataset is a central problem arising in many scienti… show more
PDF

Highlights - Most important sentences from the article

2016-07-30
1608.00163 | physics.soc-ph

Community detection in networks is one of the most popular topics of modern network science. Communi… show more
PDF

Highlights - Most important sentences from the article

2015-03-02
1503.00445 | physics.soc-ph

Nodes in real-world networks are repeatedly observed to form dense clusters, often referred to as co… show more
PDF

Highlights - Most important sentences from the article

2017-08-22
1708.06810 | physics.soc-ph

Modularity, since its introduction, has remained one of the most widely used metrics to assess the q… show more
PDF

Highlights - Most important sentences from the article

2013-08-05

Networks (or graphs) appear as dominant structures in diverse domains, including sociology, biology,… show more
PDF

Highlights - Most important sentences from the article

2012-08-27
1208.5464 | cs.IR

The Web is a typical example of a social network. One of the most intriguing features of the Web is … show more
PDF

Highlights - Most important sentences from the article

2013-09-24

This paper presents a novel meta algorithm, Partition-Merge (PM), which takes existing centralized a… show more
PDF

Highlights - Most important sentences from the article

2015-02-11

The Euclidean $k$-means problem is a classical problem that has been extensively studied in the theo… show more
PDF

Highlights - Most important sentences from the article

2017-02-13

This paper focuses on the identification of overlapping communities, allowing nodes to simultaneousl… show more
PDF

Highlights - Most important sentences from the article

2012-07-18

In this work we present a new methodology to study the structure of the configuration spaces of hard… show more
PDF

Highlights - Most important sentences from the article

2012-04-04
1204.1002 | cs.DS

Nowadays, networks are almost ubiquitous. In the past decade, community detection received an increa… show more
PDF

Highlights - Most important sentences from the article