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

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

@inproceedings{schmitz2006content, author = {Schmitz, Christoph and Hotho, Andreas and Jäschke, Robert and Stumme, Gerd}, title = {Content Aggregation on Knowledge Bases using Graph Clustering}, booktitle = {Proceedings of the 3rd European Semantic Web Conference}, series = {LNCS}, publisher = {Springer}, address = {Budva, Montenegro}, year = {2006}, volume = {4011}, pages = {530-544}, url = {http://www.kde.cs.uni-kassel.de/hotho/pub/2006/schmitz2006sumarize_eswc.pdf}, isbn = {3-540-34544-2}, keywords = {2006, aggregation, clustering, content, graph, myown, ontology, theory} }

%0 = inproceedings %A = Schmitz, Christoph and Hotho, Andreas and Jäschke, Robert and Stumme, Gerd %B = Proceedings of the 3rd European Semantic Web Conference %C = Budva, Montenegro %D = 2006 %I = Springer %T = Content Aggregation on Knowledge Bases using Graph Clustering %U = http://www.kde.cs.uni-kassel.de/hotho/pub/2006/schmitz2006sumarize_eswc.pdf

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

@inproceedings{dhillon:mallela:modha:03, author = {Dhillon, I. S. and Mallela, S. and Modha, D. S.}, title = {Information-Theoretic Co-Clustering}, booktitle = {Proceedings of The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD-2003)}, year = {2003}, pages = {89--98}, url = {/brokenurl#citeseer.ist.psu.edu/dhillon03informationtheoretic.html}, keywords = {clustering, co-clustering, dhillon, information, theory, toread} }

%0 = inproceedings %A = Dhillon, I. S. and Mallela, S. and Modha, D. S. %B = Proceedings of The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD-2003) %D = 2003 %T = Information-Theoretic Co-Clustering %U = /brokenurl#citeseer.ist.psu.edu/dhillon03informationtheoretic.html

Inspired by empirical studies of networked systems such as the Internet,
cial networks, and biological networks, researchers have in recent years
veloped a variety of techniques and models to help us understand or predict
e behavior of these systems. Here we review developments in this field,
cluding such concepts as the small-world effect, degree distributions,
ustering, network correlations, random graph models, models of network growth
d preferential attachment, and dynamical processes taking place on networks.

@misc{citeulike:155, author = {Newman, M. E. J.}, title = {The structure and function of complex networks}, year = {2003}, url = {http://arxiv.org/abs/cond-mat/0303516}, keywords = {algorithm, clustering, complex_systems, folksonomy, information, kdubiq, network, retrieval, scale_free_networks, small, socialnetwork, summerschool, theory, web, web_graph, world}, abstract = {Inspired by empirical studies of networked systems such as the Internet,
cial networks, and biological networks, researchers have in recent years
veloped a variety of techniques and models to help us understand or predict
e behavior of these systems. Here we review developments in this field,
cluding such concepts as the small-world effect, degree distributions,
ustering, network correlations, random graph models, models of network growth
d preferential attachment, and dynamical processes taking place on networks.} }

%0 = misc %A = Newman, M. E. J. %D = 2003 %T = The structure and function of complex networks %U = http://arxiv.org/abs/cond-mat/0303516

Despite many empirical successes of spectral clustering methods| algorithms that cluster points using eigenvectors of matrices derived from the data|there are several unresolved issues. First, there are a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1

@inproceedings{Ng01onspectral, author = {Ng, Andrew Y. and Jordan, Michael I. and Weiss, Yair}, title = {On spectral clustering: Analysis and an algorithm}, booktitle = {Advances in Neural Information Processing Systems 14}, publisher = {MIT Press}, year = {2001}, pages = {849--856}, keywords = {clustering, community, detection, graph, spectral, theory}, abstract = {Despite many empirical successes of spectral clustering methods| algorithms that cluster points using eigenvectors of matrices derived from the data|there are several unresolved issues. First, there are a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1} }

%0 = inproceedings %A = Ng, Andrew Y. and Jordan, Michael I. and Weiss, Yair %B = Advances in Neural Information Processing Systems 14 %D = 2001 %I = MIT Press %T = On spectral clustering: Analysis and an algorithm

@unpublished{ranade:sus, author = {Ranade, A.G.}, title = {Some uses of spectral methods}, year = {2000}, keywords = {clustering, graph, spectral, svd, theory} }

%0 = unpublished %A = Ranade, A.G. %D = 2000 %T = Some uses of spectral methods

@techreport{Spielman:1996, author = {Spielman, Daniel A. and Teng, Shang}, title = {Spectral Partitioning Works: Planar Graphs and Finite Element Meshes}, publisher = {University of California at Berkeley}, address = {Berkeley, CA, USA}, year = {1996}, keywords = {clustering, community, detection, graph, spectral, survey, theory} }

%0 = techreport %A = Spielman, Daniel A. and Teng, Shang %C = Berkeley, CA, USA %D = 1996 %I = University of California at Berkeley %T = Spectral Partitioning Works: Planar Graphs and Finite Element Meshes

@article{partitioning89, author = {Pothen, A. and Simon, H.D. and Liou, K.P.}, title = {Partitioning Sparse Matrices with Eigenvectors of Graphs}, journal = {SIAM J. MATRIX ANAL. APPLIC.}, year = {1990}, volume = {11}, number = {3}, pages = {430--452}, url = {http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970011963_1997016998.pdf }, keywords = {clustering, community, graph, partitioning, spectral, theory} }

%0 = article %A = Pothen, A. and Simon, H.D. and Liou, K.P. %D = 1990 %T = Partitioning Sparse Matrices with Eigenvectors of Graphs %U = http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970011963_1997016998.pdf

@article{donath1973lbp, author = {Donath, W.E. and Hoffman, A.J.}, title = {Lower bounds for the partitioning of graphs}, journal = {IBM Journal of Research and Development}, year = {1973}, volume = {17}, number = {5}, pages = {420--425}, keywords = {clustering, community, detection, graph, spectral, theory} }

%0 = article %A = Donath, W.E. and Hoffman, A.J. %D = 1973 %T = Lower bounds for the partitioning of graphs