Top

Journal of Visualization

Published in:

22-09-2020 | Regular Paper

TS-Extractor: large graph exploration via subgraph extraction based on topological and semantic information

Authors: Kun Fu, Tingyun Mao, Yang Wang, Daoyu Lin, Yuanben Zhang, Junjian Zhan, Xian Sun, Feng Li

Published in: Journal of Visualization | Issue 1/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Exploring large graphs is difficult due to their large size and semantic information such as node attributes. Extracting only a subgraph relevant to the user-specified nodes (called focus nodes) is an effective strategy for exploring a large graph. However, existing approaches following this strategy mainly focus on graph topology and do not fully consider node attributes, resulting in the lack of clear semantics in the extracted subgraphs. In this paper, we propose a novel approach called TS-Extractor that can extract a relevant subgraph around the user-selected focus nodes to help the user explore the large graph from a local perspective. By combining the graph topology and the user-selected node attributes, TS-Extractor can extract and visualize a connected subgraph that contains as many nodes sharing the same/similar attribute values with the focus nodes as possible, thereby providing the user with clear semantics. Based on TS-Extractor, we develop a Web-based graph exploration system that allows users to interactively extract, analyze and expand subgraphs. Through two case studies and a user study, we demonstrate the usability and effectiveness of TS-Extractor.

Graphic abstract

previous article On aesthetics for user-sketched layouts of vertex-weighted graphs

next article Colormap optimization with data equality

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Abello J, Van Ham F, Krishnan N (2006) Ask-graphview: a large scale graph visualization system. IEEE Trans Visual Comput Graph 12(5):669–676CrossRef

Abello J, Hadlak S, Schumann H, Schulz HJ (2014) A modular degree-of-interest specification for the visual analysis of large dynamic networks. IEEE Trans Visual Comput Graph 20(3):337–350CrossRef

Auber D, Chiricota Y, Jourdan F, Melançon G (2003) Multiscale visualization of small world networks. In: IEEE symposium on information visualization 2003 (IEEE Cat. No. 03TH8714), IEEE, pp 75–81

Bostock M, Ogievetsky V, Heer J (2011) D\(^3\) data-driven documents. IEEE Trans Visual Comput Graph 17(12):2301–2309CrossRef

Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Networks ISDN Syst 30(1–7):107–117CrossRef

Chau DH, Kittur A, Hong JI, Faloutsos C (2011) Apolo: Interactive large graph sensemaking by combining machine learning and visualization. In: Acm Sigkdd international conference on knowledge discovery & data mining

Chen W, Guo F, Han D, Pan J, Nie X, Xia J, Zhang X (2019) Structure-based suggestive exploration: a new approach for effective exploration of large networks. IEEE Trans Visual Comput Graph 25(1):555–565CrossRef

Crnovrsanin T, Liao I, Wuy Y, Ma KL (2011) Visual recommendations for network navigation. In: Eurographics

Dörk M, Riche NH, Ramos G, Dumais S (2012) Pivotpaths: strolling through faceted information spaces. IEEE Trans Visual Comput Graph 18(12):2709–2718CrossRef

Dunne C, Shneiderman B (2013) Motif simplification: Improving network visualization readability with fan, connector, and clique glyphs. In: Sigchi conference on human factors in computing systems

Dupont P (2006) Relevant subgraph extraction from random walks in a graph. Res Rep Rr 13(4):264–268

Edge D, Larson J, Mobius M, White C (2018) Trimming the hairball: Edge cutting strategies for making dense graphs usable. In: 2018 IEEE international conference on Big Data (Big Data). IEEE, pp 3951–3958

Frank VH, Adam P (2009) “search, show context, expand on demand”: supporting large graph exploration with degree-of-interest. IEEE Trans Visual Comput Graph 15(6):953CrossRef

Furnas GW (1986) Generalized fisheye views 17(4)

Ghoniem M, Mcgee F, Melançon G, Otjacques B, Pinaud B (2019) The state of the art in multilayer network visualization. arXiv preprint arXiv:1902.06815

Haveliwala TH (2003) Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. Technical Report 2003-29, Stanford InfoLab, http://ilpubs.stanford.edu:8090/750/, extended version of the WWW2002 paper on Topic-Sensitive PageRank

Heer J, Boyd D (2005) Vizster: visualizing online social networks. In: IEEE symposium on information visualization, 2005. INFOVIS 2005. IEEE, pp 32–39

Herman I, Melançon G, Marshall MS (2002) Graph visualization and navigation in information visualization: a survey. IEEE Trans Visual Comput Graph 6(1):24–43CrossRef

Holten D (2006) Hierarchical edge bundles: visualization of adjacency relations in hierarchical data. IEEE Trans Visual Comput Graph 12(5):741–748CrossRef

