×

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:

MCODE; AS 136
PDFBibTeX XMLCite
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.: 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), (Gabow, H. N.; Fagin, R., Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC (2005), ACM Press: ACM Press New York, NY, USA)
[4] Agarwal, P. K.; Procopiuc, C. M., Exact and approximation algorithms for clustering, (Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (1998), ACM-SIAM: ACM-SIAM Philadelphia, PA, USA) · 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; D.J. Aldous, J.A. Fill, Reversibe Markov Chains and Random Walks on Graphs. http://www.stat.berkeley.edu/aldous/RWG/book.html
[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, (Proceedings of the Fourty-seventh Annual Symposium on Foundations of Computer Science, FOCS (2006), IEEE Computer Society Press: IEEE Computer Society Press Washington, DC, USA)
[10] Arora, S.; Rao, S.; Vazirani, U., Expander flows, geometric embeddings and graph partitioning, (Proceedings of the Thirty-Sixth Annual Symposium on Theory of Computing, STOC (2004), ACM Press: ACM Press New York, NY, USA) · 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, (Proceedings of the Eighth International Conference on Information Visualisation (2004), IEEE Computer Society)
[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: 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; 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); 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, (Dehne, F. K.H. A.; Sack, J.-R.; Santoro, N., Proceedings of the Second Workshop on Algorithms and Data Structures. Proceedings of the Second Workshop on Algorithms and Data Structures, WADS’91. Proceedings of the Second Workshop on Algorithms and Data Structures. Proceedings of the Second Workshop on Algorithms and Data Structures, WADS’91, Lecture Notes in Computer Science, vol. 519 (1991), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · 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: 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; L.M.A. Bettencourt, Tipping the balances of a small world, Tech. Rep. MIT-CTP-3361 (cond-mat/0304321
[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 University Press Cambridge, UK · Zbl 0797.05032
[28] Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M., The maximum clique problem, (Du, D.-Z.; Pardalos, P. M., Handbook of Combinatorial Optimization, vol. Supplement Volume A (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA, USA), 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); 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, (Proceedings of the Eighth International Conference on Information Visualisation (2004), IEEE Computer Society)
[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, (Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, KDD (1998), ACM: ACM New York, NY, USA) · 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, (Di Battista, G.; Zwick, U., Proceedings of the Eleventh European Symposium on Algorithms. Proceedings of the Eleventh European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 2832 (2003), Springer-Verlag GmbH: Springer-Verlag GmbH Heidelberg, Germany)
[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, (Hancock, E. R.; Vento, M., Proceedings of the Fourth IARP International Workshop on Graph Based Representations in Pattern Recognition. Proceedings of the Fourth IARP International Workshop on Graph Based Representations in Pattern Recognition, Lecture Notes in Computer Science, vol. 2726 (2003), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · 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; 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, (Leighton, F. T.; Shor, P., Proceedings of the Twenty-ninth Annual Symposium on Theory of Computing, STOC (1997), ACM Press: ACM Press New York, NY, USA) · 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, (Problems in Analysis: Symposium in Honor of Salomon Bochner (1969) (1970), Princeton University Press: Princeton University Press Princeton, NJ, USA) · 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; 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, (Proceedings of the Twenty-fourth Symposium on Principles of Database Systems (2005), ACM Press: ACM Press New York, NY, USA)
[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: American Mathematical Society Providence, RI, USA · Zbl 0867.05046
[52] F.R.K. Chung, Random walks and local cuts in graphs, Linear Algebra and its Applications; 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, (Kambhampati, S.; Knoblock, C. A., Proceedings of IJCAI-03 Workshop on Information Integration on the Web, IIWeb-03 (2003), AAAI)
[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: 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, (Mirchandani, P. B.; Francis, R. L., Discrete Location Theory (1990), John Wiley and Sons, Inc.: John Wiley and Sons, Inc. New York, NY, USA), 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; P. Crescenzi, V. Kann, A compendium of np optimization problems. http://www.csc.kth.se/viggo/wwwcompendium/wwwcompendium.html
[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; 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
[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, (Proceedings of the Twenty-First International Conference on Machine Learning, vol. 69 (2004), ACM Press: ACM Press New York, NY, USA)
[73] Diwan, A. A.; Rane, S.; Seshadri, S.; Sudarshan, S., Clustering techniques for minimizing external path length, (Proceedings of the Twenty-second International Conference on Very Large Data Bases (VLDB) (1996), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Francisco, CA, USA)
[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: 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, (Pandya, P. K.; Radhakrishnan, J., Proceedings of the Twenty-Third Conference on the Foundations of Software Technology and Theoretical Computer Science. Proceedings of the Twenty-Third Conference on the Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 2914 (2003), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · Zbl 1205.68259
[81] Duda, R. O.; Hart, P. E.; Stork, D. G., Pattern Classification (2001), John Wiley & Sons, Inc.: 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, (Proceedings of the Seventh International Symposium on Graph Drawing. Proceedings of the Seventh International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 1731 (1999), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany)
[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, (Selected Papers of Alfréd Rényi, vol. 2 (1976), Akadémiai Kiadó: Akadémiai Kiadó Budapest, Hungary), 308-315, First publication in Publ. Math. Debrecen 1959
[85] Erdős, P.; Rényi, A., On the evolution of random graphs, (Selected Papers of Alfréd Rényi, vol. 2 (1976), Akadémiai Kiadó: Akadémiai Kiadó Budapest, Hungary), 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, (Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC (1988), ACM Press: ACM Press New York, NY, USA)
[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; 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: 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) · Zbl 1032.91716
[108] Gkantsidis, C.; Mihail, M.; Saberi, A., Conductance and congestion in power law graphs, (Proceedings of the International Conference on Measurement and Modeling of Computer Systems (2003), ACM Press: ACM Press New York, NY, USA)
[109] Gkantsidis, C.; Mihail, M.; Zegura, E., Spectral analysis of Internet topologies, (Proceedings of the Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM, vol. 1 (2003), IEEE: IEEE New York, NY, USA)
[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 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, (Philip, T., Proceedings of the Nineteenth International Conference on Computer Applications in Industry and Engineering. Proceedings of the Nineteenth International Conference on Computer Applications in Industry and Engineering, CAINE (2006), ICSA)
[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, (Proceedings of the Fourty-first Annual Symposium on Foundations of Computer Science. Proceedings of the Fourty-first Annual Symposium on Foundations of Computer Science, FOCS (2000), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA, USA)
[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 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, (Batagelj, V.; Bock, H.-H.; Ferligoj, A.; Ziberna, A., Data Science and Classification, Studies in Classification, Data Analysis, and Knowledge Organization (2006), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Germany), 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, (Hochbaum, D. S., Approximation Algorithms for NP-hard Problems (1997), PWS Publishing Company: PWS Publishing Company Boston, MA, USA), 346-398, (Chapter 9)
[127] Holzapfel, K.; Kosub, S.; Maaß, M. G.; Täubig, H., The complexity of detecting fixed-density clusters, (Petreschi, R.; Persiano, G.; Silvestri, R., Proceedings of the Fifth Italian Conference on Algorithms and Complexity. Proceedings of the Fifth Italian Conference on Algorithms and Complexity, CIAC. Proceedings of the Fifth Italian Conference on Algorithms and Complexity. Proceedings of the Fifth Italian Conference on Algorithms and Complexity, CIAC, Lecture Notes in Computer Science, vol. 2653 (2003), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Germany) · Zbl 1032.68121
[128] Hopcroft, J. E.; Khan, O.; Kulis, B.; Selman, B., Natural communities in large linked networks, (Proceedings of the Ninth International Conference on Knowledge Discovery and Data Mining. Proceedings of the Ninth International Conference on Knowledge Discovery and Data Mining, KDD (2003), ACM: ACM New York, NY, USA)
[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.: 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: 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, (Proceedings of the Fourtieth Annual Symposium on Foundations of Computer Science. Proceedings of the Fourtieth Annual Symposium on Foundations of Computer Science, FOCS (1999), IEEE Computer Society: IEEE Computer Society Washington, DC, USA) · 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, (Proceedings of a Symposium on the Complexity of Computer Computations (1972), IBM: IBM Plenum, NY, USA) · Zbl 0366.68041
[144] Kempe, D.; McSherry, F., A decentralized algorithm for spectral analysis, (Babai, L., Proceedings of the Thirty-sixth Annual Symposium on Theory of Computing. Proceedings of the Thirty-sixth Annual Symposium on Theory of Computing, STOC (2004), ACM Press: ACM Press New York, NY, USA) · 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, (Díaz, J.; Serna, M. J., Proceedings of the Fourth Annual European Symposium on Algorithms. Proceedings of the Fourth Annual European Symposium on Algorithms, ESA. Proceedings of the Fourth Annual European Symposium on Algorithms. Proceedings of the Fourth Annual European Symposium on Algorithms, ESA, Lecture Notes in Computer Science, vol. 1136 (1996), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · Zbl 0947.05073
[147] Kim, S., Graph theoretic sequence clustering algorithms and their applications to genome comparison, (Wang, J. T.L.; Wu, C. H.; Wang, P. P., Computational Biology and Genome Informatics (2003), World Scientific Publishing Company), 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: 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: 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, (Proceedings of the Twelfth International World-Wide Web Conference. Proceedings of the Twelfth International World-Wide Web Conference, WWW (2003), ACM Press: ACM Press New York, NY, USA)
[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, (IEEE International Conference on Image Processing, vol. 2 (2005), IEEE)
[160] Lang, K.; Rao, S., A flow-based method for improving the expansion or conductance of graph cuts, (Nemhauser, G. L.; Bienstock, D., Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization. Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization, IPCO. Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization. Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization, IPCO, Lecture Notes in Computer Science, vol. 3064 (2004), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · 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; V. Latora, M. Marchiori, A measure of centrality based on the network efficiency, Tech. Rep. cond-mat/0402050 · Zbl 1122.91372
[163] Lawler, G. F., Intersections of Random Walks, Probability and its Applications (1991), Birkhäuser: 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, (Bolyai Society Mathematical Studies, 2. Bolyai Society Mathematical Studies, 2, Combinatorics, Pál Erdős is Eighty, vol. 2 (1996), Bolyai Mathematical Society), 353-397 · Zbl 0854.60071
[168] Luo, B.; Wilson, R. C.; Hancock, E. R., Spectral feature vectors for graph clustering, (Caelli, T.; Amin, A.; Duin, R. P.; Kamel, M.; de Ridder, D., Proceedings of the Joint IARP International Workshops on Syntactical and Structural Pattern Recognition and Statistical Pattern Recognition. Proceedings of the Joint IARP International Workshops on Syntactical and Structural Pattern Recognition and Statistical Pattern Recognition, Lecture Notes in Computer Science, vol. 2396 (2002), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · Zbl 1073.68717
[169] Luo, B.; Wilson, R. C.; Hancock, E. R., Spectral clustering of graphs, (Goos, G.; Hartmanis, J.; van Leeuwen, J., Proceedings of the Tenth International Conference on Computer Analysis of Images and Patterns. Proceedings of the Tenth International Conference on Computer Analysis of Images and Patterns, CAIP. Proceedings of the Tenth International Conference on Computer Analysis of Images and Patterns. Proceedings of the Tenth International Conference on Computer Analysis of Images and Patterns, CAIP, Lecture Notes in Computer Science, vol. 2756 (2003), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · 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; 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, (Proceedings of the Fourty-Second IEEE Symposium on Foundations of Computer Science. Proceedings of the Fourty-Second IEEE Symposium on Foundations of Computer Science, FOCS (2001), IEEE Computer Society Press: IEEE Computer Society Press Washington, DC, USA)
[174] F. McSherry, Spectral methods for data analysis, Ph.D. Thesis, University of Washington, Seattle, WA, USA, 2004; 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, (Leen, T. K.; Dietterich, T. G.; Tresp, V., Advances in Neural Information Processing Systems 13. Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems, NIPS (2000), MIT Press: MIT Press Cambridge, MA, USA)
[176] Meilă, M.; Shi, J., A random walks view of spectral segmentation, (Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (2001), Morgan Kauffman: Morgan Kauffman San Francisco, CA, USA)
[177] Michalewicz, Z.; Fogel, D. B., How to Solve it: Modern Heuristics (2004), Springer-Verlag GmbH: 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; 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, (Proceedings of the IEEE International Conference on Data Mining. Proceedings of the IEEE International Conference on Data Mining, ICDM (2002))
[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; M.E.J. Newman, A measure of betweenness centrality based on random walks, Tech. Rep. cond-mat/0309045
[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, (Pastor-Satorras, R.; Rubi, M.; Díaz Guilera, A., Statistical Mechanics of Complex Networks: Proceedings of the XVIII Sitges Conference on Statistical Mechanics. Statistical Mechanics of Complex Networks: Proceedings of the XVIII Sitges Conference on Statistical Mechanics, Lecture Notes in Physics, vol. 625 (2003), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Germany) · Zbl 1151.91746
[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, (Dietterich, T. G.; Becker, S.; Ghahramani, Z., Proceedings of the Fourteenth Conference on Advances in Neural Information Processing Systems, vol. 2 (2002), The MIT Press: The MIT Press Cambridge, MA, USA)
[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); 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, (Nikoletseas, S., Proceedings of the Fourth International Workshop on Efficient and Experimental Algorithms. Proceedings of the Fourth International Workshop on Efficient and Experimental Algorithms, WEA. Proceedings of the Fourth International Workshop on Efficient and Experimental Algorithms. Proceedings of the Fourth International Workshop on Efficient and Experimental Algorithms, WEA, Lecture Notes in Computer Science, vol. 3505 (2005), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · Zbl 1121.68357
[192] Papadimitriou, C. H., Computational Complexity (1993), Addison Wesley: 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] (Perkins, C. E., Ad Hoc Networking (2001), Addison Wesley: Addison Wesley Reading, MA, USA)
[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; 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; 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, (Boulicaut, J.-F.; Esposito, F.; Giannotti, F.; Pedreschi, D., Proceedings of the Fifteenth European Conference on Machine Learning. Proceedings of the Fifteenth European Conference on Machine Learning, ECML. Proceedings of the Fifteenth European Conference on Machine Learning. Proceedings of the Fifteenth European Conference on Machine Learning, ECML, Lecture Notes in Computer Science (2004), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · Zbl 1132.68589
[205] Schaeffer, S. E., Stochastic local clustering for massive graphs, (Ho, T. B.; Cheung, D.; Liu, H., Proceedings of the Ninth Pacific-Asia Conference on Knowledge Discovery and Data Mining. Proceedings of the Ninth Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD. Proceedings of the Ninth Pacific-Asia Conference on Knowledge Discovery and Data Mining. Proceedings of the Ninth Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD, Lecture Notes in Computer Science, vol. 3518 (2005), Springer-Velgar GmbH: Springer-Velgar GmbH Berlin, Heidelberg, Germany)
[206] S.E. Schaeffer, Algorithms for nonuniform networks, Ph.D. Thesis, Helsinki University of Technology, Espoo, Finland, April 2006; 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, (Proceedings of the IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON’06, International Workshop on Wireless Ad-hoc and Sensor Networks, IWWAN’06, subtrack (2006), IEEE Communications Society: IEEE Communications Society New York, NY, USA)
[208] Shamir, R.; Sharan, R.; Tsur, D., Cluster graph modification problems, (Proceedings of the Twenty-eighth International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the Twenty-eighth International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2573 (2002), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Germany) · 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, (Wiedermann, J.; Tel, G.; Pokorný, J.; Bieliková, M.; Štuller, J., Proceedings of the Thirty-second International Conference on Current Trends in Theory and Practice of Computer Science. Proceedings of the Thirty-second International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM. Proceedings of the Thirty-second International Conference on Current Trends in Theory and Practice of Computer Science. Proceedings of the Thirty-second International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM, Lecture Notes in Computer Science, vol. 3831 (2006), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · Zbl 1175.68284
[211] Sinclair, A., Algorithms for Random Generation & Counting: A Markov Chain Approach (1993), Birkhäuser: 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, (Proceedings of the Thirty-seventh IEEE Symposium on Foundations of Computing. Proceedings of the Thirty-seventh IEEE Symposium on Foundations of Computing, FOCS (1996), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA, USA) · Zbl 1122.05062
[214] Spielman, D. A.; Teng, S.-H., Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, (Babai, L., Proceedings of the Thirty-sixth Annual Symposium on Theory of Computing. Proceedings of the Thirty-sixth Annual Symposium on Theory of Computing, STOC (2004), ACM Press: ACM Press New York, NY, USA) · 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., (Clustering Overhead for Hierarchical Routing in Mobile ad hoc Networks. Clustering Overhead for Hierarchical Routing in Mobile ad hoc Networks, Proceedings of the Twenty-first Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3 (2002), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA, USA)
[217] Swamy, C.; Shmoys, D. B., Fault-tolerant facility location, (Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2003), ACM, SIAM) · 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.: Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, pp. 569-650
[220] T. Tanimoto, IBM Internal Report, November 17 1957; 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, (Proceedings of the Thirty-Fourth Symposium on Computing and Statistics. Proceedings of the Thirty-Fourth Symposium on Computing and Statistics, Interface-2002 (2002), The Interface Foundation of North America: The Interface Foundation of North America Fairfax Station, VA, USA)
[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; 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, (Arenas, M.; Herrera, F.; Lozano, M.; Merelo, J.; Romero, G.; Sáanchez, A., Proceedings of the IV Spanish Conference on Metaheuristics. Proceedings of the IV Spanish Conference on Metaheuristics, Evolutionary and Bioinspired Algorithms, vol. 2 (2005), Granada: Granada Spain), (in Spanish)
[226] Vazirani, V. V., Approximation Algorithms (2001), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Germany · Zbl 1138.90417
[227] Virtanen, S. E., Clustering the Chilean web, (Proceedings of the First Latin American Web Congress. Proceedings of the First Latin American Web Congress, LAWEB (2003), IEEE Computer Society: IEEE Computer Society Los Alamitos, CA, USA)
[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; 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, (Unger, H.; Böhme, T.; Mikler, A. R., Proceedings of Second International Workshop on Innovative Internet Computing Systems. Proceedings of Second International Workshop on Innovative Internet Computing Systems, Lecture Notes in Computer Science, vol. 2346 (2002), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · 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 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; 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); 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, (British Machine Vision Conference (2003))
[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; 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, (Kim, W.; Kohavi, R.; Gehrke, J.; DuMouchel, W., Proceedings of the Tenth International Conference on Knowledge Discovery and Data Mining. Proceedings of the Tenth International Conference on Knowledge Discovery and Data Mining, KDD (2004), ACM Press: ACM Press New York, NY, USA)
[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, (Proceedings of the Eight International Conference on VLSI Design (1995), IEEE: IEEE New York, NY, USA)
[242] Yang, B.; Liu, J., An efficient probabilistic approach to network community mining, (Yao, J.; Lingras, P.; Wu, W.-Z.; Szczuka, M.; Cercone, N.; Slezak, D., Rough Sets and Knowledge Technology, Second International Conference. Rough Sets and Knowledge Technology, Second International Conference, RSKT 2007, 14-16 May, Toronto, Canada. Rough Sets and Knowledge Technology, Second International Conference. Rough Sets and Knowledge Technology, Second International Conference, RSKT 2007, 14-16 May, Toronto, Canada, Lecture Notes in Computer Science, vol. 4481 (2007)), 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; 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, (Proceddings of the Sixth Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Proceddings of the Sixth Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD. Proceddings of the Sixth Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Proceddings of the Sixth Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD, Lecture Notes in Computer Science, vol. 2336 (2002), Springer-Verlag GmbH: Springer-Verlag GmbH Berlin, Heidelberg, Germany) · 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); 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.