{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T17:03:55Z","timestamp":1790010235341,"version":"4.0.1"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,5,21]],"date-time":"2016-05-21T00:00:00Z","timestamp":1463788800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Research Foundation of Korea(NRF); Ministry of Science, ICT and Future Planning (KR)","award":["NRF-2015K1A3A1A14021055"],"award-info":[{"award-number":["NRF-2015K1A3A1A14021055"]}]},{"name":"Ministry of Science, ICT and Future Planning (KR); Institute for Information & communications Technology Promotion (KR)","award":["10044970"],"award-info":[{"award-number":["10044970"]}]},{"name":"Information communications Technology Promotion (KR); Ministry of Science, ICT and Future Planning (KR)","award":["No.R0190-15-2012"],"award-info":[{"award-number":["No.R0190-15-2012"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["World Wide Web"],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s11280-016-0393-1","type":"journal-article","created":{"date-parts":[[2016,5,23]],"date-time":"2016-05-23T18:02:10Z","timestamp":1464026530000},"page":"491-514","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["MTP: discovering high quality partitions in real world graphs"],"prefix":"10.1007","volume":"20","author":[{"given":"Yongsub","family":"Lim","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Won-Jo","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ho-Jin","family":"Choi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"U","family":"Kang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,5,21]]},"reference":[{"key":"393_CR1","doi-asserted-by":"crossref","unstructured":"Abou-Rjeili, A., Karypis, G.: Multilevel algorithms for partitioning power-law graphs. Proceedings of the 20th International Conference on Parallel and Distributed Processing, 124\u2013124 (2006).","DOI":"10.1109\/IPDPS.2006.1639360"},{"key":"393_CR2","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1038\/nature09182","volume":"466","author":"Y-Y Ahn","year":"2010","unstructured":"Ahn, Y. -Y., Bagrow, J.P., Lehmann, S.: Link communities reveal multiscale complexity in networks. Nature. 466, 761\u2013764 (2010).","journal-title":"Nature"},{"issue":"6749","key":"393_CR3","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1038\/43601","volume":"401","author":"R Albert","year":"1999","unstructured":"Albert, R., Jeong, H., Barab\u00e1si, A.L.: Internet: Diameter of the world-wide Web. Nature. 401 (6749), 130\u2013131 (1999).","journal-title":"Nature"},{"key":"393_CR4","doi-asserted-by":"crossref","unstructured":"Andersen, R., Chung, F.R.K., Lang, K.J.: Local graph partitioning using pagerank vectors. 47th Annual IEEE Symposium on Foundations of Computer Science, 475\u2013486 (2006).","DOI":"10.1109\/FOCS.2006.44"},{"key":"393_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Ge, R., Sachdeva, S.: Finding overlapping communities in social networks Toward a rigorous approach. Proceedings of the 13th ACM Conference on Electronic Commerce, 37\u201354 (2012).","DOI":"10.1145\/2229012.2229020"},{"key":"393_CR6","doi-asserted-by":"crossref","unstructured":"Bourse, F., Lelarge, M., Vojnovic, M.: Balanced graph edge partition. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1456\u20131465 (2014).","DOI":"10.1145\/2623330.2623660"},{"key":"393_CR7","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Papadimitriou, S., Modha, D.S., Faloutsos, C.: Fully automatic cross-associations. Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 79\u201388 (2004).","DOI":"10.1145\/1014052.1014064"},{"issue":"25","key":"393_CR8","doi-asserted-by":"crossref","first-page":"15879","DOI":"10.1073\/pnas.252631999","volume":"99","author":"F Chung","year":"2002","unstructured":"Chung, F., Linyuan, L.: The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. U.S.A. 99 (25), 15879\u201315882 (2002).","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"key":"393_CR9","doi-asserted-by":"crossref","unstructured":"Ciglan, M., Laclav\u00edk, M., N\u00f8rv\u00e5g, K.: On community detection in real-world networks and the importance of degree assortativity. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1007\u20131015 (2013).","DOI":"10.1145\/2487575.2487666"},{"key":"393_CR10","doi-asserted-by":"crossref","unstructured":"Dhillon, I.S., Mallela, S., Modha, D.S.: Information-theoretic co-clustering. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 89\u201398 (2003).","DOI":"10.1145\/956750.956764"},{"issue":"1","key":"393_CR11","doi-asserted-by":"crossref","first-page":"016105+","DOI":"10.1103\/PhysRevE.80.016105","volume":"80","author":"TS Evans","year":"2009","unstructured":"Evans, T.S., Lambiotte, R.: Line graphs, link partitions, and overlapping communities. Phys. Rev. E. 80 (1), 016105+ (2009).","journal-title":"Phys. Rev. E"},{"key":"393_CR12","doi-asserted-by":"crossref","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 251\u2013262 (1999).","DOI":"10.1145\/316188.316229"},{"key":"393_CR13","doi-asserted-by":"crossref","unstructured":"Fiduccia, C.M., Mattheyses, R.M.: A linear-time heuristic for improving network partitions. Proceedings of the 19th Design Automation Conference, 175\u2013181 (1982).","DOI":"10.1109\/DAC.1982.1585498"},{"issue":"3","key":"393_CR14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato, S.: Community detection in graphs. Phys. Rep. 486 (3), 75\u2013174 (2010).","journal-title":"Phys. Rep."},{"key":"393_CR15","unstructured":"Gopalan, P., Mimno, D.M., Gerrish, S., Freedman, M.J., Blei, D.M.: Scalable inference of overlapping communities. 26th Annual Conference on Neural Information Processing Systems, 2258\u20132266 (2012)."},{"key":"393_CR16","unstructured":"Hendrickson, B., Leland, R.: The Chaco User\u2019s Guide Version 2.0. Technical report, Sandia National Laboratories, 1995."},{"issue":"2","key":"393_CR17","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1137\/0916028","volume":"16","author":"B Hendrickson","year":"1995","unstructured":"Hendrickson, B., Leland, R.: An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Comput. 16 (2), 452\u2013469 (1995).","journal-title":"SIAM J. Sci. Comput."},{"key":"393_CR18","doi-asserted-by":"crossref","unstructured":"Hendrickson, B., Leland, R.W.: A multi-level algorithm for partitioning graphs. Proceedings Supercomputing, 28 (1995).","DOI":"10.1145\/224170.224228"},{"issue":"7","key":"393_CR19","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"CAR Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 65: Find. Commun. ACM. 4 (7), 321\u2013322 (1961).","journal-title":"Commun. ACM"},{"key":"393_CR20","doi-asserted-by":"crossref","unstructured":"Kang, U., Faloutsos, C.: Beyond caveman communities: Hubs and spokes for graph compression and mining. 11th IEEE International Conference on Data Mining, 300\u2013309 (2011).","DOI":"10.1109\/ICDM.2011.26"},{"key":"393_CR21","doi-asserted-by":"crossref","unstructured":"Kang, U., Lee, J.Y., Koutra, D., Faloutsos, C.: Net-ray: Visualizing and mining billion-scale graphs. Advances in Knowledge Discovery and Data Mining - 18th Pacific-Asia Conference, 348\u2013361 (2014).","DOI":"10.1007\/978-3-319-06608-0_29"},{"issue":"3","key":"393_CR22","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1145\/990308.990313","volume":"51","author":"R Kannan","year":"2004","unstructured":"Kannan, R, Vempala, S, Vetta, A: On clusterings: good, bad and spectral. J. ACM. 51 (3), 497\u2013515 (2004).","journal-title":"J. ACM"},{"issue":"1","key":"393_CR23","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1006\/jpdc.1997.1404","volume":"48","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput. 48 (1), 96\u2013129 (1998).","journal-title":"J. Parallel Distrib. Comput."},{"key":"393_CR24","doi-asserted-by":"crossref","unstructured":"Kernighan, B.W., Lin, S.: An Efficient Heuristic Procedure for Partitioning Graphs. Bell Sys. Tech. J. 49 (2) (1970).","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"issue":"4","key":"393_CR25","doi-asserted-by":"crossref","first-page":"046104","DOI":"10.1103\/PhysRevE.83.046104","volume":"83","author":"A Khadivi","year":"2011","unstructured":"Khadivi, A., Rad, A.A., Hasler, M.: Network community-detection enhancement by proper weighting. Phys. Rev. E. 83 (4), 046104 (2011).","journal-title":"Phys. Rev. E"},{"key":"393_CR26","doi-asserted-by":"crossref","unstructured":"Kolmogorov, V., Boykov, Y., Rother, C.: Applications of parametric maxflow in computer vision. IEEE 11th International Conference on Computer Vision, 1\u20138 (2007).","DOI":"10.1109\/ICCV.2007.4408910"},{"key":"393_CR27","doi-asserted-by":"crossref","unstructured":"Koutra, D., Kang, U., Vreeken, J., Faloutsos, C.: VOG: Summarizing and understanding large graphs. Proceedings of the 2014 SIAM International Conference on Data Mining, 91\u201399 (2014).","DOI":"10.1137\/1.9781611973440.11"},{"key":"393_CR28","doi-asserted-by":"crossref","unstructured":"Lang, K.J., Rao, S.: A flow-based method for improving the expansion or conductance of graph cuts. Integer Programming and Combinatorial Optimization, 10th International IPCO Conference, 325\u2013337 (2004).","DOI":"10.1007\/978-3-540-25960-2_25"},{"key":"393_CR29","unstructured":"Jure, L. http:\/\/snap.stanford.edu\/snap\/ ."},{"key":"393_CR30","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Statistical properties of community structure in large social and information networks. Proceedings of the 17th International Conference on World Wide Web, 695\u2013704 (2008).","DOI":"10.1145\/1367497.1367591"},{"key":"393_CR31","doi-asserted-by":"crossref","unstructured":"Lim, S., Ryu, S., Kwon, S., Jung, K., Lee, J.-G.: Linkscan*: Overlapping community detection using the link-space transformation. IEEE 30th International Conference on Data Engineering, 292\u2013303 (2014).","DOI":"10.1109\/ICDE.2014.6816659"},{"key":"393_CR32","doi-asserted-by":"crossref","unstructured":"Lim, Y., Jung, K., Kohli, P.: Energy minimization under constraints on label counts. 11th European Conference on Computer Vision, 535\u2013551 (2010).","DOI":"10.1007\/978-3-642-15552-9_39"},{"key":"393_CR33","doi-asserted-by":"crossref","unstructured":"Lim, Y., Jung, K., Kohli, P.: Efficient energy minimization for enforcing label statistics, Vol. 36 (2014).","DOI":"10.1109\/TPAMI.2014.2306415"},{"issue":"12","key":"393_CR34","doi-asserted-by":"crossref","first-page":"3077","DOI":"10.1109\/TKDE.2014.2320716","volume":"26","author":"Y Lim","year":"2014","unstructured":"Lim, Y., Kang, U., Faloutsos, C.: SlashBurn: Graph compression and mining beyond caveman communities. IEEE Trans. Knowl. Data Eng. 26 (12), 3077\u20133089 (2014).","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"393_CR35","doi-asserted-by":"crossref","unstructured":"Lim, Y., Lee, W.-J., Choi, H.-J., Kang, U.: Discovering large subsets with high quality partitions in real world graphs. 2015 International Conference on Big Data and Smart Computing, 186\u2013193 (2015).","DOI":"10.1109\/35021BIGCOMP.2015.7072830"},{"key":"393_CR36","unstructured":"Lin, Z., Cao, N., Tong, H., Wang, F., Kang, U., Chau, D.H.: Interactive multi-resolution exploration of million node graphs. IEEE VIS (2013)."},{"key":"393_CR37","doi-asserted-by":"crossref","unstructured":"Lin, Z., Cao, N., Tong, H., Wang, F., Kang, U., Horng, D.: (Polo) Chau. Demonstrating interactive multi-resolution large graph exploration. 13th IEEE International Conference on Data Mining Workshops, 1097\u20131100 (2013).","DOI":"10.1109\/ICDMW.2013.124"},{"key":"393_CR38","unstructured":"Nagano, K., Kawahara, Y., Aihara, K.: Size-constrained submodular minimization through minimum norm base. Proceedings of the 28th International Conference on Machine Learning, 977\u2013984 (2011)."},{"key":"393_CR39","doi-asserted-by":"crossref","unstructured":"Naor, J., Schwartz, R.: Balanced metric labeling. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 582\u2013591 (2005).","DOI":"10.1145\/1060590.1060676"},{"key":"393_CR40","doi-asserted-by":"crossref","unstructured":"Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E. 69 (2), 026113 (2004).","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"393_CR41","doi-asserted-by":"crossref","unstructured":"Nishimura, J., Ugander, J.: Restreaming graph partitioning: simple versatile algorithms for advanced balancing. The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1106\u20131114 (2013).","DOI":"10.1145\/2487575.2487696"},{"key":"393_CR42","doi-asserted-by":"crossref","unstructured":"Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys Rev. E. 76 (3) (2007).","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"393_CR43","doi-asserted-by":"crossref","unstructured":"Satuluri, V., Parthasarathy, S.: Scalable graph clustering using stochastic flows: applications to community discovery. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 737\u2013746 (2009).","DOI":"10.1145\/1557019.1557101"},{"issue":"1","key":"393_CR44","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","volume":"1","author":"ES Schaeffer","year":"2007","unstructured":"Schaeffer, E.S.: Graph clustering. Comput. Sci. Rev. 1 (1), 27\u201364 (2007).","journal-title":"Comput. Sci. Rev."},{"issue":"2","key":"393_CR45","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(92)90017-P","volume":"43","author":"A Sen","year":"1992","unstructured":"Sen, A., Deng, H., Guha, S.: On a graph partition problem with application to vlsi layout. Inf. Process. Lett. 43 (2), 87\u201394 (1992).","journal-title":"Inf. Process. Lett."},{"issue":"8","key":"393_CR46","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J Shi","year":"2000","unstructured":"Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22 (8), 888\u2013905 (2000).","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"3","key":"393_CR47","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1109\/JCN.2006.6182774","volume":"8","author":"G Siganos","year":"2006","unstructured":"Siganos, G., Tauro, S.L., Michalis, F.: Jellyfish: A conceptual model for the as internet topology. J. Commun. Netw. 8 (3), 339\u2013350 (2006).","journal-title":"J. Commun. Netw."},{"key":"393_CR48","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 81\u201390 (2004).","DOI":"10.1145\/1007352.1007372"},{"key":"393_CR49","doi-asserted-by":"crossref","unstructured":"Stanton, I.: Streaming balanced graph partitioning algorithms for random graphs. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 1287\u20131301 (2014).","DOI":"10.1137\/1.9781611973402.95"},{"key":"393_CR50","doi-asserted-by":"crossref","unstructured":"Stanton, I., Kliot, G.: Streaming graph partitioning for large distributed graphs. The 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1222\u20131230 (2012).","DOI":"10.1145\/2339530.2339722"},{"key":"393_CR51","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E., Gkantsidis, C., Radunovic, B., Vojnovic, M.: FENNEL: Streaming graph partitioning for massive scale graphs. Seventh ACM International Conference on Web Search and Data Mining, 333\u2013342 (2014).","DOI":"10.1145\/2556195.2556213"},{"key":"393_CR52","doi-asserted-by":"crossref","unstructured":"Ugander, J., Backstrom, L.: Balanced label propagation for partitioning massive graphs. Sixth ACM International Conference on Web Search and Data Mining, 507\u2013516 (2013).","DOI":"10.1145\/2433396.2433461"},{"issue":"6","key":"393_CR53","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1109\/TPAMI.2003.1201819","volume":"25","author":"S Wang","year":"2003","unstructured":"Wang, S., Siskind, J.M.: Image segmentation with ratio cut. IEEE Trans. Pattern Anal. Intell. 25 (6), 675\u2013690 (2003).","journal-title":"IEEE Trans. Pattern Anal. Intell."},{"issue":"14","key":"393_CR54","first-page":"1917","volume":"7","author":"N Xu","year":"2014","unstructured":"Xu, N., Chen, L., Loggp, B.C.: A log-based dynamic graph partitioning method. PVLDB. 7 (14), 1917\u20131928 (2014).","journal-title":"PVLDB"},{"issue":"6","key":"393_CR55","doi-asserted-by":"crossref","first-page":"1560","DOI":"10.1109\/TKDE.2014.2377743","volume":"27","author":"N Xu","year":"2015","unstructured":"Xu, N., Cui, B., Chen, L., Zi, H., Shao, Y.: Heterogeneous environment aware streaming graph partitioning. IEEE Trans. Knowl. Data Eng. 27 (6), 1560\u20131572 (2015).","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"393_CR56","doi-asserted-by":"crossref","unstructured":"Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. 12th IEEE International Conference on Data Mining, 745\u2013754 (2012).","DOI":"10.1145\/2350190.2350193"},{"key":"393_CR57","doi-asserted-by":"crossref","unstructured":"Yang, J., Leskovec, J.: Overlapping community detection at scale: a nonnegative matrix factorization approach. Sixth ACM International Conference on Web Search and Data Mining, 587\u2013596 (2013).","DOI":"10.1145\/2433396.2433471"},{"key":"393_CR58","doi-asserted-by":"crossref","unstructured":"Yang, T., Jin, R., Chi, Y., Zhu, S.: Combining link and content for community detection: a discriminative approach. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 927\u2013936 (2009).","DOI":"10.1145\/1557019.1557120"}],"container-title":["World Wide Web"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-016-0393-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11280-016-0393-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-016-0393-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-016-0393-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T16:58:01Z","timestamp":1567961881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11280-016-0393-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,21]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["393"],"URL":"https:\/\/doi.org\/10.1007\/s11280-016-0393-1","relation":{},"ISSN":["1386-145X","1573-1413"],"issn-type":[{"value":"1386-145X","type":"print"},{"value":"1573-1413","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,21]]}}}