{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:37:08Z","timestamp":1750307828539,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["(MDA904-01-1-0022)"],"award-info":[{"award-number":["(MDA904-01-1-0022)"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            Clustering method is one of the most important tools in statistics. In a graph theory model, clustering is the process of finding all dense subgraphs. A mathematically well-defined measure for graph density is introduced in this article as follows. Let\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) be a graph (or multi-graph) and\n            <jats:italic>H<\/jats:italic>\n            be a subgraph of\n            <jats:italic>G<\/jats:italic>\n            . The dynamic density of\n            <jats:italic>H<\/jats:italic>\n            is the greatest integer\n            <jats:italic>k<\/jats:italic>\n            such that min\n            <jats:sub>\n              \u2200\n              <jats:italic>P<\/jats:italic>\n            <\/jats:sub>\n            {|\n            <jats:italic>E<\/jats:italic>\n            (\n            <jats:italic>H<\/jats:italic>\n            \/\n            <jats:italic>P<\/jats:italic>\n            )|\/|\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>H<\/jats:italic>\n            \/\n            <jats:italic>P<\/jats:italic>\n            )| \u2212 1} &gt;\n            <jats:italic>k<\/jats:italic>\n            where the minimum is taken over all possible partitions\n            <jats:italic>P<\/jats:italic>\n            of the vertex set of\n            <jats:italic>H<\/jats:italic>\n            , and\n            <jats:italic>H<\/jats:italic>\n            \/\n            <jats:italic>P<\/jats:italic>\n            is the graph obtained from\n            <jats:italic>H<\/jats:italic>\n            by contracting each part of\n            <jats:italic>P<\/jats:italic>\n            into a single vertex. A subgraph\n            <jats:italic>H<\/jats:italic>\n            of\n            <jats:italic>G<\/jats:italic>\n            is a level-\n            <jats:italic>k<\/jats:italic>\n            community if\n            <jats:italic>H<\/jats:italic>\n            is a maximal subgraph of\n            <jats:italic>G<\/jats:italic>\n            with dynamic density at least\n            <jats:italic>k<\/jats:italic>\n            . An algorithm is designed in this paper to detect all level-\n            <jats:italic>h<\/jats:italic>\n            communities of an input multi-graph\n            <jats:italic>G<\/jats:italic>\n            . The worst-case complexity of this algorithm is upper bounded by\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            )|\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>h<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ). This new method is one of few available clustering methods that are mathematically well-defined, supported by rigorous mathematical proof and able to achieve the optimization goal with polynomial complexity. As a byproduct, this algorithm also can be applied for finding edge-disjoint spanning trees of a multi-graph. The worst-case complexity is lower than all known algorithms for multi-graphs.\n          <\/jats:p>","DOI":"10.1145\/1367064.1367075","type":"journal-article","created":{"date-parts":[[2008,7,2]],"date-time":"2008-07-02T12:09:19Z","timestamp":1215000559000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Clustering, community partition and disjoint spanning trees"],"prefix":"10.1145","volume":"4","author":[{"given":"Cun-Quan","family":"Zhang","sequence":"first","affiliation":[{"name":"West Virginia University, Morgantown, WV"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongbin","family":"Ou","sequence":"additional","affiliation":[{"name":"West Virginia University, Morgantown, WV"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,7,4]]},"reference":[{"volume-title":"Technical Report BN 9-71. Stichting Mathematisch Centrum","author":"Anthonisse J. M.","key":"e_1_2_1_1_1","unstructured":"Anthonisse , J. M. 1971. Technical Report BN 9-71. Stichting Mathematisch Centrum , Amsterdam, The Netherlands . Anthonisse, J. M. 1971. Technical Report BN 9-71. Stichting Mathematisch Centrum, Amsterdam, The Netherlands."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.1.104"},{"key":"e_1_2_1_3_1","unstructured":"Barahona F. 2004. Network reinforcement. IBM Research preprint. http:\/\/www.research.ibm.com\/people\/b\/barahon\/publications.html.  Barahona F. 2004. Network reinforcement. IBM Research preprint. http:\/\/www.research.ibm.com\/people\/b\/barahon\/publications.html."},{"key":"e_1_2_1_4_1","unstructured":"Berkhin P. 2002. Survey of Clustering Data Mining Techniques. Accrue Software.  Berkhin P. 2002. Survey of Clustering Data Mining Techniques. Accrue Software."},{"volume-title":"Pattern Recognition with Fuzzy Objective Function Algorithms","author":"Bezdek J. C.","key":"e_1_2_1_5_1","unstructured":"Bezdek , J. C. 1981. Pattern Recognition with Fuzzy Objective Function Algorithms , Plenum Press , New York . Bezdek, J. C. 1981. Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, New York."},{"key":"e_1_2_1_6_1","first-page":"91","volume-title":"Proceedings of the 15th International Conference on Machine Learning","author":"Bradley P. S.","unstructured":"Bradley , P. S. , and Fayyad , U. M . 1998. Refining initial points for K-means clustering . In Proceedings of the 15th International Conference on Machine Learning ( San Francisco, CA). pp. 91 -- 99 . Bradley, P. S., and Fayyad, U. M. 1998. Refining initial points for K-means clustering. In Proceedings of the 15th International Conference on Machine Learning (San Francisco, CA). pp. 91--99."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1967.1053964"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90023-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3829"},{"key":"e_1_2_1_10_1","first-page":"58","article-title":"U-statistic hierarchical clustering","volume":"4","author":"D'andrade R.","year":"1978","unstructured":"D'andrade , R. 1978 . U-statistic hierarchical clustering . Psychometrika 4 , 58 -- 67 . D'andrade, R. 1978. U-statistic hierarchical clustering. Psychometrika 4, 58--67.","journal-title":"Psychometrika"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/967900.968021"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/01969727308546046"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/41.8.578"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1022"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Gabow H. N.","year":"1995","unstructured":"Gabow , H. N. 1995 b. Algorithms for graphic polymatroids and parametric s-sets . In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 88--97. Gabow, H. N. 1995b. Algorithms for graphic polymatroids and parametric s-sets. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 88--97."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758774"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0904"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220040"},{"key":"e_1_2_1_22_1","volume-title":"Data Mining: Concepts and Techniques, The Morgan-Kaufmann Series in Data Management Systems","author":"Han J.","year":"2000","unstructured":"Han , J. , and Kamber , M . 2000 . Data Mining: Concepts and Techniques, The Morgan-Kaufmann Series in Data Management Systems . Jim Gray, Series Ed. Morgan-Kaufmann, San Francisco , CA. Han, J., and Kamber, M. 2000. Data Mining: Concepts and Techniques, The Morgan-Kaufmann Series in Data Management Systems. Jim Gray, Series Ed. Morgan-Kaufmann, San Francisco, CA."},{"volume-title":"Clustering Algorithms","author":"Hartigan J. A.","key":"e_1_2_1_23_1","unstructured":"Hartigan , J. A. 1975. Clustering Algorithms , Wiley , New York . Hartigan, J. A. 1975. Clustering Algorithms, Wiley, New York."},{"volume-title":"Fuzzy cluster analysis, methods for classification, data analysis and image recognition","author":"Hoppner F.","key":"e_1_2_1_24_1","unstructured":"Hoppner , F. , Klawonn , F. , Kruse , R. , and Runkler . T. 1999. Fuzzy cluster analysis, methods for classification, data analysis and image recognition . Wiley , New York . Hoppner, F., Klawonn, F., Kruse, R., and Runkler. T. 1999. Fuzzy cluster analysis, methods for classification, data analysis and image recognition. Wiley, New York."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/331499.331504"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289588"},{"volume-title":"Proceedings of the International Conference on Fuzzy Systems and Knowledge Discovery (Nov.).","author":"Lampinen T.","key":"e_1_2_1_27_1","unstructured":"Lampinen , T. , Koivisto , H. , and Honkanen , T . 2002. Profiling network applications with fuzzy C-means clustering and self-organising map . In Proceedings of the International Conference on Fuzzy Systems and Knowledge Discovery (Nov.). Lampinen, T., Koivisto, H., and Honkanen, T. 2002. Profiling network applications with fuzzy C-means clustering and self-organising map. In Proceedings of the International Conference on Fuzzy Systems and Knowledge Discovery (Nov.)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.5.405"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability","volume":"1","author":"Macqueen J. B.","year":"1967","unstructured":"Macqueen , J. B. 1967 . Some methods for classification and analysis of multivariate observations . In Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability , vol. 1 . University of California Press, Berkeley, CA, 281--297. Macqueen, J. B. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, vol. 1. University of California Press, Berkeley, CA, 281--297."},{"key":"e_1_2_1_30_1","unstructured":"Massart D. L. and Kaufman L. 1983. Interpretation of Analytical Chemical Data by the Use of Cluster Analysis. Wiley Interscience New York ISBN: 0471078611.  Massart D. L. and Kaufman L. 1983. Interpretation of Analytical Chemical Data by the Use of Cluster Analysis. Wiley Interscience New York ISBN: 0471078611."},{"volume-title":"K-Means and Hierarchical Clustering","author":"Moore A. W.","key":"e_1_2_1_31_1","unstructured":"Moore , A. W. 2001. K-Means and Hierarchical Clustering , Carnegie Mellon University , Nov . Moore, A. W. 2001. K-Means and Hierarchical Clustering, Carnegie Mellon University, Nov."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312248"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400054101"},{"key":"e_1_2_1_35_1","unstructured":"Roberts F. S. and Tesman B. 2004. Applied Combinatorics (2nd Ed.). Prentice-Hall Englewood Cliffs NJ.   Roberts F. S. and Tesman B. 2004. Applied Combinatorics (2nd Ed.). Prentice-Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.4.701"},{"key":"e_1_2_1_37_1","unstructured":"SAS Institute. Inc. Introduction to Clustering Procedures. Chap. 8 of SAS\/STAT User's Guide. (SAS OnlineDoc#8482;: Version 8).  SAS Institute. Inc. Introduction to Clustering Procedures. Chap. 8 of SAS\/STAT User's Guide. (SAS OnlineDoc#8482;: Version 8)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"volume-title":"TextMining Workshop, KDD.","author":"Steinbach M.","key":"e_1_2_1_39_1","unstructured":"Steinbach , M. , Karypis , G. , and Kumar , V . 2000. A comparison of document clustering techniques . TextMining Workshop, KDD. Steinbach, M., Karypis, G., and Kumar, V. 2000. A comparison of document clustering techniques. TextMining Workshop, KDD."},{"key":"e_1_2_1_40_1","first-page":"78","article-title":"How to explain hierarchical clustering","volume":"17","author":"Stephen S. P.","year":"1994","unstructured":"Stephen , S. P. 1994 . How to explain hierarchical clustering . Connections 17 , 2, 78 -- 80 . Stephen, S. P. 1994. How to explain hierarchical clustering. Connections 17, 2, 78--80.","journal-title":"Connections"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.221"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Wasserman S. and Faust K. 1994. Social Network Analysis. Cambridge University Press Cambridge UK.  Wasserman S. and Faust K. 1994. Social Network Analysis. Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_43_1","first-page":"331","article-title":"Finding communities in linear time: A physics approach","volume":"38","author":"Wu F.","year":"2004","unstructured":"Wu , F. , and Huberman , B. A. 2004 . Finding communities in linear time: A physics approach . Europ. Phys. J. B - Condensed Matter 38 , 2, 331 -- 338 . Wu, F., and Huberman, B. A. 2004. Finding communities in linear time: A physics approach. Europ. Phys. J. B - Condensed Matter 38, 2, 331--338.","journal-title":"Europ. Phys. J. B - Condensed Matter"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.4.536"},{"volume-title":"Integer Flows and Cycle Covers of Graphs","author":"Zhang C. Q.","key":"e_1_2_1_45_1","unstructured":"Zhang , C. Q. 1997. Integer Flows and Cycle Covers of Graphs . Marcel Dekker Inc ., New York. Zhang, C. Q. 1997. Integer Flows and Cycle Covers of Graphs. Marcel Dekker Inc., New York."},{"key":"e_1_2_1_46_1","unstructured":"Zhang C. Q. and Ou Y. 2006. Method for Data Clustering and Classification by a Graph Theory Model -- Network Partition into High Density Subgraphs. US Patent (Pending 2006: &num; 11\/416 766; Provisional 2005: &num; 60\/677 655)).  Zhang C. Q. and Ou Y. 2006. Method for Data Clustering and Classification by a Graph Theory Model -- Network Partition into High Density Subgraphs. US Patent (Pending 2006: &num; 11\/416 766; Provisional 2005: &num; 60\/677 655))."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367075","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1367064.1367075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:54Z","timestamp":1750255074000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1367064.1367075"],"URL":"https:\/\/doi.org\/10.1145\/1367064.1367075","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,6]]},"assertion":[{"value":"2006-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}