A Scalable Node Ordering Strategy Based on Community Structure for Enhanced Temporal Network Visualization

  • Claudio Linhares Federal University of Uberlândia
  • Fabiola S. Pereira Federal University of Uberlândia
  • Luis E. Rocha University of Greenwich
  • Jose Gustavo S. Paiva Federal University of Uberlândia
  • Jean R. Ponciano Federal University of Uberlândia
  • Bruno A. Travençolo Federal University of Uberlândia

Resumo


Temporal networks have been used to map the structural evolution of social, technological, and biological systems, among others. Due to the large amount of information on real-world temporal networks, increasing attention has been given to issues related to the visual scalability of network visualization layouts. However, visual clutter due to edge overlap remains the main challenge calling for efficient methods to improve the visual experience. In this paper, we propose a novel and scalable node reordering approach for temporal network visualization, named Community-based Node Ordering (CNO), combining static community detection with node reordering techniques to enhance the identification of visual patterns. The perception of trends, periodicity, anomalies, and other temporal patterns, is facilitated, resulting in faster decision making. Our method helps not only the study of network activity patterns within communities but also the analysis of relatively large networks by breaking down its structure in smaller parts. Using CNO, we further propose a taxonomy to categorize activity patterns within communities. We performed a number of experiments and quantitative analyses using two real-world networks with distinct characteristics and showed that the proposed layout and taxonomy speed up the identification of patterns that would otherwise be difficult to see.

Palavras-chave: Temporal networks, Dynamic networks, Network communities, Node reordering, Massive sequence view, Visual scalability

Referências

R. Albert, A.-L. Barabási. Statistical mechanics of complex networks. Rev Mod Phys, 74 (1) (2002), pp. 47-97, 10.1103/RevModPhys.74.47

E. Estrada. Introduction to complex networks: structure and dynamics. Lect Notes Math, 2126 (2015), pp. 93-131, 10.1007/978-3-319-11322-7_3

L. da Fontoura Costa, O.N. Oliveira Jr., G. Travieso, F.A. Rodrigues, P.R.V. Boas, L. Antiqueira, et al. Analyzing and modeling real-world phenomena with complex networks: a survey of applications. Adv Phys, 60 (3) (2011), pp. 329-412, 10.1080/00018732.2011.572452

P. Holme, J. Saramäki. Temp Netw. Phys Rep, 519 (3) (2012), pp. 97-125, 10.1016/j.physrep.2012.03.001

D. Holten, B. Cornelissen, J.J. van Wijk. Trace visualization using hierarchical edge bundles and massive sequence views. Proceedings of the 2007 4th IEEE international workshop on visualizing software for understanding and analysis (2007), pp. 47-54, 10.1109/VISSOF.2007.4290699

S. Elzen, D. Holten, J. Blaas, J.J. van Wijk. Dynamic network visualization with extended massive sequence views
IEEE Trans Vis Comput Graph, 20 (8) (2014), pp. 1087-1099, 10.1109/TVCG.2013.263

C.D.G. Linhares, B.A.N. Travençolo, J.G.S. Paiva, L.E.C. Rocha. DyNetVis: a system for visualization of dynamic networks. Proceedings of the symposium on applied computing, SAC ’17, ACM, Marrakech, Morocco (2017), pp. 187-194, 10.1145/3019612.3019686

Mi P., Sun M., M. Masiane, Cao Y., C. North. Interactive graph layout of a million nodes. Informatics, 3 (2016), p. 23, 10.3390/informatics3040023

S. Fortunato, D. Hric. Community detection in networks: a user guide. Phys Rep, 659 (2016), pp. 1-44, 10.1016/j.physrep.2016.09.002

S. Fortunato. Community detection in graphs. Phys Rep, 486 (3) (2010), pp. 75-174, 10.1016/j.physrep.2009.11.002

G.K. Orman, V. Labatut, M. Plantevit, J.F. Boulicaut. A method for characterizing communities in dynamic attributed complex networks. Proceedings of the 2014 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM 2014) (2014), pp. 481-484, 10.1109/ASONAM.2014.6921629

M. Rosvall, C.T. Bergstrom. Mapping change in large networks. PLoS ONE, 5 (1) (2010), pp. 1-7, 10.1371/journal.pone.0008694

A. Sallaberry, C. Muelder, Ma K.-L. Clustering, visualizing, and navigating for large dynamic graphs. Proceedings of the graph drawing, 7704 (2012), pp. 487-498, 10.1007/978-3-642-36763-2_43

M. Behrisch, B. Bach, N. Henry Riche, T. Schreck, J.-D. Fekete. Matrix reordering methods for table and network visualization. Comput Graph Forum, 35 (3) (2016), pp. 693-716, 10.1111/cgf.12935

G.D. Battista, P. Eades, R. Tamassia, I.G. Tollis. Algorithms for drawing graphs: an annotated bibliography
Comput Geom, 4 (5) (1994), pp. 235-282

