Information Propagation in
Complex Networks


Structures and Dynamics

Marcus Märtens

NAS logo Network
Architectures and
Services 		TU Delft logo

What is information propagation?

I tell you something you did not know before.

Classical information theory


Claude Shannon (1916-2001)
father of information theory

What if there are more receivers?

... that can be senders as well?

... with different channels?

What if there are really a lot more?

Two aspects of information propagation

Structure

networks: nodes and links

answers: Who can exchange information?

Dynamics

change over time
models, rules and algorithms

answers: How is information exchanged?

Ch 4: Computer worms

Structure

  • IP4 address space
  • nodes: computers, hosts
  • links: Internet

Dynamics

  • worm infects host
  • worm sends copies to random addresses
  • administrator removes infection

Result

Long-term evolution of computer worms can be described by time-dependent epidemic model

Ch 3: Human brains

Structure

  • MEG measurements
  • nodes: brain regions
  • links: increased information flow

Dynamics

  • microscopic: neuronal activity
  • macroscopic: information flow between brain regions

Result

Clusters of small networks provide a spatial meaningful high-order organization of the brain.

Ch 2: Antisocial behavior

Structure

  • short-term: 5vs5 ad-hoc matches
  • long-term: player networks
  • nodes: players
  • links: defined by teams

Dynamics

  • game interactions (killing avatars)
  • text-chat between competing teams
  • text-chat between members of a single team

Result

Detection system for antisocial behavior.

Ch 5: Superinfection

  • What happens when two propagations processes compete?
  • Can we fight a "bad" computer worm by spreading a "good" computer worm?

Theoretical models for propagation of one virus: epidemic model
Extension to more viruses: superinfection model

Result

Conditions for stable coexistence of both viruses and for extinctions exist.

Ch 6: Learning network structures

  • The structure of the network is essential for any propagation!
  • Formulas relate structural network properties with each other, for example:

$\blacktriangle = \frac{1}{6} \sum\limits_{i = 1}^{N} \lambda_i^3$

  • Can a smart machine come up with formulas by studying networks?

Closing thoughts

  • Did I tell you something you did not know before?
  • Good! Information propagation works.
  • Feel free to propagate this information.

Many thanks to all my collaborators, co-authors and supporters!