PaperlayerView exact revision on arXiv

Source-linked AI summary

NDlib: a Python Library to Model and Analyze Diffusion Processes Over Complex Networks

Giulio Rossetti, Letizia Milli, Salvatore Rinzivillo, Alina Sirbu, Fosca Giannotti, Dino Pedreschi

arXiv:1801.05854v1cs.SI

TL;DR

Diffusion studies have many available tools, making it difficult for users to find one suited to their task and expertise. NDlib combines a diffusion-simulation library with remote execution and visual interfaces; in the tested scenario, it completed SIR runs one order of magnitude faster than two direct competitors.

  • Problem

    The range of available tools makes it difficult and time-consuming to identify a diffusion tool suited to a user's task and expertise.

    Source: §1 · p. 1

  • Method

    NDlib provides a modular diffusion-simulation framework with a Python library, remote experiment server, and visual interface.

    Source: §1 · p. 1, §3.2 · p. 5, §3.6 · p. 8

  • Results

    In the tested scenario, NDlib completed SIR runs one order of magnitude faster than ComplexNetworkSim and Nepidemix.

    Source: §4.2.2 · p. 15

  • Takeaways & Limitations

    Its implemented models and extensibility make NDlib a candidate for comparing diffusion schemes beyond classical compartmental models.

    Source: §5 · p. 15

    The authors caution that library comparisons are not exhaustive because results depend on model differences, library design, and programming language.

    Source: §4.2.2 · p. 14

Abstract

from arXiv · show

Nowadays the analysis of dynamics of and on networks represents a hot topic in the Social Network Analysis playground. To support students, teachers, developers and researchers in this work we introduce a novel framework, namely NDlib, an environment designed to describe diffusion simulations. NDlib is designed to be a multi-level ecosystem that can be fruitfully used by different user segments. For this reason, upon NDlib, we designed a simulation server that allows remote execution of experiments as well as an online visualization tool that abstracts its programmatic interface and makes available the simulation platform to non-technicians.

1 Introduction

NDlib addresses the difficulty of choosing among diffusion tools by offering a framework for modeling and studying diffusion over complex networks. Its library, remote experiment server, and visual interface serve both technical and nontechnical users.

1 Introduction

  • The abundance of diffusion tools makes it hard and time-consuming for users to identify one suited to their task and expertise.Source: §1 · p. 1
  • NDlib is a framework for modeling, simulating, and studying diffusive phenomena over complex networks.Source: §1 · p. 1
  • NDlib targets both technical and nontechnical users through a programmatic interface and a web-based visual interface.Source: §1 · pp. 1–2
  • Its experiment server supports controlled exploratories and separates experiment definition from execution.Source: §1 · p. 2
  • NDlib aims to address limitations of existing libraries, including their support for dynamic network topologies, while reducing usage complexity.Source: §1 · p. 2

2 Dynamics On and Of Networks

The section introduces diffusion processes and network models that capture change over time. It distinguishes epidemic and opinion dynamics, and contrasts temporal networks with snapshots, whose choice of time window can affect subsequent analysis.

2 Dynamics On and Of Networks

  • Network analysis historically gave little attention to time, while human-generated traces have made time-aware network data increasingly available.Source: §2 · p. 2

2.1 Network Diffusion

  • Epidemic and spreading processes and opinion dynamics share enough features to be modeled within a common framework.Source: §2.1 · p. 2

2.1.1 Epidemics and Spreading

  • Epidemic spread does not require active participation, whereas information and idea diffusion depends on individual choices.Source: §2.1.1 · pp. 2–3

2.1.2 Opinion Dynamics

  • Opinion models represent individuals as agents whose states change through neighbor interactions and may oscillate among possible values.Source: §2.1.2 · p. 3

2.2 Time-Evolving Networks

  • Dynamic networks represent nodes and edges changing over time, and the paper uses Dynamic Network as an umbrella term for several evolving-network formalisms.Source: §2.2 · p. 3

2.2.1 Dynamic Network Models

  • Temporal networks track node and edge appearances and disappearances without temporal aggregation, preserving moment-by-moment system status.Source: §2.2.1 · p. 3
  • Snapshot graphs partition network history into ordered static graphs, but the chosen window size can affect subsequent analysis.Source: §2.2.1 · p. 4

3 NDlib: Network Diffusion Library

NDlib is organized as a Python library, a remote experiment server, and a visual interface for a broad user base. Its models use discrete-time agent-based iterations and a shared configuration interface for defining simulations.