F. Beck, M. Burch, S. Diehl, D. Weiskopf. The state of the art in visualizing dynamic graphs. EuroVis STAR, 2 (7) (2014), p. 11

B. Bach. Unfolding dynamic networks for visual exploration. IEEE Comput Graph, 36 (2) (2016), pp. 74-82, 10.1109/MCG.2016.32

J.M. Six, I.G. Tollis. A framework and algorithms for circular drawings of graphs. J Discr Algorithms, 4 (1) (2006), pp. 25-50, 10.1016/j.jda.2005.01.009

D. Archambault, H.C. Purchase. Can animation support the visualisation of dynamic graphs? Inform Sci, 330 (2016), pp. 495-509, 10.1016/j.ins.2015.04.017

M. Burch. Exploring density regions for analyzing dynamic graph data. J Vis Lang Comput (2017), 10.1016/j.jvlc.2017.09.007

M. Burch, C. Vehlow, F. Beck, S. Diehl, D. Weiskopf. Parallel edge splatting for scalable dynamic graph visualization. IEEE Trans Vis Comput Gr, 17 (12) (2011), pp. 2344-2353, 10.1109/TVCG.2011.226

M. Burch. Visual analytics of large dynamic digraphs. Inform Vis, 16 (3) (2017), pp. 167-178, 10.1177/1473871616661194

Y. Tanahashi, Ma K.L. Design Considerations for Optimizing Storyline Visualizations. IEEE Trans Vis Comput Graph, 18 (12) (2012), pp. 2679-2688, 10.1109/TVCG.2012.212

M. Burch, M. Hlawatsch, D. Weiskopf. Visualizing a sequence of a thousand graphs (or even more). Comput Graph Forum (2017), 10.1111/cgf.13185

Teng P., Li H., Zhang X. Survey on visualization layout for big data. Part II, Proceedings of the 5th international conference on intelligence science and big data engineering. Big data and machine learning techniques - IScIDE 2015, Revised Selected Papers, Volume 9243 (2015), pp. 384-394, 10.1007/978-3-319-23862-3_38

A. Lancichinetti, S. Fortunato. Community detection algorithms: a comparative analysis. Phys Rev E, 80 (2009), p. 056117, 10.1103/PhysRevE.80.056117

R. Jarvis, E. Patrick. Clustering using a similarity measure based on shared near neighbors. IEEE T Comput, C-22 (11) (1973), pp. 1025-1034, 10.1109/T-C.1973.223640

M. Ester, H.-P. Kriegel, J. Sander, Xu X. A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with Noise. Proceedings of the Second international conference on knowledge discovery and data mining, AAAI Press (1996), pp. 226-231

Wang W., W.N. Street. A novel algorithm for community detection and influence ranking in social networks
Proceedings of the 2014 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM 2014) (2014), pp. 555-560, 10.1109/ASONAM.2014.6921641

I. Gialampoukidis, T. Tsikrika, S. Vrochidis, I. Kompatsiaris. Community detection in complex networks based on DBSCAN* and a Martingale process. Proceedings of the 2016 11th international workshop on semantic and social media adaptation and personalization (SMAP) (2016), pp. 1-6, 10.1109/SMAP.2016.7753375

M. Rosvall, C.T. Bergstrom. Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci, 105 (4) (2008), pp. 1118-1123, 10.1073/pnas.0706851105

V.D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre. Fast unfolding of communities in large networks. J Stat Mech-Theory E, 2008 (10) (2008), p. P10008, 10.1088/1742-5468/2008/10/p10008

M. Girvan, M.E.J. Newman. Community structure in social and biological networks. Proc Natl Acad Sci, 99 (12) (2002), pp. 7821-7826, 10.1073/pnas.122653799

M.E.J. Newman, M. Girvan. Finding and evaluating community structure in networks. Phys Rev E, 69 (2004), p. 026113, 10.1103/PhysRevE.69.026113

M.A. Porter, J.-P. Onnela, P.J. Mucha. Communities in networks. Not Am Math Soc, 56 (9) (2009), pp. 1082-1097

Ahn Y.-Y., J.P. Bagrow, S. Lehmann. Link communities reveal multiscale complexity in networks. Nature, 466 (7307) (2010), pp. 761-764, 10.1038/nature09182

I. Basaille, S. Kirgizov, É. Leclercq, M. Savonnet, N. Cullot. Towards a Twitter observatory: a multi-paradigm framework for collecting, storing and analysing tweets. Proceedings of the 2016 IEEE 10th international conference on research challenges in information science (RCIS). Grenoble, France (2016), pp. 1-10, 10.1109/RCIS.2016.7549324

F. Beck, M. Burch, S. Diehl, D. Weiskopf. A taxonomy and survey of dynamic graph visualization. Comput Graph Forum, 36 (1) (2017), pp. 133-159, 10.1111/cgf.12791

D. Greene, D. Doyle, P. Cunningham. Tracking the evolution of communities in dynamic social networks. Proceedings of the 2010 international conference on advances in social networks analysis and mining, ASONAM’10, IEEE Computer Society (2010), pp. 176-183, 10.1109/ASONAM.2010.17

