Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts, and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomaration approach.

@incollection{springerlink:10.1007/978-3-540-74839-7_12, author = {Brandes, Ulrik and Delling, Daniel and Gaertler, Marco and Görke, Robert and Hoefer, Martin and Nikoloski, Zoran and Wagner, Dorothea}, title = {On Finding Graph Clusterings with Maximum Modularity}, editor = {Brandstädt, Andreas and Kratsch, Dieter and Müller, Haiko}, booktitle = {Graph-Theoretic Concepts in Computer Science}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, address = {Berlin / Heidelberg}, year = {2007}, volume = {4769}, pages = {121-132}, url = {http://dx.doi.org/10.1007/978-3-540-74839-7_12}, doi = {10.1007/978-3-540-74839-7_12}, isbn = {978-3-540-74838-0}, keywords = {clustering, graph, modularity, theory}, abstract = {Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts, and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomaration approach.} }

%0 = incollection %A = Brandes, Ulrik and Delling, Daniel and Gaertler, Marco and Görke, Robert and Hoefer, Martin and Nikoloski, Zoran and Wagner, Dorothea %B = Graph-Theoretic Concepts in Computer Science %C = Berlin / Heidelberg %D = 2007 %I = Springer %T = On Finding Graph Clusterings with Maximum Modularity %U = http://dx.doi.org/10.1007/978-3-540-74839-7_12

@article{newman2006fcs, author = {Newman, MEJ}, title = {Finding community structure in networks using the eigenvectors of matrices}, journal = {Physical Review E}, publisher = {APS}, year = {2006}, volume = {74}, number = {3}, pages = {36104}, keywords = {community, detection, graph, modularity, spectral, theory} }

%0 = article %A = Newman, MEJ %D = 2006 %I = APS %T = Finding community structure in networks using the eigenvectors of matrices

Recently, research projects such as PADLR and SWAP
have developed tools like Edutella or Bibster, which are targeted at
establishing peer-to-peer knowledge management (P2PKM) systems. In
such a system, it is necessary to obtain provide brief semantic
descriptions of peers, so that routing algorithms or matchmaking
processes can make decisions about which communities peers should
belong to, or to which peers a given query should be forwarded.
This paper provides a graph clustering technique on
knowledge bases for that purpose. Using this clustering, we can show
that our strategy requires up to 58% fewer queries than the
baselines to yield full recall in a bibliographic P2PKM scenario.

@inproceedings{schmitz2006content, author = {Schmitz, Christoph and Hotho, Andreas and Jäschke, Robert and Stumme, Gerd}, title = {Content Aggregation on Knowledge Bases using Graph Clustering}, editor = {Sure, York and Domingue, John}, booktitle = {The Semantic Web: Research and Applications}, series = {LNAI}, publisher = {Springer}, address = {Heidelberg}, year = {2006}, volume = {4011}, pages = {530-544}, url = {http://www.kde.cs.uni-kassel.de/stumme/papers/2006/schmitz2006content.pdf}, keywords = {2006, aggregation, clustering, content, graph, itegpub, l3s, myown, nepomuk, ontologies, ontology, seminar2006, theory}, abstract = {Recently, research projects such as PADLR and SWAP
have developed tools like Edutella or Bibster, which are targeted at
establishing peer-to-peer knowledge management (P2PKM) systems. In
such a system, it is necessary to obtain provide brief semantic
descriptions of peers, so that routing algorithms or matchmaking
processes can make decisions about which communities peers should
belong to, or to which peers a given query should be forwarded.
This paper provides a graph clustering technique on
knowledge bases for that purpose. Using this clustering, we can show
that our strategy requires up to 58% fewer queries than the
baselines to yield full recall in a bibliographic P2PKM scenario.} }

%0 = inproceedings %A = Schmitz, Christoph and Hotho, Andreas and Jäschke, Robert and Stumme, Gerd %B = The Semantic Web: Research and Applications %C = Heidelberg %D = 2006 %I = Springer %T = Content Aggregation on Knowledge Bases using Graph Clustering %U = http://www.kde.cs.uni-kassel.de/stumme/papers/2006/schmitz2006content.pdf

@book{diestel2006graphentheorie, author = {Diestel, Reinhard}, title = {Graph Theory}, publisher = {Springer-Verlag Heidelberg, New York}, year = {2005}, pages = {I-XVI, 1-344}, edition = {3 (electronic edition)}, url = {http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf}, keywords = {book, density, diesel, graph, theory} }

%0 = book %A = Diestel, Reinhard %D = 2005 %I = Springer-Verlag Heidelberg, New York %T = Graph Theory %U = http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf

@book{Chung:1997, author = {Chung, F. R. K.}, title = {Spectral Graph Theory}, publisher = {American Mathematical Society}, year = {1997}, keywords = {graph, spectral, theory} }

%0 = book %A = Chung, F. R. K. %D = 1997 %I = American Mathematical Society %T = Spectral Graph Theory