Hong Z, Xu P, Yuan X, Qu H (2013) Edge bundling in information visualization. Tsinghua Sci Technol 18(2):145–156CrossRef

Jia Y, Hoberock J, Garland M, Hart J (2008) On the visualization of social and other scale-free networks. IEEE Trans Visual Comput Graph 14(6):1285–1292CrossRef

Kairam S, Riche NH, Drucker S, Fernandez R, Heer J (2015) Refinery: visual exploration of large, heterogeneous networks through associative browsing. Comput Graph Forum Wiley Online Library 34:301–310CrossRef

Laumond A, Melançon G, Pinaud B (2017) edoi: Exploratory degree of interest exploration of multilayer networks based on user interest. In: VIS 2017, Poster session

Leskovec J, Faloutsos C (2006) Sampling from large graphs. In: Proceedings of the 12th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 631–636

Li C, Baciu G, Wang Y (2017) Module-based visualization of large-scale graph network data. J Visual 20(2):205–215CrossRef

Liu S, Cui W, Wu Y, Liu M (2014) A survey on information visualization: recent advances and challenges. Visual Comput 30(12):1373–1393CrossRef

Moscovich T, Chevalier F, Henry N, Pietriga E, Fekete JD (2009) Topology-aware navigation in large networks. In: Sigchi conference on human factors in computing systems

Pienta R, Abello J, Kahng M, Chau DH (2015) Scalable graph exploration and visualization: Sensemaking challenges and opportunities. In: International conference on Big Data & smart computing

Pienta R, Kahng M, Lin Z, Vreeken J, Talukdar P, Abello J, Parameswaran G, Chau DH (2017) Facets: adaptive local exploration of large graphs. In: Proceedings of the 2017 SIAM international conference on Data Mining. SIAM, pp 597–605

Pretorius AJ, Wijk JJV (2008) Visual inspection of multivariate graphs

Shen Z, Ma KL, Eliassi-Rad T (2006) Visual analysis of large heterogeneous social networks by semantic and structural abstraction. IEEE Trans Visual Comput Graph 12(6):1427–1439CrossRef

Shi L, Liao Q, Tong H, Hu Y, Zhao Y, Lin C (2014) Hierarchical focus+ context heterogeneous network visualization. In: 2014 IEEE Pacific visualization symposium (PacificVis). IEEE, pp 89–96

Shneiderman B, Aris A (2006) Network visualization by semantic substrates. IEEE Trans Visual Comput Graph 12(5):733–740CrossRef

Stef VDE, Wijk V, Jarke J (2014) Multivariate network exploration and presentation: from detail to overview via selections and aggregations. IEEE Trans Visual Comput Graph 20(12):2310CrossRef

Tang J, Zhang J, Yao L, Li J, Zhang L, Su Z (2008) Arnetminer: extraction and mining of academic social networks. In: Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 990–998

Tong H, Faloutsos C, Pan JY (2006) Fast random walk with restart and its applications. In: Sixth international conference on data mining (ICDM’06). IEEE, pp 613–622

Von Landesberger T, Kuijper A, Schreck T, Kohlhammer J, van Wijk JJ, Fekete JD, Fellner DW (2011) Visual analysis of large graphs: state-of-the-art and future research challenges. Comput Graph Forum Wiley Online Library 30:1719–1749CrossRef

Wattenberg M (2006) Visual exploration of multivariate graphs. In: Proceedings of the SIGCHI conference on Human Factors in computing systems. ACM, pp 811–819

Zhan C, Zhang D, Wang Y, Lin D, Wang H (2019) Ies-backbone: an interactive edge selection based backbone method for small world network visualization. IEEE Access PP(99):1

Zhao Y, Luo X, Lin X, Wang H, Chen W (2019) Visual analytics for electromagnetic situation awareness in radio monitoring and management. IEEE Trans Visual Comput Graph PP(99):1

Title: TS-Extractor: large graph exploration via subgraph extraction based on topological and semantic information
Authors: Kun Fu
Tingyun Mao
Yang Wang
Daoyu Lin
Yuanben Zhang
Junjian Zhan
Xian Sun
Feng Li
Publication date: 22-09-2020
Publisher: Springer Berlin Heidelberg
Published in: Journal of Visualization / Issue 1/2021
Print ISSN: 1343-8875
Electronic ISSN: 1875-8975
DOI: https://doi.org/10.1007/s12650-020-00699-y

Springer Professional

Abstract

Graphic abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2021

Bubble storytelling with automated animation: a Brexit hashtag activism case study

VIStory: interactive storyboard for exploring visual information in scientific publications

Lagrangian visualization of mixing enhancement induced by finite-time stretching in compressible vortex interaction

Correction to: An automatic tooth reconstruction method based on multimodal data

Visual dimension analysis based on dimension subdivision

Who talks to whom: an evaluation of a call log visualization

Premium Partner