Brandes, Ulrik and Delling, Daniel and Gaertler, Marco and Görke, Robert and Hoefer, Martin and Nikoloski, Zoran and Wagner, Dorothea
Brandstädt, Andreas and Kratsch, Dieter and Müller, Haiko
On Finding Graph Clusterings with Maximum Modularity
Graph-Theoretic Concepts in Computer Science
Springer
2007
4769
121-132
Lecture Notes in Computer Science
Berlin / Heidelberg
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.
http://dx.doi.org/10.1007/978-3-540-74839-7_12
10.1007/978-3-540-74839-7_12
clustering, graph, modularity, theory
Abstract - SpringerLink
Schmitz, Christoph and Hotho, Andreas and Jäschke, Robert and Stumme, Gerd
Sure, York and Domingue, John
Content Aggregation on Knowledge Bases using Graph Clustering
The Semantic Web: Research and Applications
Springer
2006
4011
530-544
LNAI
Heidelberg
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.
http://www.kde.cs.uni-kassel.de/stumme/papers/2006/schmitz2006content.pdf
2006, aggregation, clustering, content, graph, itegpub, l3s, myown, nepomuk, ontologies, ontology, seminar2006, theory
Schmitz, Christoph and Hotho, Andreas and J\"aschke, Robert and Stumme, Gerd
Content Aggregation on Knowledge Bases using Graph Clustering
Proceedings of the 3rd European Semantic Web Conference
Springer
2006
4011
June
530-544
LNCS
Budva, Montenegro
http://www.kde.cs.uni-kassel.de/hotho/pub/2006/schmitz2006sumarize_eswc.pdf
2006, aggregation, clustering, content, graph, myown, ontology, theory
Schmitz, Christoph and Hotho, Andreas and Jäschke, Robert and Stumme, Gerd
Sure, York and Domingue, John
Content Aggregation on Knowledge Bases using Graph Clustering
The Semantic Web: Research and Applications
Springer
2006
4011
530-544
LNAI
Heidelberg
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.
http://www.kde.cs.uni-kassel.de/stumme/papers/2006/schmitz2006content.pdf
2006, aggregation, clustering, content, graph, itegpub, l3s, myown, nepomuk, ontologies, ontology, seminar2006, theory
Dhillon, I. S. and Mallela, S. and Modha, D. S.
Information-Theoretic Co-Clustering
Proceedings of The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD-2003)
2003
89–98
/brokenurl#citeseer.ist.psu.edu/dhillon03informationtheoretic.html
clustering, co-clustering, dhillon, information, theory, toread
Newman, M. E. J.
The structure and function of complex networks
2003
March
Inspired by empirical studies of networked systems such as the Internet,
social networks, and biological networks, researchers have in recent years
developed a variety of techniques and models to help us understand or predict
the behavior of these systems. Here we review developments in this field,
including such concepts as the small-world effect, degree distributions,
clustering, network correlations, random graph models, models of network growth
and preferential attachment, and dynamical processes taking place on networks.
http://arxiv.org/abs/cond-mat/0303516
algorithm, clustering, complex_systems, folksonomy, information, kdubiq, network, retrieval, scale_free_networks, small, socialnetwork, summerschool, theory, web, web_graph, world
Ng, Andrew Y. and Jordan, Michael I. and Weiss, Yair
On spectral clustering: Analysis and an algorithm
Advances in Neural Information Processing Systems 14
MIT Press
2001
849–856
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
clustering, community, detection, graph, spectral, theory
Ranade, A.G.
Some uses of spectral methods
2000
clustering, graph, spectral, svd, theory
Spielman, Daniel A. and Teng, Shang
Spectral Partitioning Works: Planar Graphs and Finite Element Meshes
University of California at Berkeley
1996
Berkeley, CA, USA
clustering, community, detection, graph, spectral, survey, theory
Pothen, A. and Simon, H.D. and Liou, K.P.
Partitioning Sparse Matrices with Eigenvectors of Graphs
SIAM J. MATRIX ANAL. APPLIC.
1990
11
430–452
3
http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970011963_1997016998.pdf
clustering, community, graph, partitioning, spectral, theory
Donath, W.E. and Hoffman, A.J.
Lower bounds for the partitioning of graphs
IBM Journal of Research and Development
1973
17
420–425
5
clustering, community, detection, graph, spectral, theory