{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T19:52:15Z","timestamp":1772308335313,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,12,21]],"date-time":"2010-12-21T00:00:00Z","timestamp":1292889600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2010,12,21]],"date-time":"2010-12-21T00:00:00Z","timestamp":1292889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Graph clustering is an important issue for several applications associated with data analysis in graphs. However, the discovery of groups of highly connected nodes that can represent clusters is not an easy task. Many assumptions like the number of clusters and if the clusters are or not balanced, may need to be made before the application of a clustering algorithm. Moreover, without previous information regarding data label, there is no guarantee that the partition found by a clustering algorithm automatically extracts the relevant information present in the data. This paper proposes a new graph clustering algorithm that automatically defines the number of clusters based on a clustering tendency connectivity-based validation measure, also proposed in the paper. According to the computational results, the new algorithm is able to efficiently find graph clustering partitions for complete graphs.<\/jats:p>","DOI":"10.1007\/s13173-010-0027-x","type":"journal-article","created":{"date-parts":[[2010,12,20]],"date-time":"2010-12-20T17:34:54Z","timestamp":1292866494000},"page":"19-29","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A graph clustering algorithm based on a clustering coefficient for\u00a0weighted graphs"],"prefix":"10.1007","volume":"17","author":[{"given":"Mari\u00e1 C. V.","family":"Nascimento","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9 C. P. L. F.","family":"Carvalho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,12,21]]},"reference":[{"issue":"24","key":"27_CR1","doi-asserted-by":"publisher","first-page":"13790","DOI":"10.1073\/pnas.191502998","volume":"98","author":"A Bhattacharjee","year":"2001","unstructured":"Bhattacharjee A, Richards WG, Staunton J, Li C, Monti S, Vasa P, Ladd C, Beheshti J, Bueno R, Gillette M, Loda M, Weber G, Mark EJ, Lander ES, Wong W, Johnson BE, Golub TR, Sugarbaker DJ, Meyerson M (2001) Classification of human lung carcinomas by mRNA expression profiling reveals distinct adenocarcinoma sub-classes. Proc Natl Acad Sci USA 98(24):13790\u201313795","journal-title":"Proc Natl Acad Sci USA"},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"3171","DOI":"10.1016\/j.cor.2005.01.027","volume":"33","author":"V Boginski","year":"2006","unstructured":"Boginski V, Butenko S, Pardalos PM (2006) Mining market data: a network approach. Comput Oper Res 33:3171\u20133184","journal-title":"Comput Oper Res"},{"issue":"6","key":"27_CR3","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111","volume":"70","author":"A Clauset","year":"2004","unstructured":"Clauset A, Newman MEJ, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111","journal-title":"Phys Rev E"},{"issue":"11","key":"27_CR4","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1109\/TPAMI.2007.1115","volume":"29","author":"IS Dhillon","year":"2007","unstructured":"Dhillon IS, Guan Y, Kulis B (2007) Weighted graph cuts without eigenvectors a multilevel approach. IEEE Trans Pattern Anal Mach Intell 29(11):1944\u20131957","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"27_CR5","first-page":"107","volume-title":"KBS in government, online publications","author":"IW Evett","year":"1987","unstructured":"Evett IW, Spiehler EJ (1987) Rule induction in forensic science. In: KBS in government, online publications, pp 107\u2013118"},{"key":"27_CR6","first-page":"464","volume-title":"31ST ANNUAL ACM STOC","author":"T Feder","year":"1999","unstructured":"Feder T, Hell P, Klein S, Motwani R (1999) Complexity of graph partition problems. In: 31ST ANNUAL ACM STOC. Plenum, New York, pp 464\u2013472"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1111\/j.1469-1809.1936.tb02137.x","volume":"7","author":"RA Fisher","year":"1936","unstructured":"Fisher RA (1936) The use of multiple measurements in taxonomic problems. Ann Eugen 7:179\u2013188","journal-title":"Ann Eugen"},{"issue":"5439","key":"27_CR8","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1126\/science.286.5439.531","volume":"286","author":"TR Golub","year":"1999","unstructured":"Golub TR, Slonim DK, Tamayo P, Huard C, Gaasenbeek M, Mesirov JP, Coller H, Loh ML, Downing JR, Caligiuri MA, Bloomfield CD, Lander ES (1999) Molecular classification of cancer: class discovery and class prediction by gene expression monitoring. Science 286(5439):531\u2013537","journal-title":"Science"},{"issue":"11","key":"27_CR9","doi-asserted-by":"publisher","first-page":"e1195","DOI":"10.1371\/journal.pone.0001195","volume":"2","author":"Y Hoshida","year":"2007","unstructured":"Hoshida Y, Brunet JP, Tamayo P, Golub TR, Mesiro JP (2007) Subclass mapping: identifying common subtypes in independent disease data sets. PLoS ONE 2(11):e1195","journal-title":"PLoS ONE"},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01908075","volume":"2","author":"L Hubert","year":"1985","unstructured":"Hubert L, Arabie P (1985) Comparing partitions. J Classif 2:193\u2013218","journal-title":"J Classif"},{"key":"27_CR11","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1186\/1471-2105-8-250","volume":"8","author":"C Huttenhower","year":"2007","unstructured":"Huttenhower C, Flamholz AI, Landis JN, Sahi S, Myers CL, Olszewski KL, Hibbs MA, Siemers NO, Troyanskaya OG, Coller HA (2007) Nearest neighbor networks: clustering expression data based on gene neighborhoods. BMC Bioinform 8:250","journal-title":"BMC Bioinform"},{"key":"27_CR12","volume-title":"Proceedings of the international parallel processing symposium","author":"G Karypis","year":"1996","unstructured":"Karypis G, Kumar V (1996) Parallel multilevel graph partitioning. In: Proceedings of the international parallel processing symposium"},{"issue":"1","key":"27_CR13","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis G, Kumar V (1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J Sci Comput 20(1):359\u2013392","journal-title":"SIAM J Sci Comput"},{"issue":"7043","key":"27_CR14","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1038\/nature03702","volume":"435","author":"J Lu","year":"2005","unstructured":"Lu J, Getz G, Miska EA, Alvarez-Saavedra E, Lamb J, Peck D, Sweet-Cordero A, Ebert BL, Mak RH, Ferrando AA, Downing JR, Jacks T, Horvitz RR, Golub TR (2005) Microrna expression profiles classify human cancers. Nature 435(7043):834\u2013838","journal-title":"Nature"},{"key":"27_CR15","first-page":"1025","volume-title":"Advances in neural information processing systems","author":"M Maier","year":"2009","unstructured":"Maier M, von\u00a0Luxburg U, Hein M (2009) Influence of graph construction on graph-based clustering measures. In: Koller D, Schuurmans D, Bengio Y, Bottou L (eds) Advances in neural information processing systems, vol 21, pp\u00a01025\u20131032. Curran, Red Hook"},{"key":"27_CR16","volume-title":"Consensus clustering: a resampling-based method for class discovery and visualization of gene expression microarray data","author":"S Monti","year":"2003","unstructured":"Monti S, Tamayo P, Mesirov J, Golub T (2003) Consensus clustering: a resampling-based method for class discovery and visualization of gene expression microarray data. Kluwer Academic, Dordrecht. Tech rep, Broad Institute\/MIT"},{"key":"27_CR17","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/prot.340110203","volume":"11","author":"K Nakai","year":"1991","unstructured":"Nakai K, Kanehisa M (1991) Expert system for predicting protein localization sites in gram-negative bacteria. Proteins 11:95\u2013110","journal-title":"Proteins"},{"key":"27_CR18","doi-asserted-by":"publisher","first-page":"1381","DOI":"10.1016\/j.cor.2009.02.014","volume":"37","author":"MCV Nascimento","year":"2010","unstructured":"Nascimento MCV, Toledo FMB, Carvalho ACPLF (2010) Investigation of a new GRASP-based clustering algorithm applied to biological data. Comput Oper Res 37:1381\u20131388","journal-title":"Comput Oper Res"},{"key":"27_CR19","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"MEJ Newman","year":"2004","unstructured":"Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69:026113","journal-title":"Phys Rev E"},{"key":"27_CR20","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.065103","volume":"71","author":"JP Onnela","year":"2005","unstructured":"Onnela JP, Saram\u00e4ki J, Kert\u00e9sz J, Kaski K (2005) Intensity and coherence of motifs in weighted complex networks. Phys Rev E 71:065(R), 103(R)","journal-title":"Phys Rev E"},{"key":"27_CR21","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/11569596_31","volume-title":"Computer and information sciences\u2014ISCIS 2005","author":"P Pons","year":"2005","unstructured":"Pons P, Latapy M (2005) Computing communities in large networks using random walks. In: Computer and information sciences\u2014ISCIS 2005, pp 284\u2013293"},{"issue":"26","key":"27_CR22","doi-asserted-by":"publisher","first-page":"15,149","DOI":"10.1073\/pnas.211566398","volume":"98","author":"S Ramaswamy","year":"2001","unstructured":"Ramaswamy S, Tamayo P, Rifkin R, Mukherjee S, Yeang CH, Angelo M, Ladd C, Reich M, Latulippe E, Mesirov JP, Poggio T, Gerald W, Loda M, Lander ES, Golub TR (2001) Multiclass cancer diagnosis using tumor gene expression signatures. Proc Natl Acad Sci USA 98(26):15,149\u201315,154","journal-title":"Proc Natl Acad Sci USA"},{"key":"27_CR23","volume":"74","author":"J Reichardt","year":"2006","unstructured":"Reichardt J, Bornholdt S (2006) Statistical mechanics of community detection. Phys Rev E 74:016 110","journal-title":"Phys Rev E"},{"key":"27_CR24","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","volume":"1","author":"SE Schaeffer","year":"2007","unstructured":"Schaeffer SE (2007) Graph clustering. Comput Sci Rev 1:27\u201364","journal-title":"Comput Sci Rev"},{"key":"27_CR25","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J Shi","year":"2000","unstructured":"Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell 22:888\u2013905","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"27_CR26","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1038\/nm0102-68","volume":"8","author":"MA Shipp","year":"2002","unstructured":"Shipp MA, Ross KN, Tamayo P, Weng AP, Kutok JL, Aguiar RCT, Gaasenbeek M, Angelo M, Reich M, Pinkus GS, Ray TS, Koval MA, Last KW, Norton A, Lister TA, Mesirov J (2002) Diffuse large b-cell lymphoma outcome prediction by gene-expression profiling and supervised machine learning. Nat Med 8:68\u201374","journal-title":"Nat Med"},{"key":"27_CR27","doi-asserted-by":"publisher","first-page":"4465","DOI":"10.1073\/pnas.012025199","volume":"99","author":"AI Su","year":"2002","unstructured":"Su AI, Cooke MP, Ching KA, Hakak Y, Walker JR, Wiltshire T, Orth AP, Vega RG, Sapinoso LM, Moqrich A, Patapoutian A, Hampton GM, Schultz PG, Hogenesch JB (2002) Large-scale analysis of the human and mouse transcriptomes. Proc Natl Acad Sci USA 99:4465\u20134470","journal-title":"Proc Natl Acad Sci USA"},{"issue":"6871","key":"27_CR28","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1038\/415530a","volume":"415","author":"LJ van \u2019t Veer","year":"2002","unstructured":"van \u2019t Veer LJ, Dai H, van\u00a0de Vijver MJ, He YD, Hart AA, Mao M, Peterse HL, van\u00a0der Kooy K, Marton MJ, Witteveen AT, Schreiber GJ, Kerkhoven RM, Roberts C, Linsley PS, Bernards R, Friend SH (2002) Gene expression profiling predicts clinical outcome of breast cancer. Nature 415(6871):530\u2013536","journal-title":"Nature"},{"key":"27_CR29","unstructured":"Venables WN, Smith DM (2010) An introduction to R. R Development Core Team, The R Foundation for Statistical Computing, version\u00a02.11.1"},{"key":"27_CR30","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D Watts","year":"1998","unstructured":"Watts D, Strogatz S (1998) Collective dynamics of small-world networks. Nature 393:440","journal-title":"Nature"},{"issue":"20","key":"27_CR31","doi-asserted-by":"publisher","first-page":"11462","DOI":"10.1073\/pnas.201162998","volume":"98","author":"M West","year":"2001","unstructured":"West M, Blanchette C, Dressman H, Huang E, Ishida S, Spang R, Zuzan H, Olson JA, Marks JR, Nevins JR (2001) Predicting the clinical status of human breast cancer by using gene expression profiles. Proc Natl Acad Sci USA 98(20):11462\u201311467","journal-title":"Proc Natl Acad Sci USA"},{"key":"27_CR32","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S1535-6108(02)00032-6","volume":"1","author":"EJ Yeoh","year":"2002","unstructured":"Yeoh EJ, Ross ME, Shurtleff SA, Williams WK, Patel D, Mahfouz R, Behm F, Raimondi SC, Relling MV, Patel A, Cheng C, Campana D, Wilkins D, Zhou X, Li J, Liu H, Pui CH, Evans WE, Naeve C, Wong L, Downing J (2002) Classification, subtype discovery, and prediction of outcome in pediatric acute lymphoblastic leukemia by gene expression profiling. Cancer Cell 1:133\u2013143","journal-title":"Cancer Cell"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-010-0027-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-010-0027-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-010-0027-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-010-0027-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T09:52:04Z","timestamp":1630489924000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-010-0027-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,21]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["27"],"URL":"https:\/\/doi.org\/10.1007\/s13173-010-0027-x","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,21]]},"assertion":[{"value":"27 May 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}