{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T12:08:16Z","timestamp":1767182896598},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,8,21]],"date-time":"2021-08-21T00:00:00Z","timestamp":1629504000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,21]],"date-time":"2021-08-21T00:00:00Z","timestamp":1629504000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2021,12]]},"abstract":"Abstract<\/jats:title>Graph sampling methods have been used to reduce the size and complexity of big complex networks for graph mining and visualization. However, existing graph sampling methods often fail to preserve the connectivity and important structures of the original graph. This paper introduces a new divide and conquer approach to spectral graph sampling based on graph connectivity, called the BC Tree (i.e., decomposition of a connected graph into biconnected components) and spectral sparsification. Specifically, we present two methods, spectral vertex sampling$$BC\\_SV$$<\/jats:tex-math>B<\/mml:mi>C<\/mml:mi>_<\/mml:mi>S<\/mml:mi>V<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and spectral edge sampling$$BC\\_SS$$<\/jats:tex-math>B<\/mml:mi>C<\/mml:mi>_<\/mml:mi>S<\/mml:mi>S<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>by computing effective resistance values of vertices and edges for each connected component. Furthermore, we present$$DBC\\_SS$$<\/jats:tex-math>D<\/mml:mi>B<\/mml:mi>C<\/mml:mi>_<\/mml:mi>S<\/mml:mi>S<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$DBC\\_GD$$<\/jats:tex-math>D<\/mml:mi>B<\/mml:mi>C<\/mml:mi>_<\/mml:mi>G<\/mml:mi>D<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, graph connectivity-based distributed algorithms for spectral sparsification and graph drawing respectively, aiming to further improve the runtime efficiency of spectral sparsification and graph drawing by integrating connectivity-based graph decomposition and distributed computing. Experimental results demonstrate that$$BC\\_SV$$<\/jats:tex-math>B<\/mml:mi>C<\/mml:mi>_<\/mml:mi>S<\/mml:mi>V<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$BC\\_SS$$<\/jats:tex-math>B<\/mml:mi>C<\/mml:mi>_<\/mml:mi>S<\/mml:mi>S<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>are significantly faster than previous spectral graph sampling methods while preserving the same sampling quality.$$DBC\\_SS$$<\/jats:tex-math>D<\/mml:mi>B<\/mml:mi>C<\/mml:mi>_<\/mml:mi>S<\/mml:mi>S<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$DBC\\_GD$$<\/jats:tex-math>D<\/mml:mi>B<\/mml:mi>C<\/mml:mi>_<\/mml:mi>G<\/mml:mi>D<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>obtain further significant runtime improvement over sequential approaches, and$$DBC\\_GD$$<\/jats:tex-math>D<\/mml:mi>B<\/mml:mi>C<\/mml:mi>_<\/mml:mi>G<\/mml:mi>D<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>further achieves significant improvements in quality metrics over sequential graph drawing layouts.<\/jats:p>","DOI":"10.1007\/s41109-021-00405-3","type":"journal-article","created":{"date-parts":[[2021,8,21]],"date-time":"2021-08-21T09:02:55Z","timestamp":1629536575000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["BC tree-based spectral sampling for big complex network visualization"],"prefix":"10.1007","volume":"6","author":[{"given":"Jingming","family":"Hu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tuan Tran","family":"Chu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seok-Hee","family":"Hong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jialu","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amyra","family":"Meidiana","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marnijati","family":"Torkel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Eades","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kwan-Liu","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,21]]},"reference":[{"issue":"4","key":"405_CR1","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1109\/TPDS.2018.2869805","volume":"30","author":"A Arleo","year":"2019","unstructured":"Arleo A, Didimo W, Liotta G, Montecchiani F (2019) A distributed multilevel force-directed algorithm. IEEE Trans Parallel Distrib Syst 30(4):754\u2013765. https:\/\/doi.org\/10.1109\/TPDS.2018.2869805","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"11","key":"405_CR2","doi-asserted-by":"publisher","first-page":"3747","DOI":"10.1073\/pnas.0400087101","volume":"101","author":"A Barrat","year":"2004","unstructured":"Barrat A, Barthelemy M, Pastor-Satorras R, Vespignani A (2004) The architecture of complex weighted networks. Proc Natl Acad Sci USA 101(11):3747\u20133752","journal-title":"Proc Natl Acad Sci USA"},{"issue":"1","key":"405_CR3","first-page":"1","volume":"38","author":"TA Davis","year":"2011","unstructured":"Davis TA, Hu Y (2011) The university of Florida sparse matrix collection. ACM Trans Math Softw (TOMS) 38(1):1","journal-title":"ACM Trans Math Softw (TOMS)"},{"key":"405_CR4","first-page":"149","volume":"42","author":"P Eades","year":"1984","unstructured":"Eades P (1984) A heuristic for graph drawing. Congr Numer 42:149\u2013160","journal-title":"Congr Numer"},{"key":"405_CR5","unstructured":"Eades P (1991) Drawing free trees. International Institute for Advanced Study of Social Information Science, Fujitsu Limited"},{"key":"405_CR6","doi-asserted-by":"crossref","unstructured":"Eades P, Hong S-H, Nguyen A, Klein K (2017a) Shape-based quality metrics for large graph visualization. J Graph Algorithms Appl 21(1):29\u201353","DOI":"10.7155\/jgaa.00405"},{"key":"405_CR7","doi-asserted-by":"crossref","unstructured":"Eades P, Nguyen QH, Hong S (2017b) Drawing big graphs using spectral sparsification. Proc GD 2017:272\u2013286","DOI":"10.1007\/978-3-319-73915-1_22"},{"issue":"1","key":"405_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-6-260","volume":"6","author":"JJ Forman","year":"2005","unstructured":"Forman JJ, Clemons PA, Schreiber SL, Haggarty SJ (2005) Spectralnet-an application for spectral graph analysis and visualization. BMC Bioinform 6(1):1\u201313","journal-title":"BMC Bioinform"},{"issue":"3","key":"405_CR9","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0378-8733(78)90021-7","volume":"1","author":"LC Freeman","year":"1978","unstructured":"Freeman LC (1978) Centrality in social networks conceptual clarification. Soc Netw 1(3):215\u2013239","journal-title":"Soc Netw"},{"issue":"11","key":"405_CR10","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1002\/spe.4380211102","volume":"21","author":"TMJ Fruchterman","year":"1991","unstructured":"Fruchterman TMJ, Reingold EM (1991) Graph drawing by force-directed placement. Softw Pract Exp 21(11):1129\u20131164. https:\/\/doi.org\/10.1002\/spe.4380211102","journal-title":"Softw Pract Exp"},{"key":"405_CR11","doi-asserted-by":"crossref","unstructured":"Galimberti E, Madeddu C, Bonchi F, Ruffo G (2019) Visualizing structural balance in signed networks. In: International conference on complex networks and their applications. Springer, pp 53\u201365","DOI":"10.1007\/978-3-030-36683-4_5"},{"key":"405_CR12","unstructured":"Gammon J, Chakravarti IM, Laha RG, Roy J (1967) Handbook of methods of applied statistics"},{"key":"405_CR13","doi-asserted-by":"crossref","unstructured":"Gansner ER, Koren Y, North S (2004). Graph drawing by stress majorization. In: International symposium on graph drawing. Springer, pp 239\u2013250","DOI":"10.1007\/978-3-540-31843-9_25"},{"issue":"1","key":"405_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41109-017-0042-3","volume":"3","author":"R Gera","year":"2018","unstructured":"Gera R, Alonso L, Crawford B, House J, Mendez-Bermudez J, Knuth T, Miller R (2018) Identifying network structure similarity using spectral graph theory. Appl Netw Sci 3(1):1\u201315","journal-title":"Appl Netw Sci"},{"key":"405_CR15","doi-asserted-by":"crossref","unstructured":"Hachul S, J\u00fcnger M (2004). Drawing large graphs with a potential-field-based multilevel algorithm. In: International symposium on graph drawing. Springer, pp 285\u2013295","DOI":"10.1007\/978-3-540-31843-9_29"},{"issue":"2","key":"405_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.7155\/jgaa.00150","volume":"11","author":"S Hachul","year":"2007","unstructured":"Hachul S, J\u00fcnger M (2007) Large-graph layout algorithms at work: an experimental study. J Graph Algorithms Appl 11(2):345\u2013369","journal-title":"J Graph Algorithms Appl"},{"key":"405_CR17","doi-asserted-by":"crossref","unstructured":"Hagberg A, Swart P, Chult DS (2008) Exploring network structure, dynamics, and function using networkx","DOI":"10.25080\/TCWV9851"},{"key":"405_CR18","unstructured":"Hong S-H, Lu S (2020) Graph sampling methods for big complex networks integrating centrality, k-core, and spectral sparsification. In: Proceedings of the 35th annual ACM symposium on applied computing, pp 1843\u20131851"},{"key":"405_CR19","doi-asserted-by":"publisher","unstructured":"Hong S-H, Nguyen Q, Meidiana A, Li J, Eades P (2018) BC tree-based proxy graphs for visualization of big graphs. In: 2018 IEEE pacific visualization symposium (PacificVis). IEEE. https:\/\/doi.org\/10.1109\/pacificvis.2018.00011","DOI":"10.1109\/pacificvis.2018.00011"},{"issue":"6","key":"405_CR20","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft J, Tarjan R (1973) Algorithm 447: efficient algorithms for graph manipulation. Commun ACM 16(6):372\u2013378","journal-title":"Commun ACM"},{"key":"405_CR21","unstructured":"Hu P, Lau WC (2013) A survey and taxonomy of graph sampling. CoRR, abs\/1308.5865"},{"key":"405_CR22","doi-asserted-by":"crossref","unstructured":"Hu J, Hong S, Eades P (2019) Spectral vertex sampling for big complex graphs. In: Proceedings of the complex networks, pp 216\u2013227","DOI":"10.1007\/978-3-030-36683-4_18"},{"key":"405_CR23","doi-asserted-by":"crossref","unstructured":"Hu J, Hong S-H, Chen J, Torkel M, Eades P, Ma K-L (2020). Connectivity-based spectral sampling for big complex network visualization. In: International conference on complex networks and their applications. Springer, pp 237\u2013248","DOI":"10.1007\/978-3-030-65347-7_20"},{"issue":"2","key":"405_CR24","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1111\/j.1469-8137.1912.tb05611.x","volume":"11","author":"P Jaccard","year":"1912","unstructured":"Jaccard P (1912) The distribution of the flora in the alpine zone. 1. New Phytol 11(2):37\u201350","journal-title":"New Phytol"},{"key":"405_CR25","doi-asserted-by":"crossref","unstructured":"Koren Y (2003) On spectral graph drawing. In: International computing and combinatorics conference. Springer, pp 496\u2013508","DOI":"10.1007\/3-540-45071-8_50"},{"key":"405_CR26","doi-asserted-by":"crossref","unstructured":"Leskovec J, Faloutsos C (2006) Sampling from large graphs. In: Proceedings of the SIGKDD. ACM, pp 631\u2013636","DOI":"10.1145\/1150402.1150479"},{"key":"405_CR27","doi-asserted-by":"crossref","unstructured":"Meidiana A, Hong S, Huang J, Eades P, Ma K (2019) Topology-based spectral sparsification. In: Proceedings of the LDAV, pp 73\u201382","DOI":"10.1109\/LDAV48142.2019.8944358"},{"issue":"2","key":"405_CR28","doi-asserted-by":"publisher","first-page":"26126","DOI":"10.1103\/PhysRevE.67.026126","volume":"67","author":"MEJ Newman","year":"2003","unstructured":"Newman MEJ (2003) Mixing patterns in networks. Phys Rev E 67(2):26126","journal-title":"Phys Rev E"},{"issue":"2","key":"405_CR29","doi-asserted-by":"publisher","first-page":"595","DOI":"10.7155\/jgaa.00370","volume":"19","author":"A Nocaj","year":"2015","unstructured":"Nocaj A, Ortmann M, Brandes U (2015) Untangling the hairballs of multi-centered, small-world online social media networks. JGAA 19(2):595\u2013618","journal-title":"JGAA"},{"key":"405_CR30","doi-asserted-by":"crossref","unstructured":"Rossi R, Ahmed N (2015) The network data repository with interactive graph analytics and visualization. In: Twenty-Ninth AAAI conference on artificial intelligence, pp 4292\u20134293","DOI":"10.1609\/aaai.v29i1.9277"},{"issue":"2","key":"405_CR31","doi-asserted-by":"publisher","first-page":"27105","DOI":"10.1103\/PhysRevE.75.027105","volume":"75","author":"J Saramki","year":"2007","unstructured":"Saramki J, Kivel\u00e4 M, Onnela J-P, Kaski K, Kert\u00f9sz J (2007) Generalizations of the clustering coefficient to weighted complex networks. Phys Rev E 75(2):27105","journal-title":"Phys Rev E"},{"issue":"16","key":"405_CR32","doi-asserted-by":"publisher","first-page":"6483","DOI":"10.1073\/pnas.0808904106","volume":"106","author":"M\u00c1 Serrano","year":"2009","unstructured":"Serrano M\u00c1, Bogun\u00e1 M, Vespignani A (2009) Extracting the multiscale backbone of complex weighted networks. Proc Natl Acad Sci 106(16):6483\u20136488","journal-title":"Proc Natl Acad Sci"},{"key":"405_CR33","doi-asserted-by":"crossref","unstructured":"Spielman DA (2007). Spectral graph theory and its applications. In: 48th annual IEEE symposium on foundations of computer science (FOCS\u201907). IEEE, pp 29\u201338","DOI":"10.1109\/FOCS.2007.4389477"},{"issue":"6","key":"405_CR34","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1137\/080734029","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman DA, Srivastava N (2011) Graph sparsification by effective resistances. SIAM J Comput 40(6):1913\u20131926","journal-title":"SIAM J Comput"},{"issue":"4","key":"405_CR35","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1137\/08074489X","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman DA, Teng S-H (2011) Spectral sparsification of graphs. SIAM J Comput 40(4):981\u20131025","journal-title":"SIAM J Comput"},{"issue":"1","key":"405_CR36","first-page":"401","volume":"23","author":"Y Wu","year":"2017","unstructured":"Wu Y, Cao N, Archambault DW, Shen Q, Qu H, Cui W (2017) Evaluation of graph sampling: a visualization perspective. IEEE TVCG 23(1):401\u2013410","journal-title":"IEEE TVCG"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00405-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-021-00405-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00405-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T01:08:36Z","timestamp":1725671316000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-021-00405-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,21]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["405"],"URL":"https:\/\/doi.org\/10.1007\/s41109-021-00405-3","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2021,8,21]]},"assertion":[{"value":"2 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"60"}}