3 NDlib: Network Diffusion Library

  • NDlib combines a Python core, a RESTful remote experiment server, and a web-oriented visual interface to serve users with different backgrounds.Source: §3 · p. 4

3.1 Library Rationale

  • NDlib models diffusion as a discrete-time agent-based process that updates node states by applying model rules at each iteration.Source: §3.1 · p. 4
  • A simulation combines a network, a diffusion model, and its configuration and initial state, with a shared interface across models.Source: §3.1 · pp. 4–5
  • The configuration can specify model parameters, node or edge attributes, and the initial state of the process.Source: §3.1 · pp. 4–5
  • Simulation output can be requested in batches or one iteration at a time, with each iteration reporting nodes whose status changed.Source: §3.1 · p. 5

3.2 Visualization Facilities

NDlib provides visualizations for tracking diffusion over time and comparing model executions. It also supports parallel runs with varying initial infected nodes and percentile ranges for assessing model stability.

3.2 Visualization Facilities

  • Bokeh and Matplotlib provide web-oriented and print-oriented visualization contexts, with Bokeh using multiplots instead of overlaying multiple trends.Both follow the same programmatic plotting template.Source: §3.2 · p. 5
  • NDlib offers Diffusion Trend plots for class distributions and Diffusion Prevalence plots for changes in class node counts at each iteration.The plots use model metadata and simulation results to generate labels, headings, and parameter values independent of the specific model.Source: §3.2 · p. 5
  • Comparison plots extend trend and prevalence views to compare selected statuses across multiple models run on the same network.Figure 1 shows comparisons for the Infected class across SI and SIR models.Source: §3.2 · p. 5, Figure 1 · p. 6

3.3 Model Parallel Executions

  • Parallel runs vary the initial infected nodes across executions of the same model and network, specified by a percentage or explicit node sets.When a percentage is used, nodes are sampled independently for each execution.Source: §3.3 · p. 6
  • Visualizations of multiple runs show average trend lines with a user-defined percentile range to help assess model stability.Figure 2 illustrates multiple SIR executions with inter-quartile ranges.Source: §3.3 · p. 6

3.4 Dynamic Network Support

NDlib supports diffusion on dynamic network topologies through DyNetX and dynamic versions of classic epidemic models. DyNetX represents changing edges over time while retaining compatibility with NetworkX graph facilities.

3.4 Dynamic Network Support

  • NDlib introduces DyNetX and dynamic diffusion models so users can describe and simulate diffusion on changing network topologies.Dynamic networks matter because flattening a topology can overestimate connections and speed spreading, while sparse time-evolving structures can produce different outcomes.Source: §3.4 · p. 6

3.4.1 DyNetX Rationale

  • DyNetX extends NetworkX graph classes to support temporal networks and snapshot graphs through one interface, with conversion to NetworkX graphs when flattened or sliced.The design balances compact dynamic-graph descriptions with a Pythonic interface and avoids reimplementing a graph model.Source: §3.4.1 · p. 7
  • Dynamic edges are represented by presence intervals, and the data structure size is O(|E| * |T|) without particularly affecting the standard NetworkX graph model.Here |E| is the flattened edge-set cardinality and |T| the timestamp-set cardinality.Source: §3.4.1 · p. 7

3.4.2 Diffusive Phenomena in Dynamic Networks.

  • DynamicDiffusionModel separates simulation rules for snapshot graphs from those for temporal networks through execute_snapshots() and execute_iterations().The class also defines initialization through init(self, graph).Source: §3.4.2 · p. 7
  • NDlib implements dynamic SI, SIS, and SIR models for both snapshot graphs and temporal networks, retaining the existing configuration strategy and visualization facilities.Source: §3.4.2 · p. 7

3.5 Extensibility: User Defined Models

NDlib lets users extend its diffusion models and run experiments through a REST server. The server organizes simulations as experiments, while its API and web documentation support configuring and executing them remotely.

3.5 Extensibility: User Defined Models

  • A user-defined diffusion model extends DiffusionModel and implements initialization and an iteration step that defines node status-change rules.Model metadata describes parameters and node statuses, supporting configuration checks and customized visualizations; iterations apply synchronous updates from a shared initial configuration.Source: §3.5 · p. 8

3.6 Experiment Server

  • NDlib-REST separates experiment definition from execution by providing a RESTful server queryable through API calls.An experiment contains a network and one or more configured models, and tracks the simulation definition and current diffusion status.Source: §3.6 · p. 8, §3.6.1 · p. 8
  • The REST workflow creates an experiment token, loads a network and models, optionally configures node or edge parameters, and executes simulation steps.Users may also reset an experiment and change its models or network; experiments can be explicitly destroyed or expire after an administrator-configured window.Source: §3.6.1 · p. 8

