Loading...
Please wait, while we are loading the content...
Similar Documents
Summary : Modularity and Community Structure in Networks
| Content Provider | Semantic Scholar |
|---|---|
| Author | Newman, Mark E. J. |
| Abstract | Main Point: Newman defines the modularity of a graph partitioning as the difference between the number of edges within the partitions found and the number of expected edges in these partitions if the network were produced by placing edges at random between vertices of an equivalent degree distribution. He argues that optimizing modularity is a better approach for community detection than partitional approaches useful to other domains such as load balancing in parallel computing, because we do not know the number of communities present in a network, nor their sizes, in advance. He then describes a spectral method for modularity maximization that shows that finding the principal eigenvector of what he calls the modularity matrix is enough to maximize the modularity of a bisection of any given network, and proves further that a recursive application of this method to the partitions of a network will naturally lead to the number of divisions giving the maximum modularity. Newman shows several experimental results on real networks of up to 27, 000 vertices validating that the communities found by maximizing modularity are meaningful and that the spectral method for modularity maximization outperforms previously attempted approaches. Newman begins by pointing out the difference between partitioning methods useful for applications such as load balancing in parallel computing, where we seek to partition a graph into a set number of partitions with the goal of minimizing the number of edges that cross partitions, and the goal in community detection, where we do not automatically assume that good partitions exist, but we would like to discover any that do. Community detection is therefore more exploratory and algorithms designed for this purpose need not output any communities at all if they do not exist in a network, and they shouldn't look for a fixed number of communities nor seek communities of a fixed size. Newman goes on to explain that modularity is a concept very useful for community detection. By dividing a network into groups of maximal modularity, we are partitioning it in such a way that maximizes our " surprise " at seeing such groups in a random graph. The modularity of a partition is defined as the number of edges falling within partitions minus the expected number of edges in an equivalent (same number of vertices) network with edges placed at random, with a multiplicative constant. Suppose a network has a set of n vertices V … |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.ucsb.edu/~veronika/MAE/summary_modularitycommunitystructure_newman.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
