×

Graph clustering. (English) Zbl 1302.68237

Summary: In this survey we overview the definitions and methods for graph clustering, that is, finding sets of “related” vertices in graphs. We review the many definitions for what is a cluster in a graph and measures of cluster quality. Then we present global algorithms for producing a clustering for the entire vertex set of an input graph, after which we discuss the task of identifying a cluster for a specific seed vertex by local computation. Some ideas on the application areas of graph clustering algorithms are given. We also address the problematics of evaluating clusterings and benchmarking cluster algorithms.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
62H30 Classification and discrimination; cluster analysis (statistical aspects)
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68-02 Research exposition (monographs, survey articles) pertaining to computer science

Software:

AS 136; MCODE
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Drineas, Petros; Frieze, Alan; Kannan, Ravi; Vempala, Santosh; Vinay, V., Clustering in large graphs and matrices, Machine learning, 56, 9-33, (2004) · Zbl 1089.68090
[2] Aarts, E.; Lenstra, J.K., Local search in combinatorial optimization, (1997), John Wiley & Sons, Inc. Chichester, UK · Zbl 0869.00019
[3] Achlioptas, D.; Clauset, A.; Kempe, D.; Moore, C., On the bias of traceroute sampling (or: why almost every network looks like it has a power law), ()
[4] Agarwal, P.K.; Procopiuc, C.M., Exact and approximation algorithms for clustering, () · Zbl 0994.68178
[5] Agrawal, R.; Jagadish, H.V., Algorithms for searching massive graphs, IEEE transactions on knowledge and data engineering, 6, 2, 225-238, (1994)
[6] D.J. Aldous, J.A. Fill, Reversibe Markov Chains and Random Walks on Graphs. http://www.stat.berkeley.edu/aldous/RWG/book.html, 2001 (in preparation)
[7] Altaf-Ul-Amin, M.; Shinbo, Y.; Mihara, K.; Kurokawa, K.; Kanaya, S., Development and implementation of an algorithm for detection of protein complexes in large interaction networks, BMC bioinformatics, 7, 207, (2006)
[8]  , R.G.; Hu, T., Multiterminal network flows, SIAM journal, 9, 551-570, (1961) · Zbl 0112.12405
[9] Andersen, R.; Chung, F.R.K.; Lang, K., Local partitioning using pagerank vectors, ()
[10] Arora, S.; Rao, S.; Vazirani, U., Expander flows, geometric embeddings and graph partitioning, () · Zbl 1192.68467
[11] Asahiro, Y.; Hassin, R.; Iwama, K., Complexity of finding dense subgraphs, Discrete applied mathematics, 121, 1, 15-26, (2002) · Zbl 1002.68108
[12] Auber, D.; Delest, M.; Chiricota, Y., Strahler based graph clustering using convolution, ()
[13] Aurenhammer, F., Voronoi diagrams — A survey of a fundamental geometric data structure, ACM computing surveys, 23, 3, 345-405, (1991)
[14] Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti Spaccamela, A.; Protasi, M., Complexity and approximation: combinatorial optimization problems and their approximability properties, (1999), Springer-Verlag GmbH Berlin, Heidelberg, Germany · Zbl 0937.68002
[15] F.R. Bach, M.I. Jordan, Learning spectral clustering, Tech. Rep. UCB/CSD-03-1249, Computer Science Division, University of California, Berkeley, CA, USA, Jun. 2003
[16] G.D. Bader, C.W.V. Hogue, An automated method for finding molecular complexes in large protein interaction networks, BMC Bioinformatics 4(2)
[17] Bagrow, J.P.; Bollt, E.M., Local method for detecting communities, Physical review E, 72, 046108, (2005)
[18] Bansal, N.; Blum, A.; Chawla, S., Correlation clustering, Machine learning, 56, 1-3, 89-113, (2004) · Zbl 1089.68085
[19] Bar-Ilan, J.; Kortsarz, G.; Peleg, D., How to allocate network centers, Journal of algorithms, 15, 3, 385-415, (1993) · Zbl 0784.68012
[20] Bar-Ilan, J.; Kortsarz, G.; Peleg, D., How to allocate network centers, Journal of algorithms, 15, 3, 385-415, (1993) · Zbl 0784.68012
[21] Bar-Ilan, J.; Peleg, D., Approximation algorithms for selecting network centers, () · Zbl 0764.68059
[22] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512, (1999) · Zbl 1226.05223
[23] Behrends, E., Introduction to Markov chains, with special emphasis on rapid mixing, (2000), Vieweg & Sohn Braunschweig, Wiesbaden, Germany · Zbl 0953.60063
[24] L.M.A. Bettencourt, Tipping the balances of a small world, Tech. Rep. MIT-CTP-3361 (cond-mat/0304321 at arXiv.org), Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA, USA, 2002
[25] Biernacki, C.; Celeux, G.; Govaert, G., Assessing a mixture model for clustering with the integrated completed likelihood, IEEE transactions on pattern analysis and machine intelligence, 22, 7, 719-725, (2000)
[26] Biernacki, C.; Govaert, G., Using the classification likelihood to choose the number of clusters, Computing science and statistics, 29, 2, 451-457, (1997)
[27] Biggs, N., Algebraic graph theory, (1994), Cambridge University Press Cambridge, UK · Zbl 0797.05032
[28] Bomze, I.M.; Budinich, M.; Pardalos, P.M.; Pelillo, M., The maximum clique problem, (), 1-74 · Zbl 1253.90188
[29] J.G. Booth, G. Casella, J.P. Hobert, Clustering using objective functions and stochastic search, Journal of the Royal Statistical Society, Series B (2007) (submitted for publication) · Zbl 1400.62128
[30] Boutin, F.; Hascoet, M., Cluster validity indices for graph partitioning, ()
[31] Boyer, F.; Morgat, A.; Labarre, L.; Pothier, J.; Viari, A., Syntons, metabolons and interactons: an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data, Bioinformatics, 21, 23, 4209-4215, (2005)
[32] Bradley, P.S.; Fayyad, U.M.; Reina, C., Scaling clustering algorithms to large databases, () · Zbl 1027.62046
[33] Brandes, U., A faster algorithm for betweenness centrality, Journal of mathematical sociology, 25, 2, 163-177, (2001) · Zbl 1051.91088
[34] Brandes, U.; Gaertler, M.; Wagner, D., Experiments on graph clustering algorithms, ()
[35] Brin, S.; Page, L., The anatomy of a large-scale hypertextual web search engine, Computer networks and ISDN systems, 30, 1-7, 107-117, (1998)
[36] Broder, A.Z.; Kumar, S.R.; Maghoul, F.; Raghavan, P.; Rajagopalan, S.; Stata, R.; Tomkins, A.; Wiener, J., Graph structure in the web, Computer networks, 33, 1-6, 309-320, (2000)
[37] Bui, T.N.; Leighton, F.T.; Chaudhuri, S.; Sipser, M., Graph bisection algorithms with good average case behavior, Combinatorica, 7, 2, 171-191, (1987)
[38] Bunke, H.; Foggia, P.; Guidobaldi, C.; Vento, M., Graph clustering using the weighted minimum common supergraph, () · Zbl 1040.68547
[39] Campbell, J.F., Hub location and the \(p\)-hub Median problem, Operations research, 44, 6, 923-935, (1996) · Zbl 0879.90127
[40] Capoccia, A.; Servedioa, V.; Caldarellia, G.; Colaiorib, F., Detecting communities in large networks, Physica A: statistical mechanics and its applications, 352, 2-4, 669-676, (2005)
[41] J.J.M. Carrasco, D.C. Fain, K.J. Lang, L. Zhukov, Clustering of bipartite advertiser-keyword graph, in: Proceedings of the Third IEEE International Conference on Data Mining, Workshop on Clustering Large Data Sets, 2003
[42] Chakrabarti, D.; Faloutsos, C., Graph mining: laws, generators, and algorithms, ACM computing surveys, 38, 1, (2006), Article No. 2
[43] Charikar, M.; Chekuri, C.; Feder, T.; Motwani, R., Incremental clustering and dynamic information retrieval, () · Zbl 0963.68062
[44] Charikar, M.; Panigrahy, R., Clustering to minimize the sum of cluster diameters, Journal of computer and system sciences, 68, 2, 417-441, (2004) · Zbl 1091.68099
[45] Cheeger, J., A lower bound for the smallest eigenvalue of the Laplacian, () · Zbl 0212.44903
[46] Chen, N.; Chen, A.; Zhou, L.; Lu, L., A graph-based clustering algorithm in large transaction databases, Intelligent data analysis, 5, 4, 327-338, (2001) · Zbl 1088.68562
[47] D. Cheng, R. Kannan, S. Vempala, G. Wang, On a recursive spectral algorithm for clustering from pairwise similarities, Tech. Rep. MIT-LCS-TR-906, Laboratory of Computer Science, Massachusetts Institute of Technology, Boston, MA, USA, 2003
[48] Cheng, D.; Vempala, S.; Kannan, R.; Wang, G., A divide-and-merge methodology for clustering, ()
[49] Chudak, F.A.; Shmoys, D.B., Improved approximation algorithms for the uncapacitated facility location problem, SIAM journal on computing, 33, 1, 1-25, (2003) · Zbl 1044.90056
[50] Chun, T.Y., World wide web robots: an overview, Online information review, 22, 3, 135-142, (1999)
[51] Chung, F.R.K., Spectral graph theory, (1997), American Mathematical Society Providence, RI, USA
[52] F.R.K. Chung, Random walks and local cuts in graphs, Linear Algebra and its Applications · Zbl 1115.05054
[53] Chung, F.R.K.; Lu, L.; Vu, V., The spectra of random graphs with given expected degrees, Internet mathematics, 1, 3, 257-275, (2004) · Zbl 1080.05021
[54] Clauset, A., Finding local community structure in networks, Physical review E, 72, 026132, (2005)
[55] Clauset, A.; Moore, C., Accuracy and scaling phenomena in Internet mapping, Physical review letters, 94, 1, 018701, (2005)
[56] Clauset, A.; Newman, M.E.J.; Moore, C., Finding community structure in very large networks, Physical review E, 70, 6, 066111, (2004)
[57] Cohen, W.W.; Ravikumar, P.; Fienberg, S.E., A comparison of string distance metrics for name-matching tasks, ()
[58] Comellas, F.; Gago Álvarez, S., Spectral bounds for the betweenness of a graph, Linear algebra and its applications, 423, 1, 74-80, (2007) · Zbl 1114.05058
[59] Condon, A.; Karp, R.M., Algorithms for graph partitioning on the planted partition model, Random structures & algorithms, 18, 2, 116-140, (2001) · Zbl 0972.68129
[60] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C., Introduction to algorithms, (2001), MIT Press and McGraw Hill Cambridge, MA, USA, pp. 643-700
[61] Cornuéjols, G.; Nemhauser, G.L.; Wolsey, L.A., The uncapacitated facility location problem, (), 119-171 · Zbl 0727.90043
[62] P. Crescenzi, V. Kann, A compendium of np optimization problems. http://www.csc.kth.se/viggo/wwwcompendium/wwwcompendium.html, accessed on May 18, 2007
[63] Cvetković, D., Signless Laplacians and line graphs, bulletin, classe des sciences mathématiques et naturelles, Sciences mathématiques académie serbe des sciences et des arts, CXXXI, 30, 85-92, (2005) · Zbl 1119.05066
[64] L. da F. Costa, F.A. Rodrigues, G. Travieso, P.R. Villas Boas, Characterization of complex networks: A survey of measurements, Tech. Rep. cond-mat/0505185 arXiv.org, May 2005
[65] Dall’Asta, L.; Alvarez-Hamelin, I.; Barrat, A.; Vázquez, A.; Vespignani, A., Exploring networks with traceroute-like probes: theory and simulations, Theoretical computer science, 355, 1, 6-24, (2006) · Zbl 1088.68015
[66] Danon, L.; Díaz Guilera, A.; Arenas, A., The effect of size heterogeneity on community identification in complex networks, Journal of statistical mechanics theory and experiment, P11010, (2006)
[67] Danon, L.; Díaz Guilera, A.; Duch, J.; Arenas, A., Comparing community structure identification, Journal of statistical mechanics theory and experiment, P09008, (2005)
[68] Dave, R.N.; Krishnapuram, R., Robust clustering methods: A unified view, IEEE transactions on fuzzy systems, 5, 2, 270-293, (1997)
[69] Davies, D.L.; Bouldin, D.W., A cluster separation measure, IEEE transactions on pattern analysis and machine intelligence, 1, 4, 224-227, (1979)
[70] de Abreu, N.M.M., Old and new results on algebraic connectivity of graphs, Linear algebra and its applications, 423, 1, 53-73, (2007) · Zbl 1115.05056
[71] Díaz, J.; Petit, J.; Serna, M., A survey of graph layout problems, ACM computing surveys, 34, 3, 313-356, (2002)
[72] Ding, C.; He, X., Linearized cluster assignment via spectral ordering, ()
[73] Diwan, A.A.; Rane, S.; Seshadri, S.; Sudarshan, S., Clustering techniques for minimizing external path length, ()
[74] Donetti, L.; Muñoz, M.A., Detecting network communities: A new systematic and efficient algorithm, Journal of statistical mechanics, P10012, (2004) · Zbl 1073.82596
[75] Dong, Yihong; Zhuang, Yueting; Chen, Ken; Tai, Xiaoying, A hierarchical clustering algorithm based on fuzzy graph connectedness, Fuzzy sets and systems, 157, 13, 1760-1774, (2006) · Zbl 1100.68105
[76] Dorogovtsev, S.N.; Mendes, J.F.F., Evolution of networks, Advances in physics, 51, 4, 1079-1187, (2002)
[77] Doyle, P.G.; Snell, J.L., Random walks and electric networks, (1984), Mathematical Association of America Washington, DC, USA · Zbl 0583.60065
[78] Du, H., An algorithm for detecting community structure of social networks based on prior knowledge and modularity, Complexity, 12, 3, 53-60, (2007)
[79] Dubes, R.C.; Jain, A.K., Clustering methodologies in exploratory data analysis, Advances in computers, 19, 113-228, (1980)
[80] Dubhashi, D.P.; Laura, L.; Panconesi, A., Analysis and experimental evaluation of a simple algorithm for collaborative filtering in planted partition models, () · Zbl 1205.68259
[81] Duda, R.O.; Hart, P.E.; Stork, D.G., Pattern classification, (2001), John Wiley & Sons, Inc. New York, NY, USA · Zbl 0968.68140
[82] Edachery, J.; Sen, A.; Brandenburg, F.J., Graph clustering using distance-\(k\) cliques, ()
[83] Elias, P.; Feinstein, A.; Shannon, C.E., Note on maximum flow through a network, IRE transactions on information theory IT-2, 117-119, (1956)
[84] Erdős, P.; Rényi, A., On random graphs I, (), 308-315, First publication in Publ. Math. Debrecen 1959
[85] Erdős, P.; Rényi, A., On the evolution of random graphs, (), 482-525, First publication in MTA Mat. Kut. Int. Közl. 1960
[86] Farkas, I.J.; Derényi, I.; Barabási, A.-L.; Vicsek, T., Spectra of “real-world” graphs: beyond the semicircle law, Physical review E, 64, 2, 026704, (2001)
[87] Farnstrom, F.; Lewis, J.; Elkan, C., Scalability for clustering algorithms revisited, SIGKDD explorations, 2, 2, 1-7, (2000)
[88] Feder, T.; Greene, D.H., Optimal algorithms for approximate clustering, ()
[89] Feige, U.; Krauthgamer, R., A polylogarithmic approximation of the minimum bisection, SIAM journal on computing, 31, 4, 1090-1118, (2002) · Zbl 1015.68240
[90] Feige, U.; Peleg, D.; Kortsarz, G., The dense \(k\)-subgraph problem, Algoritmica, 29, 3, 410-421, (2001) · Zbl 0969.68117
[91] Felner, A., Finding optimal solutions to the graph partitioning problem with heuristic search, Annals of mathematics and artificial intelligence, 45, 3-4, 292-322, (2005) · Zbl 1110.68099
[92] Fiedler, M., Algebraic connectivity of graphs, Czechoslovak mathematical journal, 23, 298-305, (1973) · Zbl 0265.05119
[93] Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak mathematical journal, 25, 619-633, (1975) · Zbl 0437.15004
[94] Flake, G.W.; Lawrence, S.; Giles, C.L.; Coetzee, F.M., Self-organization and identification of web communities, IEEE computer, 35, 3, 66-71, (2002)
[95] Flake, G.W.; Tarjan, R.E.; Tsioutsiouliklis, K., Graph clustering and minimum cut trees, Internet mathematics, 1, 1, 385-408, (2004) · Zbl 1098.68095
[96] Ford, L.R.; Fulkerson, D.R., Maximum flow through a network, Canadian journal of mathematics, 8, 399-404, (1956) · Zbl 0073.40203
[97] Fortunato, S.; Latora, V.; Marchiori, M., Method to find community structures based on information centrality, Physical review E, 70, 056104, (2004)
[98] Fraley, C.; Raftery, A.E., How many clusters? which clustering method? answers via model-based cluster analysis, The computer journal, 41, 8, 578-588, (1998) · Zbl 0920.68038
[99] Fränti, P.; Virmajoki, O.; Hautamäki, V., Fast PNN-based clustering using k-nearest neighbor graph, IEEE transactions on pattern analysis and machine intelligence, 28, 11, 1875-1881, (2006)
[100] Freeman, L.C., A set of measures of centrality based upon betweenness, Sociometry, 40, 1, 35-41, (1977)
[101] T. Furuta, M. Sasaki, F. Ishizaki, A. Suzuki, H. Miyazawa, A new cluster formation method for sensor networks using facility location theory, Tech. Rep. NANZAN-TR-2006-01, Nanzan Academic Society Mathematical Sciences and Information Engineering, Nagoya, Japan, August 2006 · Zbl 1194.90022
[102] Gallo, G.; Grigoriadis, M.D.; Tarjan, R.E., A fast parametric maximum flow algorithm and applications, SIAM journal on computing, 18, 1, 30-55, (1989) · Zbl 0679.68080
[103] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman San Francisco, CA, USA · Zbl 0411.68039
[104] Garey, M.R.; Johnson, D.S.; Stockmeyer, L.J., Some simplified NP-complete graph problems, Theoretical computer science, 1, 3, 237-267, (1976) · Zbl 0338.05120
[105] Gath, I.; Geva, A.B., Unsupervised optimal fuzzy clustering, IEEE transactions on pattern analysis and machine intelligence, 11, 7, 773-780, (1989) · Zbl 0709.62592
[106] Gilbert, E.N., Random graphs, Annals of mathematical statistics, 30, 4, 1141-1144, (1959) · Zbl 0168.40801
[107] Girvan, M.; Newman, M.E.J., Community structure in social and biological networks, Proceedings of the national Academy of sciences, USA, 99, 8271-8276, (2002)
[108] Gkantsidis, C.; Mihail, M.; Saberi, A., Conductance and congestion in power law graphs, ()
[109] Gkantsidis, C.; Mihail, M.; Zegura, E., Spectral analysis of Internet topologies, ()
[110] Goh, K.-I.; Kahng, B.; Kim, D., Spectra and eigenvectors of scale-free networks, Physical review E, 64, 5, 051903, (2001)
[111] Goldberg, A.V.; Tarjan, R.E., A new approach to the maximum-flow problem, Journal of the ACM, 35, 4, 921-940, (1988) · Zbl 0661.90031
[112] Gonzalez, T.F., Clustering to minimize the maximum intercluster distance, Theoretical computer science, 38, 293-306, (1985) · Zbl 0567.62048
[113] Grimmett, G.R.; Stirzaker, D.R., Probability and random processes, (2001), Oxford University Press Oxford, UK · Zbl 1015.60002
[114] Grout, V.; Cunningham, S., A constrained version of a clustering algorithm for switch placement and interconnection in large networks, ()
[115] Guattery, S.; Miller, G.L., On the quality of spectral separators, SIAM journal on matrix analysis and applications, 19, 3, 701-719, (1998) · Zbl 0905.05050
[116] Guha, S.; Mishra, N.; Motwani, R.; O’Callaghan, L., Clustering data streams, ()
[117] Guimerà, R.; Mossa, S.; Turtschi, A.; Nunes Amaral, L.A., The worldwide air transportation network: anomalous centrality, community structure, and cities’ global roles, Proceedings of the national Academy of science of the united states of America, 102, 22, 7794-7799, (2005) · Zbl 1135.90309
[118] Gusfield, D., Algorithms on strings, trees, and sequences: computer science and computational biology, (1997), Cambridge University Press Cambridge, UK · Zbl 0934.68103
[119] Hartigan, J.A.; Wong, M.A., Algorithm AS 136: A \(k\)-means clustering algorithm, Applied statistics, 29, 100-108, (1979) · Zbl 0447.62062
[120] Hartuv, E.; Shamir, R., A clustering algorithm based on graph connectivity, Information processing letters, 76, 4-6, 175-181, (2000) · Zbl 0996.68525
[121] He, X.; Zha, H.; Ding, C.H.Q.; Simon, H.D., Web document clustering using hyperlink structures, Computational statistics & data analysis, 41, 1, 19-45, (2002) · Zbl 1015.62130
[122] Hennig, C.; Hausdorf, B., Design of dissimilarity measures: A new dissimilarity measure between species distribution ranges, (), 29-38
[123] Higham, D.J.; Kalna, G.; Kibble, M., Spectral clustering and its use in bioinformatics, Journal of computational and applied mathematics, 204, 1, 25-37, (2007) · Zbl 1123.65024
[124] Hlaoui, A.; Wang, S., Median graph computation for graph clustering, Soft computing — A fusion of foundations methodologies and applications, 10, 1, 47-53, (2006)
[125] Hochbaum, D.D.; Shmoys, D.B., A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM, 33, 3, 533-550, (1986)
[126] Hochbaum, D.S., Various notions of approximations: good, better, best, and more, (), 346-398, (Chapter 9)
[127] Holzapfel, K.; Kosub, S.; Maaß, M.G.; Täubig, H., The complexity of detecting fixed-density clusters, () · Zbl 1032.68121
[128] Hopcroft, J.E.; Khan, O.; Kulis, B.; Selman, B., Natural communities in large linked networks, ()
[129] Höppner, F.; Klawonn, F.; Kruse, R.; Runkler, T., Fuzzy cluster analysis: methods for classification, data analysis and image recognition, (1999), John Wiley & Sons, Inc. Hoboken, NJ, USA · Zbl 0944.65009
[130] Hou, T.-C.; Tsai, T.-J., An access-based clustering protocol for multihop wireless ad hoc networks, IEEE journal on selected areas in communications, 19, 7, 1201-1210, (2001)
[131] Hsu, W.-L.; Nemhauser, G.L., Easy and hard bottleneck location problems, Discrete and applied mathematics, 1, 209-216, (1979) · Zbl 0424.90049
[132] Hu, H.; Yan, X.; Huang, Y.; Han, J.; Zhou, X.J., Mining coherent dense subgraphs across massive biological networks for functional discovery, Bioinformatics, Suppl. 1, 213-221, (2005)
[133] Jaccard, P., Distribution de la flore alpine dans la bassin de dranses et dans quelques regions voisines, Bulletin del la société vaudoisedes sciences naturelles, 37, 241-272, (1901), cited in [122]
[134] Jain, A.K.; Dubes, R.C., Algorithms for clustering data, (1988), Prentice-Hall Englewood, NJ, USA · Zbl 0665.62061
[135] Jain, A.K.; Murty, M.N.; Flynn, P.J., Data clustering: A review, ACM computing surveys, 31, 3, 264-323, (1999)
[136] Jain, K.; Vazirani, V.V., Primal-dual approximation algorithms for metric facility location and \(k\)-Median problems, () · Zbl 1138.90417
[137] Johnson, D.S.; Aragon, C.R.; McGeoch, L.A.; Schevon, C., Optimization by simulated annealing: an experimental evaluation. part I, graph partitioning, Operations research, 37, 6, 865-892, (1989) · Zbl 0698.90065
[138] Johnson, E.J.L.; Mehrotra, A.; Nemhauser, G.L., MIN-cut clustering, Mathematical programming, 62, 1, 133-151, (1993) · Zbl 0807.90117
[139] Kahale, N., A semidefinite bound for mixing rates of Markov chains, Random structures and algorithms, 11, 4, 299-313, (1998) · Zbl 0889.90154
[140] Kalcsics, J.; Nickel, S.; Schröder, M., Toward a unified territorial design approach: applications, algorithms, and GIS integration, Top, 13, 1, 1-56, (2005) · Zbl 1072.90058
[141] Kannan, N.; Selvaraj, S.; Gromiha, M.M.; Vishveshwara, S., Clusters in \(\alpha / \beta\) barrel proteins: implications for protein structure, function, and folding: A graph theoretical approach, Proteins, 43, 2, 103-112, (2001)
[142] Kannan, R.; Vempala, S.; Vetta, A., On clusterings — good, bad and spectral, Journal of the ACM, 51, 3, 497-515, (2004) · Zbl 1192.05160
[143] Karp, R.M., Reducibility among combinatorial problems, () · Zbl 0366.68041
[144] Kempe, D.; McSherry, F., A decentralized algorithm for spectral analysis, () · Zbl 1192.68848
[145] Kernighan, B.W.; Lin, S., An efficient heuristic procedure for partitioning graphs, Bell system technical journal, 49, 2, 291-308, (1970) · Zbl 0333.05001
[146] Khuller, S.; Sussmann, Y.J., The capacitated \(k\)-center problem, () · Zbl 0947.05073
[147] Kim, S., Graph theoretic sequence clustering algorithms and their applications to genome comparison, (), 81-116, (Chapter 4)
[148] King, A.D.; Przulj, N.; Jurisica, I., Protein complex prediction via cost-based clustering, Bioinformatics, 20, 17, 3013-3020, (2004)
[149] Klein, R.W.; Dubes, R.C., Experiments in projection and clustering by simulated annealing, Pattern recognition, 22, 2, 213-220, (1989) · Zbl 0709.62613
[150] Kleinberg, J., An impossibility theorem for clustering, (2002), MIT Press Cambridge, MA, USA
[151] Kleinberg, J.M.; Lawrence, S., The structure of the web, Science, 294, 5548, 1849-1850, (2001)
[152] Kleinberg, J.M.; Tardos, E., Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields, Journal of the ACM, 49, 5, 14-23, (2002)
[153] Klincewicz, J.G., Heuristics for the \(p\)-hub location problem, European journal of operational research, 53, 25-37, (1991) · Zbl 0726.90042
[154] Kozdron, M., The discrete Dirichlet problem, (April 2000)
[155] Kreher, D.L.; Stinson, D.R., Combinatorial algorithms: generation, enumeration, and search, (1998), CRC Press Boca Raton, FL, USA
[156] Krishna, P.; Vaidya, N.H.; Chatterjee, M.; Pradhan, D.K., A cluster-based approach for routing in dynamic networks, ACM SIGCOMM computer communication review, 27, 2, 49-64, (1997)
[157] Kumar, S.R.; Novak, J.; Raghavan, P.; Tomkins, A., On the bursty evolution of blogspace, ()
[158] Křivánek, M.; Morávek, J., NP-hard problems in hierarchical-tree clustering, Acta informatica, 23, 3, 311-323, (1986) · Zbl 0644.68055
[159] Lakroum, S.; Devlaminck, V.; Terrier, P.; Biela Enberg, P.; Postaire, J.-G., Clustering of the poincare vectors, ()
[160] Lang, K.; Rao, S., A flow-based method for improving the expansion or conductance of graph cuts, () · Zbl 1092.68631
[161] Latora, V.; Marchiori, M., Efficient behavior of small-world networks, Physical review letters, 87, 19, 198701, (2001)
[162] V. Latora, M. Marchiori, A measure of centrality based on the network efficiency, Tech. Rep. cond-mat/0402050, arXiv.org, February 2004 · Zbl 1122.91372
[163] Lawler, G.F., Intersections of random walks, probability and its applications, (1991), Birkhäuser Boston, MA, USA
[164] Li, R.-C., Accuracy of computed eigenvectors via optimizing a Rayleigh quotient, Bit numerical mathematics, 44, 3, 585-593, (2004) · Zbl 1069.65036
[165] Lin, C.R.; Gerla, M., Adaptive clustering for mobile wireless networks, IEEE journal on selected areas in communications, 15, 7, 1265-1275, (1997)
[166] Lipkus, A.H., A proof of the triangle inequality for the tanimoto distance, Journal of mathematical chemistry, 26, 1-3, 263-265, (1999) · Zbl 1048.92501
[167] Lovász, L., Random walks on graphs: A survey, (), 353-397 · Zbl 0854.60071
[168] Luo, B.; Wilson, R.C.; Hancock, E.R., Spectral feature vectors for graph clustering, () · Zbl 1073.68717
[169] Luo, B.; Wilson, R.C.; Hancock, E.R., Spectral clustering of graphs, () · Zbl 1040.68557
[170] R.M. MacGregor, On partitioning a graph: A theoretical and empirical study, Ph.D. Thesis, University of California, Berkeley, CA, USA, 1978
[171] Matsuda, H.; Ishihara, T.; Hashimoto, A., Classifying molecular sequences using a linkage graph with their pairwise similarities, Theoretical computer science, 210, 2, 305-325, (1999) · Zbl 0912.68218
[172] Matula, D.W.; Shahrokhi, F., Sparsest cuts and bottlenecks in graphs, Discrete applied mathematics, 27, 1-2, 113-123, (1990) · Zbl 0733.05056
[173] McSherry, F., Spectral partitioning of random graphs, ()
[174] F. McSherry, Spectral methods for data analysis, Ph.D. Thesis, University of Washington, Seattle, WA, USA, 2004 · Zbl 1192.68848
[175] Meilă, M.; Shi, J., Learning segmentation by random walks, ()
[176] Meilă, M.; Shi, J., A random walks view of spectral segmentation, ()
[177] Michalewicz, Z.; Fogel, D.B., How to solve it: modern heuristics, (2004), Springer-Verlag GmbH Berlin, Heidelberg, Germany · Zbl 1058.68105
[178] M. Mihail, C. Gkantsidis, A. Saberi, E. Zegura, On the semantics of internet topologies, Tech. Rep. GIT-CC-02-07, College of Computing, Georgia Institute of Technology, Atlanta, GA, USA, 2002
[179] Milenova, B.L.; Campos, M.M., O-cluster: scalable clustering of large high dimensional data sets, ()
[180] Newman, M.E., Finding community structure in networks using the eigenvectors of matrices, Physical review E, 74, 3, 036104, (2006)
[181] M.E.J. Newman, A measure of betweenness centrality based on random walks, Tech. Rep. cond-mat/0309045, arXiv.org, September 2003
[182] Newman, M.E.J., Properties of highly clustered networks, Physical review E, 68, 2, 026121, (2003)
[183] Newman, M.E.J., The structure and function of complex networks, SIAM review, 45, 2, 167-256, (2003) · Zbl 1029.68010
[184] Newman, M.E.J., Detecting community structure in networks, The European physical journal B, 38, 2, 321-330, (2004)
[185] Newman, M.E.J., Fast algorithm for detecting community structure in networks, Physical review E, 69, 6, 066133, (2004)
[186] Newman, M.E.J.; Girvan, M., Mixing patterns and community structure in networks, ()
[187] Newman, M.E.J.; Girvan, M., Finding and evaluating community structure in networks, Physical review E, 69, 2, 026113, (2004)
[188] Ng, A.Y.; Jordan, M.I.; Weiss, Y., On spectral clustering: analysis and an algorithm, ()
[189] O’Kelly, M., A clustering approach to the planar hub location problem, Annals of operations research, 40, 1, 339-353, (1992) · Zbl 0782.90063
[190] P. Orponen, S.E. Schaeffer, Locally computable approximations for spectral clustering and absorption times of random walks (in preparation)
[191] Orponen, P.; Schaeffer, S.E., Local clustering of large graphs by approximate Fiedler vectors, () · Zbl 1121.68357
[192] Papadimitriou, C.H., Computational complexity, (1993), Addison Wesley Reading, MA, USA · Zbl 0557.68033
[193] Pereira-Leal, J.B.; Enright, A.J.; Ouzounis, C.A., Detection of functional modules from protein interaction networks, Proteins: structure, function, and bioinformatics, 54, 1, 49-57, (2003)
[194] ()
[195] Plesník, J., A heuristic for the p-center problem in graphs, Discrete and applied mathematics, 17, 263-268, (1987) · Zbl 0637.05020
[196] Pothen, A.; Simon, H.D.; Liou, K.-P., Partitioning sparse matrices with eigenvectors of graphs, SIAM journal on matrix analysis and applications, 11, 3, 430-452, (1990) · Zbl 0711.65034
[197] Puhan, J.; Tuma, T.; Fajfar, I., Spice for windows 95/98/NT, Elektrotehnišski vestnik, 65, 5, 267-271, (1998), Electrotechnical review, Ljubljana, Slovenia
[198] Qiu, H.; Hancock, E.R., Graph matching and clustering using spectral partitions, Pattern recognition, 39, 1, 22-34, (2004)
[199] Rabaey, J.M., The spice circuit simulator, eecs department of the university of California at Berkeley
[200] Raghavan, V.V.; Yu, C.T., A comparison of the stability characteristics of some graph theoretic clustering methods, IEEE transactions on pattern analysis and machine intelligence, 3, 4, 393-403, (1981) · Zbl 0479.62052
[201] R.Z. Ríos-Mercado, E. Fernández, A reactive GRASP for a sales territory design problem with multiple balancing requirements, Tech. Rep. PISIS-2006-12, Graduate Program in Systems Engineering, Universidad Autónoma de Nuevo León, San Nicolás de los Garza, Mexico, September 2006
[202] Robles-Kelly, A.; Hancock, E.R., Graph edit distance from spectral seriation, IEEE transactions on pattern analysis and machine intelligence, 27, 3, 365-378, (2005)
[203] K.A. Rytkönen, A spring-force visualization algorithm implemented in Java (2003), unpublished
[204] Saerens, M.; Fouss, F.; Yen, L.; Dupont, P., The principal components analysis of a graph, and its relationships to spectral clustering, () · Zbl 1132.68589
[205] Schaeffer, S.E., Stochastic local clustering for massive graphs, ()
[206] S.E. Schaeffer, Algorithms for nonuniform networks, Ph.D. Thesis, Helsinki University of Technology, Espoo, Finland, April 2006
[207] Schaeffer, S.E.; Marinoni, S.; Särelä, M.; Nikander, P., Dynamic local clustering for hierarchical ad hoc networks, ()
[208] Shamir, R.; Sharan, R.; Tsur, D., Cluster graph modification problems, () · Zbl 1068.68107
[209] Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE transactions on pattern analysis and machine intelligence, 22, 8, 888-901, (2000)
[210] Šíma, J.; Schaeffer, S.E., On the NP-completeness of some graph cluster measures, () · Zbl 1175.68284
[211] Sinclair, A., Algorithms for random generation & counting: A Markov chain approach, (1993), Birkhäuser Boston, MA, USA · Zbl 0780.68096
[212] Soumyanath, K.; Deogun, J.S., On bisection width of partial \(k\)-trees, Congressus numerantium, 74, 45-51, (1990) · Zbl 0691.68048
[213] Spielman, D.A.; Teng, S.-H., Spectral partitioning works: planar graphs and finite element meshes, () · Zbl 1122.05062
[214] Spielman, D.A.; Teng, S.-H., Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, () · Zbl 1192.65048
[215] Strunkov, S.P., On weakly cospectral graphs, mathematical notes, 80, 4, 590-592, (2006), translated from Matematicheskie Zametki 80 (4) pp. 627-629 · Zbl 1110.05065
[216] Sucec, J.; Marsic, I., ()
[217] Swamy, C.; Shmoys, D.B., Fault-tolerant facility location, () · Zbl 1092.68737
[218] Świercz, B.; Starzak, Ł.; Zubert, M.; Napieralski, A., DMCS-SPICE circuit analysis
[219] Tan, P.-N.; Steinbach, M.; Kumar, V., Cluster analysis: additional issues and algorithms, (2005), Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, pp. 569-650
[220] T. Tanimoto, IBM Internal Report, November 17 1957
[221] Thelwall, M., A web crawler design for data mining, Journal of information science, 27, 5, 319-325, (2001)
[222] Toussaint, G.T., Proximity graphs for nearest neighbor decision rules: recent progress, ()
[223] van Dam, E.R.; Haemers, W.H., Which graphs are determined by their spectrum?, Linear algebra and its applications, 373, 241-272, (2003) · Zbl 1026.05079
[224] S.M. van Dongen, Graph clustering by flow simulation, Ph.D. Thesis, Universiteit Utrecht, Utrecht, The Netherlands, May 2000
[225] Vargas Suáarez, L.; Ríos-Mercado, R.Z.; López, F., Usando GRASP para resolver un problema de definición de territorios de atención comercial, (), (in Spanish)
[226] Vazirani, V.V., Approximation algorithms, (2001), Springer-Verlag GmbH Berlin, Germany · Zbl 1138.90417
[227] Virtanen, S.E., Clustering the Chilean web, ()
[228] S.E. Virtanen, Properties of nonuniform random graph models, Tech. Rep. HUT-TCS-A77, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, May 2003
[229] Vukadinović, D.; Huang, P.; Erlebach, T., On the spectrum and structure of Internet topology graphs, () · Zbl 1046.68944
[230] Washio, T.; Motoda, H., Multi relational data mining (MRDM): state of the art of graph-based data mining, ACM SIGKDD explorations newsletter, 5, 1, 59-68, (2003)
[231] Watts, D.J., Small worlds, (1999), Princeton University Press Princeton, NJ, USA
[232] R. Weber, P. Zezula, Is similarity search useful for high dimensional spaces? in: Proceedings of the Tenth International Workshop on Database and Expert Systems Applications, 1999
[233] W.T. Williams, M.B. Dale, P. Macnaughton-Smith, An objective method of weighting in similarity analysis, Nature 201 (426)
[234] Wilson, R.; Bai, X.; Hancock, E.R., Graph clustering using symmetric polynomials and local linear embedding, ()
[235] Wong, S.M.; Yao, Y.Y., An information-theoretic measure of term specificity, Journal of the American society for information science, 43, 1, 54-61, (1992)
[236] W.-C. Wong, A.W. Fu, Incremental document clustering for web page classification, in: J. Qun (Ed.), International Conference on Information Society in the 21st Century: Emerging Technologies and New Challenges, The University of Aizu, Aizu-Wakamatsu, Fukushima, Japan, 2000
[237] Wu, A.Y.; Garland, M.; Han, J., Mining scale-free networks using geodesic clustering, ()
[238] Wu, F.; Huberman, B.A., Finding communities in linear time: A physics approach, The European physical journal B, 38, 2, 331-338, (2004)
[239] Xie, X.L.; Beni, G., A validity measure for fuzzy clustering, IEEE transactions on pattern analysis and machine intelligence, 8, 841-847, (1991)
[240] Xu, Y.; Olman, V.; Xu, D., Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees, Bioinformatics, 18, 4, 536-545, (2002)
[241] Yan, J.-T.; Hsiao, P.-Y., A new fuzzy-clustering-based approach for two-way circuit partitioning, ()
[242] Yang, B.; Liu, J., An efficient probabilistic approach to network community mining, (), 267-275
[243] Q. Yang, S. Lonardi, A parallel algorithm for clustering protein – protein interaction networks, in: Workshops and Poster Abstracts of the 2005 IEEE Computational Systems Bioinformatics Conference, 2005
[244] Zachary, W.W., An information flow model for conflict and fission in small groups, Journal of anthropological research, 33, 452-473, (1977)
[245] Zahn, C.T., Graph-theoretical methods for detecting and describing gestalt clusters, IEEE transactions on computers, C-20, 1, 68-86, (1971) · Zbl 0264.68040
[246] Zaïane, O.R.; Foss, A.; Lee, C.-H.; Wang, W., On data clustering analysis: scalability, constraints, and validation, () · Zbl 1048.68955
[247] H. Zanghi, C. Ambroise, V. Miele, Fast online graph clustering via Erdős-Rényi mixture, Tech. Rep. 8, Jouy-en-Josas/Paris/Evry, France, April 2007 (submitted for publication) · Zbl 1151.68623
[248] Zhong, S.; Ghosh, J., A unified framework for model-based clustering, Journal of machine learning research, 4, 1001-1037, (2003) · Zbl 1094.68088
[249] Zoltners, A.A.; Sinha, P., Sales territory alignment: A review and model, Management science, 29, 1237-1256, (1983) · Zbl 0526.90055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.