B. Mitra, L. Tabourier, C. Roth. Intrinsically dynamic network communities. Comput Netw, 56 (3) (2012), pp. 1041-1053, 10.1016/j.comnet.2011.10.024

C. Vehlow, F. Beck, P. Auwärter, D. Weiskopf. Visualizing the evolution of communities in dynamic graphs
Comput Graph Forum, 34 (1) (2015), pp. 277-288, 10.1111/cgf.12512

S. Fortunato, M. Barthélemy. Resolution limit in community detection. Proc Natl Acad Sci, 104 (1) (2007), pp. 36-41, 10.1073/pnas.0605965104

A. Drif, A. Boukerram. Taxonomy and survey of community discovery methods in complex networks. Int J Comput Sci Eng Surv, 5 (2014), pp. 1-19, 10.5121/ijcses.2014.5401

J.-P. Onnela, J.F. Daniel, R. Stephen, A.P. Mason, J.F. Daniel, J.M. Peter, et al. Taxonomies of networks from community structure. Phys Rev E, 86 (2012), p. 036104, 10.1103/PhysRevE.86.036104

M. Rosvall, J. Delvenne, M.T. Schaub, R. Lambiotte. Different approaches to community detection. CoRR, abs/1712.06468 (2017)

S. Elzen, D. Holten, J. Blaas, J.J. van Wijk. Reducing snapshots to points: a visual analytics approach to dynamic network exploration. IEEE Trans Vis Comput Gr, 22 (1) (2016), pp. 1-10, 10.1109/TVCG.2015.2468078

C. Ware. Information visualization: perception for design. Morgan Kaufmann Series in Interactive Technologies (3 ed.), Morgan Kaufmann, San Francisco, CA, USA (2012)

B. Shneiderman. The eyes have it: a task by data type taxonomy for information visualizations
Proceedings of the 1996 IEEE Symposium on visual languages (1996), pp. 336-343, 10.1109/VL.1996.545307

P. Vanhems, A. Barrat, C. Cattuto, J.-F. Pinton, N. Khanafer, C. Régis, et al. Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PLoS One, 8 (9) (2013), pp. 1-9, 10.1371/journal.pone.0073970

M. Ghoniem, G. Shurkhovetskyy, A. Bahey, B. Otjacques. VAFLE: visual analytics of firewall log events
Proc SPIE, 9017 (2014), 10.1117/12.2037790

F.S. Pereira, S.d. Amo, J. Gama. Detecting events in evolving social networks through node centrality analysis
Proceedings of the workshop on large-scale learning from data streams in evolving environments of ECML PKDD (2016), pp. 83-93

P. Kapanipathi, P. Jain, C. Venkataramani, A. Sheth. Hierarchical interest graph from tweets. Proceedings of the 23rd international conference on world wide web, WWW ’14 Companion, ACM, New York, NY, USA (2014), pp. 311-312, 10.1145/2567948.2577353

Lim K.H., A. Datta. Following the follower: detecting communities with common interests on Twitter
Proceedings of the 23rd ACM conference on hypertext and social media, HT ’12, ACM, New York, NY, USA (2012), pp. 317-318, 10.1145/2309996.2310052

M. Imran, C. Castillo, J. Lucas, P. Meier, S. Vieweg. AIDR: artificial intelligence for disaster response. Proceedings of the 23rd international conference on world wide web, WWW ’14 Companion, ACM, New York, NY, USA (2014), pp. 159-162, 10.1145/2567948.2577034

A. Sharma. Modeling the effect of people’s preferences and social forces on adopting and sharing items
Proceedings of the 8th ACM conference on recommender systems, RecSys ’14, ACM, New York, NY, USA (2014), pp. 421-424, 10.1145/2645710.2653364

J.M. Carrascosa, R. González, R. Cuevas, A. Azcorra. Are trending topics useful for marketing? Visibility of trending topics vs traditional advertisement. Proceedings of the first ACM conference on online social networks, COSN ’13, ACM, New York, NY, USA (2013), pp. 165-176, 10.1145/2512938.2512948

L.E.C. Rocha, N. Masuda, P. Holme. Sampling of temporal networks: methods and biases. Phys Rev E, 96 (2017), p. 052302, 10.1103/PhysRevE.96.052302

Burch M., Huang W., Purchase H., Weiskopf D.. The State of the Art in Empirical User Evaluation of Graph Visualizations. 2018. doi:10.13140/RG.2.2.15550.38720.
Publicado
28/10/2019
LINHARES, Claudio; PEREIRA, Fabiola S. ; ROCHA, Luis E. ; PAIVA, Jose Gustavo S. ; PONCIANO, Jean R. ; TRAVENÇOLO, Bruno A. . A Scalable Node Ordering Strategy Based on Community Structure for Enhanced Temporal Network Visualization. In: CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 32. , 2019, Rio de Janeiro. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . DOI: https://doi.org/10.5753/sibgrapi.2019.9815.