Modularity

In graph mining the concept of dividing the nodes of a network into groups or communities as part of a clustering exercise is also called modularity. How well graph generators preserve modularity?

Introduction

Related Work

Methods

Communities in Networks

  • Modularity maximization and Maximum Likelihood
  • Statistical Infrerence
  • Degree-correlated block model

Community formation detection

Identifiying communities may offer insight on how the network is organized.

  • vertices
  • graph partitioning

Overlapping Communitites

It is not unusual for communities to overlap at their boundaries.

Finding cliques is an NP-complete problem (Bomze et al., 1999); a popular technique is the Bron–Kerbosch method (Bron and Kerbosch, 1973).

Planted Partition Model and Modularity Maximization

  • Value of the resolution Parameter

Q = 1/m (12 Sum_ij (A_ij - Pij)\delta gigj

Links and References

Working with Networks by kateto

Python

http://stackoverflow.com/questions/24255143/graph-theory-in-networkx http://stackoverflow.com/questions/29897243/graph-modularity-in-python-networkx

C and R

http://www.sixhat.net/finding-communities-in-networks-with-r-and-igraph.html

http://igraph.org/r/doc/modularity.igraph.html

References

comments powered by Disqus