3.6.2 Querying NDlib-REST

  • The online documentation page can be used to test endpoints while configuring and running experiments.Source: §3.6.1 · p. 8, Figure 3 · p. 9
  • NDlib-REST organizes JSON endpoints into categories, including experiments, exploratories, networks, models, and iterators.Exploratories let server owners publish preset scenarios, such as networks and initial states, for users to explore with configured models.Source: §3.6.2 · pp. 8–9

3.7 Web Platform

NDlib-Viz provides a web interface intended to help non-technicians design, configure, and run epidemic simulations. Its linked visualizations connect network states with model plots, while a decoupled client architecture communicates with the REST server.

3.7 Web Platform

  • NDlib-Viz is designed to let non-technicians design, configure, and run epidemic simulations without programming-language knowledge.The web application can run with a local or remote NDlib-REST installation and is used in a university Social Analysis course.Source: §3.7 · p. 10
  • The interface guides users through creating a network and models, running iterations, and exploring linked displays of node states and model results.Selecting a time instant in the charts updates the network view to show node statuses at that time.Source: §3.7 · p. 11

3.7.1 Architecture

  • The visualization framework is a single-page JavaScript and HTML5 application that separates the simulation engine from the visual interface.Its network view uses an HTML5 Canvas for efficient updates.Source: §3.7.1 · p. 11
  • A Model-Control-View design centralizes experiment status and REST communication in the model, with asynchronous server calls updating the interface when responses arrive.Source: §3.7.1 · p. 11

4 Comparative Analysis

The section surveys existing diffusion tools and compares selected libraries qualitatively and through common-model runtimes. It reports feature differences and runtime comparisons while noting limits on what those benchmarks establish.

4.1 NDlib Competitors

  • The review samples epidemic simulators as well as single-disease tools and general simulation environments, rather than attempting an exhaustive inventory.The authors describe the competitor review as selective and focused on resources they considered to have interesting facilities.Source: §4 · p. 11, §4.1 · p. 13

4.2 Comparisions

  • The comparison combines feature-based qualitative assessment with quantitative strategies including scalability and common-model running times.The quantitative comparison uses a selected subset of libraries, chosen partly for documentation and a shared approach-definition schema.Source: §4.2 · p. 13, §4.2.1 · p. 13, §4.2.2 · pp. 14–15

4.2.1 Qualitative

  • Among surveyed libraries, only NDlib natively supports opinion models; three support dynamic topologies, with NDlib the only active project among them.About half provide visualization facilities or platforms for non-developers, and only NDlib and GLEaMviz offer an experiment server.Source: §4.2.1 · p. 14

4.2.2 Quantitative

  • Quantitative comparisons are constrained because external graph implementations determine scalability limits, so scalability tests benchmark network libraries rather than diffusion functionality.The authors identify scalability and common-model runtime as two possible comparison strategies.Source: §4.2.2 · p. 14
  • NDlib runs one order of magnitude faster than the Python, NetworkX-based competitors, while EpiModel is faster without a wide gap.The comparison ran SIR with identical parameters on the same network class, varying node count; Table 2 reports the runtimes.Source: Table 2 · p. 15, §4.2.2 · p. 15

5 Conclusions and Future Works

NDlib combines a standalone library, a RESTful simulation service, and a visualization tool to support a heterogeneous audience analyzing diffusion on complex networks. Its integration with DyNetX supports dynamic network topologies, while the framework trades efficiency against ease of use through its reliance on NetworkX.

5 Conclusions and Future Works

  • NDlib combines a standalone library, RESTful simulation service, and visualization tool for a heterogeneous audience.The paper presents it as useful for comparing diffusion schemas beyond classical SI, SIS, and SIR models.Source: §5 · p. 15
  • NDlib is among the few libraries that support defining and analyzing diffusion on dynamic network topologies through DyNetX.DyNetX provides dynamic network modeling facilities and integrates with NetworkX.Source: §5 · p. 15
  • Among reviewed tools, EpiModel appears to offer comparable diffusion analytics in library, execution-time, and visualization facilities.NDlib is tailored to a wider audience and supports setting up remote experimental services for educational, model-testing, and massive-network contexts.Source: §5 · p. 15
  • NDlib's scalability and efficiency are tied to NetworkX, while several C/C++-based graph libraries can handle larger networks.The authors frame NetworkX as a foundation for reaching a widespread, diversified audience.Source: §5 · pp. 15–16
  • Future work plans to add more NDlib models, extend DyNetX analytical methods, and integrate NDlib-REST into a visual simulation platform.Source: §5 · p. 16

