TY - CONF AU - Symeonidis, Panagiotis AU - Nanopoulos, Alexandros AU - Manolopoulos, Yannis A2 - T1 - Tag recommendations based on tensor dimensionality reduction T2 - RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems PB - ACM C1 - New York, NY, USA PY - 2008/ CY - VL - IS - SP - 43 EP - 50 UR - http://portal.acm.org/citation.cfm?id=1454017 DO - http://doi.acm.org/10.1145/1454008.1454017 KW - community KW - detection KW - graph KW - recommender KW - spectral KW - tag KW - theory L1 - SN - 978-1-60558-093-7 N1 - N1 - AB - ER - TY - CHAP AU - Brandes, Ulrik AU - Delling, Daniel AU - Gaertler, Marco AU - Görke, Robert AU - Hoefer, Martin AU - Nikoloski, Zoran AU - Wagner, Dorothea A2 - Brandstädt, Andreas A2 - Kratsch, Dieter A2 - Müller, Haiko T1 - On Finding Graph Clusterings with Maximum Modularity T2 - Graph-Theoretic Concepts in Computer Science PB - Springer C1 - Berlin / Heidelberg PY - 2007/ VL - 4769 IS - SP - 121 EP - 132 UR - http://dx.doi.org/10.1007/978-3-540-74839-7_12 DO - 10.1007/978-3-540-74839-7_12 KW - clustering KW - graph KW - modularity KW - theory L1 - SN - 978-3-540-74838-0 N1 - Abstract - SpringerLink N1 - AB - 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. ER - TY - JOUR AU - Spielman, D.A. T1 - Spectral Graph Theory and its Applications JO - Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on PY - 2007/oct. VL - IS - SP - 29 EP - 38 UR - DO - 10.1109/FOCS.2007.56 KW - graph KW - spectral KW - theory L1 - SN - N1 - N1 - AB - 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. ER - TY - JOUR AU - Newman, MEJ T1 - Finding community structure in networks using the eigenvectors of matrices JO - Physical Review E PY - 2006/ VL - 74 IS - 3 SP - EP - UR - DO - KW - community KW - detection KW - graph KW - modularity KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - CONF AU - Schmitz, Christoph AU - Hotho, Andreas AU - Jäschke, Robert AU - Stumme, Gerd A2 - Sure, York A2 - Domingue, John T1 - Content Aggregation on Knowledge Bases using Graph Clustering T2 - The Semantic Web: Research and Applications PB - Springer C1 - Heidelberg PY - 2006/ CY - VL - 4011 IS - SP - 530 EP - 544 UR - http://www.kde.cs.uni-kassel.de/stumme/papers/2006/schmitz2006content.pdf DO - KW - 2006 KW - aggregation KW - clustering KW - content KW - graph KW - itegpub KW - l3s KW - myown KW - nepomuk KW - ontologies KW - ontology KW - seminar2006 KW - theory L1 - SN - N1 - N1 - AB - 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. ER - TY - JOUR AU - Dias, Vânia M.F. AU - de Figueiredo, Celina M.H. AU - Szwarcfiter, Jayme L. T1 - Generating bicliques of a graph in lexicographic order JO - Theoretical Computer Science PY - 2005/ VL - 337 IS - 1-3 SP - 240 EP - 248 UR - http://www.sciencedirect.com/science/article/B6V1G-4FD0HTT-3/2/7efa1ee4d7b4823c7315a58b94f2f280 DO - DOI: 10.1016/j.tcs.2005.01.014 KW - conp KW - graph KW - independent KW - set KW - theory L1 - SN - N1 - N1 - AB - 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. ER - TY - BOOK AU - Diestel, Reinhard A2 - T1 - Graph Theory PB - Springer-Verlag Heidelberg, New York C1 - PY - 2005/ VL - IS - SP - EP - UR - http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf DO - KW - book KW - density KW - diesel KW - graph KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Haveliwala, T.H. AU - Kamvar, S.D. T1 - The second eigenvalue of the Google matrix JO - A Stanford University Technical Report http://dbpubs. stanford. edu PY - 2003/ VL - IS - SP - EP - UR - DO - KW - graph KW - pagerank KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - CONF AU - Yu, Stella X. AU - Shi, Jianbo A2 - T1 - Multiclass Spectral Clustering T2 - Proc. International Conference on Computer Vision (ICCV 03) PB - C1 - Nice, France PY - 2003/october CY - VL - IS - SP - EP - UR - DO - KW - Spectral KW - graph KW - partitioning KW - theory L1 - SN - N1 - N1 - AB - ER - TY - UNPB AU - Blelloch, Guy A2 - T1 - Graph Separators PY - 2002/ SP - EP - UR - DO - KW - graph KW - separators KW - theory L1 - N1 - N1 - AB - ER - TY - CONF AU - Dhillon, Inderjit S. A2 - T1 - Co-clustering documents and words using bipartite spectral graph partitioning T2 - KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining PB - ACM Press C1 - New York, NY, USA PY - 2001/ CY - VL - IS - SP - 269 EP - 274 UR - http://portal.acm.org/citation.cfm?id=502512.502550 DO - 10.1145/502512.502550 KW - community KW - detection KW - graph KW - spectral KW - theory L1 - SN - 158113391X N1 - N1 - AB - ER - TY - GEN AU - Monien, B. A2 - T1 - On Spectral Bounds for the k-Partitioning of Graphs JO - PB - C1 - PY - 2001/ VL - IS - SP - EP - UR - DO - KW - graph KW - spectral KW - theory L1 - N1 - N1 - AB - ER - TY - UNPB AU - Ranade, A.G. A2 - T1 - Some uses of spectral methods PY - 2000/ SP - EP - UR - DO - KW - clustering KW - graph KW - spectral KW - svd KW - theory L1 - N1 - N1 - AB - ER - TY - BOOK AU - Chung, F. R. K. A2 - T1 - Spectral Graph Theory PB - American Mathematical Society C1 - PY - 1997/ VL - IS - SP - EP - UR - DO - KW - graph KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Chan, Pak K. AU - Schlag, Martine D. F. AU - Zien, Jason Y. T1 - Spectral K-way ratio-cut partitioning and clustering. JO - IEEE Trans. on CAD of Integrated Circuits and Systems PY - 1994/ VL - 13 IS - 9 SP - 1088 EP - 1096 UR - http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94 DO - KW - community KW - detection KW - graph KW - partitioning KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Hagen, Lars W. AU - Kahng, Andrew B. T1 - New spectral methods for ratio cut partitioning and clustering. JO - IEEE Trans. on CAD of Integrated Circuits and Systems PY - 1992/ VL - 11 IS - 9 SP - 1074 EP - 1085 UR - http://dblp.uni-trier.de/db/journals/tcad/tcad11.html#HagenK92 DO - KW - graph KW - partitioning KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Mohar, B. T1 - The Laplacian spectrum of graphs JO - Graph Theory, Combinatorics, and Applications PY - 1991/ VL - 2 IS - SP - 871 EP - 898 UR - DO - KW - graph KW - laplacian KW - spectral KW - survey KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Pothen, A. AU - Simon, H.D. AU - Liou, K.P. T1 - Partitioning Sparse Matrices with Eigenvectors of Graphs JO - SIAM J. MATRIX ANAL. APPLIC. PY - 1990/ VL - 11 IS - 3 SP - 430 EP - 452 UR - http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970011963_1997016998.pdf DO - KW - clustering KW - community KW - graph KW - partitioning KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Johnson, David S. AU - Papadimitriou, Christos H. T1 - On generating all maximal independent sets JO - Inf. Process. Lett. PY - 1988/ VL - 27 IS - 3 SP - 119 EP - 123 UR - http://portal.acm.org/citation.cfm?id=46241.46243 DO - http://dx.doi.org/10.1016/0020-0190(88)90065-8 KW - complexity KW - graph KW - independent KW - sets KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Fiedler, M. T1 - A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory JO - Czechoslovak Mathematical Journal PY - 1975/ VL - 25 IS - 100 SP - 619 EP - 633 UR - DO - KW - graph KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER -