Project: Diffusion-aware Temporal Network Layout and Visualization
Description
Background – With “Information Diffusion” we refer to the discipline of modelling how Information “spreads” over a network under the premises of a stochastic model, which approximates and encapsulates the properties of a real diffusion phenomenon [1,2]. The network on which the diffusion takes place can represent different types of networked data, e.g., a social network, a contact tracing network, etc. Considering the flexibility of this representation, it has been used to predict and simulate several real-world phenomena in different domains, such as pathogen outbreaks, malware diffusion on corporate networks, viral marketing, and so on. Within this definition, a diffusion process starts from an arbitrarly small subset of nodes of the network, called “seeds”, and then spreads through the edges as long as it is able to self-sustain (i.e., newly activated nodes will try to influence their neighbors). Finding a set of k seeds that maximizes the number of nodes activated by the diffusion proess under a certain model is a problem known as “Influence Maximization”, known to be NP-hard under classical diffusion models [2].
Despite the abundance of models and research on different algorithmic aspects of this topic (see, e.g., [3,4,5]) there is little research on visualization, typically oriented towards specific scenarios limiting the possibility to extract actionable insights for the whole community to use. A few examples of visual analytics systems oriented towards research on diffusion model design have been presented, but this research is still in its infancy [6].
Within this context, the concept of “temporal networks” [7] has unexpressed potential. Differently from dynamic network visualization with discrete time, temporal networks do not superimpose any structure to the original time dimension, thus avoiding any quantization error and loss of precision. Computing a layout of a temporal network, that is, computing an embedding of the node trajectories over time in a 2D+time 3D space, is computationally expensive. This limited its applicability to large sets of events [8]. New, faster algorithms have been recently introduced and could pave the way to new applications of this technique [9].
Goal – In this project, the candidate is expected to acquire knowledge of temporal networks and the existing methods to generate an embedding of such graph into the “Space-time Cube” (2D + t – see,e.g., [10]) . The main goal of this project is to extend/re-implement the current existing temporal layout algorithms to include information related to the underlying diffusion process, in order to create a “context-“ or, if you want, “diffusion-“aware temporal layout algorithm.
Alternatively, the candidate can also investigate novel visualization methaphors for the visualization of complex diffusion models over networks.
Requirements
• Basic understanding of graph layout algorithms
• Advanced programming skills
• Interest in developing visual analytics solutions (optional)
References and Basic Readings
[1] Guille, Adrien, et al. "Information diffusion in online social networks: A survey." ACM Sigmod Record 42.2 (2013): 17-28
[2] Shashank Sheshar Singh, et al., Influence maximization frameworks, performance, challenges and directions on social network: A theoretical study, Journal of King Saud University - Computer and Information Sciences 34.9 (2022): 7570-7603
[3] Kempe, David, Jon Kleinberg, and Éva Tardos. "Maximizing the spread of influence through a social network." Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 2003.
[4] Rossetti, Giulio, et al. "NDlib: a python library to model and analyze diffusion processes over complex networks." International Journal of Data Science and Analytics 5.1 (2018): 61-79.
[5] Li, Yuchen, et al. "Influence maximization on social graphs: A survey." IEEE Transactions on Knowledge and Data Engineering 30.10 (2018): 1852-1872.
[6] Arleo, Alessio, et al. "Influence Maximization With Visual Analytics." IEEE Transactions on Visualization and Computer Graphics 28.10 (2022): 3428-3440.
[7] Holme, Petter, and Jari Saramäki. "Temporal networks." Physics reports 519.3 (2012): 97-125.
[8] Simonetto, Paolo, Daniel Archambault, and Stephen Kobourov. "Event-based dynamic graph visualisation." IEEE Transactions on Visualization and Computer Graphics 26.7 (2018): 2373-2386.
[9] Arleo, Alessio, Silvia Miksch, and Daniel Archambault. "Event‐based Dynamic Graph Drawing without the Agonizing Pain." Computer Graphics Forum 41.6 (2023): 226-244.
[10] Bach, Benjamin, et al. "A review of temporal data visualizations based on space-time cube operations." Eurographics conference on visualization. 2014.
Details
- Supervisor
-
Alessio Arleo
- Secondary supervisor
-
Fernando Paulovich
- Interested?
- Get in contact