Appendix: Diffusion Methods implemented in NDlib

The appendix introduces the diffusion algorithms implemented in NDlib v3.0.0, covering epidemic approaches and opinion dynamics.

Appendix: Diffusion Methods implemented in NDlib

  • NDlib v3.0.0 exposes several network diffusion models covering epidemic approaches and opinion dynamics.The appendix proceeds to list the implemented algorithms.Source: Appendix: Diffusion Methods… · p. 17

A Static Epidemic Models.

NDlib's static epidemic methods include classic compartmental models, behavioral threshold variants, and other spreading rules. Their transition mechanisms range from probabilistic infection and recovery to adoption based on profiles, peer influence, or activation attempts.

A Static Epidemic Models.

  • SI, SIR, SIS, SEIS, and SEIR model infection with transitions S → I, S → I → R, S → I → S, S → E → I → S, and S → E → I → R, respectively.Their described transitions use probabilities for infection and, where applicable, exposure, recovery, or return to susceptibility.Source: A Static Epidemic Models · p. 17
  • SWIR adds a weakened state: susceptible neighbors may become infected or weakened, and weakened neighbors may become infected.Source: A Static Epidemic Models · p. 17
  • Threshold adoption depends on the infected-neighbor percentage exceeding a node threshold, while Kertesz Threshold adds blocked nodes and spontaneous adoption.Source: A Static Epidemic Models · p. 17
  • Independent Cascades gives each newly active node one probabilistic attempt to activate each inactive neighbor, and the process ends when no further activations are possible.Successful activations take effect in the next step; a node makes no later attempt on that same neighbor.Source: A Static Epidemic Models · p. 17
  • Node Profile bases adoption on each susceptible node's interests without peer pressure; Node Profile-Threshold adds peer influence when infected neighbors exceed a threshold.Source: A Static Epidemic Models · pp. 17–18

B Dynamic Epidemic Models.

NDlib implements dynamic versions of classic compartmental models using DyNetX graph structures. The described models adapt SI, SIS, and SIR formulations to evolving network topologies.

B Dynamic Epidemic Models.

  • NDlib implements dynamic network versions of SI, SIS, and SIR using DyNetX graph structures, for snapshot-based as well as temporal networks.Source: B Dynamic Epidemic Models · p. 18
  • DynSI carries the prior day's infected set into the current snapshot while using the current interaction graph, allowing node sets to differ between snapshots.Source: B Dynamic Epidemic Models · p. 18
  • DynSIS adapts S → I → S to an evolving snapshot topology and assumes a directed or undirected dynamic network.Source: B Dynamic Epidemic Models · p. 18
  • DynSIR adapts S → I → R to an evolving snapshot topology and assumes a directed or undirected dynamic network.Source: B Dynamic Epidemic Models · p. 18

C Opinion Dynamic Models.

The section describes four discrete opinion-dynamics models and a cognitive model with continuous risk-perception opinions. Their update rules range from neighbor copying to group influence and external information.

C Opinion Dynamic Models.

  • The Voter model has each individual copy a random neighbor, and on a complete network the population reaches consensus with probability for +1 equal to its initial share.It was introduced to analyze species competition and later applied to elections.Source: C Opinion Dynamic Models · p. 18
  • In Snajzd, agreeing neighboring agents influence all their neighbors; the model converges to one of two agreeing states according to initial up-spin density, with a transition at 50%.The original model uses a 2D lattice; NDlib also implements it on complex networks.Source: C Opinion Dynamic Models · p. 18
  • Q-Voter selects q neighbors to influence a target when they agree; NDlib implements ϵ = 0, and q = 1 or 2 recovers the Voter or Sznajd model, respectively.For q > 3, the described transitions can include an intermediate regime where the final state depends on the initial condition.Source: C Opinion Dynamic Models · p. 18
  • Majority Rule updates a randomly selected group on a complete graph to its majority opinion; when an even-sized group ties, a bias favors +1.Group size may be fixed or sampled from a specified distribution; the tie-breaking bias is inspired by social inertia.Source: C Opinion Dynamic Models · p. 18
  • Cognitive Opinion Dynamics represents risk perception continuously and updates it through neighbors and institutional information using four fixed individual variables.The variables are risk sensitivity, tendency to inform others, trust in institutions, and trust in peers; the model was reported to reproduce real situations, with risk sensitivity more important than institutional trust in evaluating risk.Source: C Opinion Dynamic Models · p. 18
Loading 1801.05854v1…