Newman, M.
(2006):
Finding community structure in networks using the eigenvectors of matrices.
In: Physical Review E,
Ausgabe/Number: 3,
Vol. 74,
Verlag/Publisher: APS.
Erscheinungsjahr/Year: 2006.
Seiten/Pages: 36104.
[BibTeX]
[Endnote]
@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
Chung, F. R. K. (Hrsg.)
(1997):
Spectral Graph Theory.
Erscheinungsjahr/Year: 1997.
Verlag/Publisher: American Mathematical Society,
[BibTeX]
[Endnote]
@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
Monien, B.
(2001):
On Spectral Bounds for the k-Partitioning of Graphs.
[BibTeX]
[Endnote]
@misc{Monien_onspectral,
author = {Monien, B.},
title = {On Spectral Bounds for the k-Partitioning of Graphs},
year = {2001},
keywords = {graph, spectral, theory}
}
%0 = misc
%A = Monien, B.
%D = 2001
%T = On Spectral Bounds for the k-Partitioning of Graphs
Mohar, B.
(1991):
The Laplacian spectrum of graphs.
In: Graph Theory, Combinatorics, and Applications,
Vol. 2,
Verlag/Publisher: New York: Wiley.
Erscheinungsjahr/Year: 1991.
Seiten/Pages: 871-898.
[BibTeX]
[Endnote]
@article{mohar1991lsg,
author = {Mohar, B.},
title = {The Laplacian spectrum of graphs},
journal = {Graph Theory, Combinatorics, and Applications},
publisher = {New York: Wiley},
year = {1991},
volume = {2},
pages = {871--898},
keywords = {graph, laplacian, spectral, survey, theory}
}
%0 = article
%A = Mohar, B.
%D = 1991
%I = New York: Wiley
%T = The Laplacian spectrum of graphs
Spielman, D.
(2007):
Spectral Graph Theory and its Applications.
In: Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on,
Erscheinungsjahr/Year: 2007.
Seiten/Pages: 29-38.
[Kurzfassung] [BibTeX]
[Endnote]
Spectral graph theory is the study of the eigenvalues and eigenvectors of matrices associated with graphs. In this tutorial, we will try to provide some intuition as to why these eigenvectors and eigenvalues have combinatorial significance, and will sitn'ey some of their applications.
@article{4389477,
author = {Spielman, D.A.},
title = {Spectral Graph Theory and its Applications},
journal = {Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on},
year = {2007},
pages = {29-38},
doi = {10.1109/FOCS.2007.56},
issn = {0272-5428},
keywords = {graph, spectral, theory},
abstract = {Spectral graph theory is the study of the eigenvalues and eigenvectors of matrices associated with graphs. In this tutorial, we will try to provide some intuition as to why these eigenvectors and eigenvalues have combinatorial significance, and will sitn'ey some of their applications.}
}
%0 = article
%A = Spielman, D.A.
%D = 2007
%T = Spectral Graph Theory and its Applications
Johnson, D. S. & Papadimitriou, C. H.
(1988):
On generating all maximal independent sets.
In: Inf. Process. Lett.,
Ausgabe/Number: 3,
Vol. 27,
Verlag/Publisher: Elsevier North-Holland, Inc..
Erscheinungsjahr/Year: 1988.
Seiten/Pages: 119-123.
[Volltext] [BibTeX]
[Endnote]
@article{46243,
author = {Johnson, David S. and Papadimitriou, Christos H.},
title = {On generating all maximal independent sets},
journal = {Inf. Process. Lett.},
publisher = {Elsevier North-Holland, Inc.},
address = {Amsterdam, The Netherlands, The Netherlands},
year = {1988},
volume = {27},
number = {3},
pages = {119--123},
url = {http://portal.acm.org/citation.cfm?id=46241.46243},
doi = {http://dx.doi.org/10.1016/0020-0190(88)90065-8},
issn = {0020-0190},
keywords = {complexity, graph, independent, sets, theory}
}
%0 = article
%A = Johnson, David S. and Papadimitriou, Christos H.
%C = Amsterdam, The Netherlands, The Netherlands
%D = 1988
%I = Elsevier North-Holland, Inc.
%T = On generating all maximal independent sets
%U = http://portal.acm.org/citation.cfm?id=46241.46243
Dias, V. M.; de Figueiredo, C. M. & Szwarcfiter, J. L.
(2005):
Generating bicliques of a graph in lexicographic order.
In: Theoretical Computer Science,
Ausgabe/Number: 1-3,
Vol. 337,
Erscheinungsjahr/Year: 2005.
Seiten/Pages: 240 - 248.
[Volltext] [Kurzfassung] [BibTeX]
[Endnote]
An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X[union or logical sum]Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y[not equal to][empty set], then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. We present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. We also show that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The methods are based on those by Johnson, Papadimitriou and Yannakakis, in the solution of these two problems for independent sets, instead of bicliques.
@article{Dias2005240,
author = {Dias, Vânia M.F. and de Figueiredo, Celina M.H. and Szwarcfiter, Jayme L.},
title = {Generating bicliques of a graph in lexicographic order},
journal = {Theoretical Computer Science},
year = {2005},
volume = {337},
number = {1-3},
pages = {240 - 248},
url = {http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280},
doi = {DOI: 10.1016/j.tcs.2005.01.014},
issn = {0304-3975},
keywords = {conp, graph, independent, set, theory},
abstract = {An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X[union or logical sum]Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y[not equal to][empty set], then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. We present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. We also show that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The methods are based on those by Johnson, Papadimitriou and Yannakakis, in the solution of these two problems for independent sets, instead of bicliques.}
}
%0 = article
%A = Dias, Vânia M.F. and de Figueiredo, Celina M.H. and Szwarcfiter, Jayme L.
%D = 2005
%T = Generating bicliques of a graph in lexicographic order
%U = http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280
Fiedler, M.
(1975):
A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory.
In: Czechoslovak Mathematical Journal,
Ausgabe/Number: 100,
Vol. 25,
Erscheinungsjahr/Year: 1975.
Seiten/Pages: 619-633.
[BibTeX]
[Endnote]
@article{fiedler1975pen,
author = {Fiedler, M.},
title = {A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory},
journal = {Czechoslovak Mathematical Journal},
year = {1975},
volume = {25},
number = {100},
pages = {619--633},
keywords = {graph, spectral, theory}
}
%0 = article
%A = Fiedler, M.
%D = 1975
%T = A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory
Haveliwala, T. & Kamvar, S.
(2003):
The second eigenvalue of the Google matrix.
In: A Stanford University Technical Report http://dbpubs. stanford. edu,
Erscheinungsjahr/Year: 2003.
[BibTeX]
[Endnote]
@article{haveliwala8090seg,
author = {Haveliwala, T.H. and Kamvar, S.D.},
title = {The second eigenvalue of the Google matrix},
journal = {A Stanford University Technical Report http://dbpubs. stanford. edu},
year = {2003},
keywords = {graph, pagerank, spectral, theory}
}
%0 = article
%A = Haveliwala, T.H. and Kamvar, S.D.
%D = 2003
%T = The second eigenvalue of the Google matrix
Dhillon, I. S.
(2001):
Co-clustering documents and words using bipartite spectral graph partitioning.
In: KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining,
New York, NY, USA.
[Volltext]
[BibTeX][Endnote]
@inproceedings{coclustering01,
author = {Dhillon, Inderjit S.},
title = {Co-clustering documents and words using bipartite spectral graph partitioning},
booktitle = {KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining},
publisher = {ACM Press},
address = {New York, NY, USA},
year = {2001},
pages = {269--274},
url = {http://portal.acm.org/citation.cfm?id=502512.502550},
doi = {10.1145/502512.502550},
isbn = {158113391X},
keywords = {community, detection, graph, spectral, theory}
}
%0 = inproceedings
%A = Dhillon, Inderjit S.
%B = KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining
%C = New York, NY, USA
%D = 2001
%I = ACM Press
%T = Co-clustering documents and words using bipartite spectral graph partitioning
%U = http://portal.acm.org/citation.cfm?id=502512.502550
Blelloch, G.
(2002):
Graph Separators.
[BibTeX]
[Endnote]
@unpublished{graphseparators02,
author = {Blelloch, Guy},
title = {Graph Separators},
year = {2002},
keywords = {graph, separators, theory}
}
%0 = unpublished
%A = Blelloch, Guy
%D = 2002
%T = Graph Separators
Pothen, A.; Simon, H. & Liou, K.
(1990):
Partitioning Sparse Matrices with Eigenvectors of Graphs.
In: SIAM J. MATRIX ANAL. APPLIC.,
Ausgabe/Number: 3,
Vol. 11,
Erscheinungsjahr/Year: 1990.
Seiten/Pages: 430-452.
[Volltext] [BibTeX]
[Endnote]
@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
Chan, P. K.; Schlag, M. D. F. & Zien, J. Y.
(1994):
Spectral K-way ratio-cut partitioning and clustering..
In: IEEE Trans. on CAD of Integrated Circuits and Systems,
Ausgabe/Number: 9,
Vol. 13,
Erscheinungsjahr/Year: 1994.
Seiten/Pages: 1088-1096.
[Volltext] [BibTeX]
[Endnote]
@article{journals/tcad/ChanSZ94,
author = {Chan, Pak K. and Schlag, Martine D. F. and Zien, Jason Y.},
title = {Spectral K-way ratio-cut partitioning and clustering.},
journal = {IEEE Trans. on CAD of Integrated Circuits and Systems},
year = {1994},
volume = {13},
number = {9},
pages = {1088-1096},
url = {http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94},
keywords = {community, detection, graph, partitioning, spectral, theory}
}
%0 = article
%A = Chan, Pak K. and Schlag, Martine D. F. and Zien, Jason Y.
%D = 1994
%T = Spectral K-way ratio-cut partitioning and clustering.
%U = http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94
Yu, S. X. & Shi, J.
(2003):
Multiclass Spectral Clustering.
In: Proc. International Conference on Computer Vision (ICCV 03),
Nice, France.
[BibTeX][Endnote]
@inproceedings{yu2003multiclass,
author = {Yu, Stella X. and Shi, Jianbo},
title = {Multiclass Spectral Clustering},
booktitle = {Proc. International Conference on Computer Vision (ICCV 03)},
address = {Nice, France},
year = {2003},
keywords = {Spectral, graph, partitioning, theory}
}
%0 = inproceedings
%A = Yu, Stella X. and Shi, Jianbo
%B = Proc. International Conference on Computer Vision (ICCV 03)
%C = Nice, France
%D = 2003
%T = Multiclass Spectral Clustering
Hagen, L. W. & Kahng, A. B.
(1992):
New spectral methods for ratio cut partitioning and clustering..
In: IEEE Trans. on CAD of Integrated Circuits and Systems,
Ausgabe/Number: 9,
Vol. 11,
Erscheinungsjahr/Year: 1992.
Seiten/Pages: 1074-1085.
[Volltext] [BibTeX]
[Endnote]
@article{journals/tcad/HagenK92,
author = {Hagen, Lars W. and Kahng, Andrew B.},
title = {New spectral methods for ratio cut partitioning and clustering.},
journal = {IEEE Trans. on CAD of Integrated Circuits and Systems},
year = {1992},
volume = {11},
number = {9},
pages = {1074-1085},
url = {http://dblp.uni-trier.de/db/journals/tcad/tcad11.html#HagenK92},
keywords = {graph, partitioning, spectral, theory}
}
%0 = article
%A = Hagen, Lars W. and Kahng, Andrew B.
%D = 1992
%T = New spectral methods for ratio cut partitioning and clustering.
%U = http://dblp.uni-trier.de/db/journals/tcad/tcad11.html#HagenK92
Symeonidis, P.; Nanopoulos, A. & Manolopoulos, Y.
(2008):
Tag recommendations based on tensor dimensionality reduction.
In: RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems,
New York, NY, USA.
[Volltext]
[BibTeX][Endnote]
@inproceedings{1454017,
author = {Symeonidis, Panagiotis and Nanopoulos, Alexandros and Manolopoulos, Yannis},
title = {Tag recommendations based on tensor dimensionality reduction},
booktitle = {RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems},
publisher = {ACM},
address = {New York, NY, USA},
year = {2008},
pages = {43--50},
url = {http://portal.acm.org/citation.cfm?id=1454017},
doi = {http://doi.acm.org/10.1145/1454008.1454017},
isbn = {978-1-60558-093-7},
keywords = {community, detection, graph, recommender, spectral, tag, theory}
}
%0 = inproceedings
%A = Symeonidis, Panagiotis and Nanopoulos, Alexandros and Manolopoulos, Yannis
%B = RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems
%C = New York, NY, USA
%D = 2008
%I = ACM
%T = Tag recommendations based on tensor dimensionality reduction
%U = http://portal.acm.org/citation.cfm?id=1454017
Ranade, A.
(2000):
Some uses of spectral methods.
[BibTeX]
[Endnote]
@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
Schmitz, C.; Hotho, A.; Jäschke, R. & Stumme, G.
(2006):
Content Aggregation on Knowledge Bases using Graph Clustering.
In: The Semantic Web: Research and Applications,
Heidelberg.
[Volltext]
[Kurzfassung] [BibTeX][Endnote]
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
Brandes, U.; Delling, D.; Gaertler, M.; Görke, R.; Hoefer, M.; Nikoloski, Z. & Wagner, D.
(2007):
On Finding Graph Clusterings with Maximum Modularity.
In: Graph-Theoretic Concepts in Computer Science.
4769. Aufl./Vol..
Hrsg./Editors: Brandstädt, A.; Kratsch, D. & Müller, H.
Verlag/Publisher: Springer,
Berlin / Heidelberg.
Erscheinungsjahr/Year: 2007.
Seiten/Pages: 121-132.
[Volltext] [Kurzfassung] [BibTeX]
[Endnote]
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
Diestel, R. (Hrsg.)
(2005):
Graph Theory.
3 (electronic edition). Aufl./Vol..
Erscheinungsjahr/Year: 2005.
Verlag/Publisher: Springer-Verlag Heidelberg, New York,
[Volltext] [BibTeX]
[Endnote]
@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