C. Magnien

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Algorithms for the analysis of interaction streams
Clémence Magnien
work in collaboration with Tiphaine Viard, Matthieu Latapy, Pierluigi
Crescenzi, Andrea Marino, Fabien Tarissan, Frédéric Simard, Mehdi
Naima, . . .
ComplexNetworks(.fr)
LIP6 (CNRS, Sorbonne Université)
clemence.magnien@lip6.fr

June 5-6, 2023
logobas1/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Context – Complex Networks
computer science: internet, web, peer-to-peer, usages, etc.
social sciences: collaboration, friendship, exchanges, economics,
etc.
biology: brain, genes, proteins, ecosystems, etc.
linguistics: synonyms, co-occurrences, etc.
transportation: roads, air, electricity, etc.
etc, etc

relation networks
Very different contexts
No formal definition
Common questions
C. Magnienlogobas2/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas3/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas4/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Centrality in graphs
Goal
Capture node importance
Why?
Interesting web page
Understand network structure
Network reliability...
Three main notions
DegreeCloseness centrality
Betweenness centrality
C. Magnienlogobas5/121Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Centrality in graphs
Goal
Capture node importance
Why?
Interesting web page
Understand network structure
Network reliability...
Three main notions
DegreeCloseness centrality
Betweenness centrality
C. Magnienlogobas5/121Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Degree centrality
Degree of a node
its number of links
more links = more importantContext
Friendships

C. Magnien

Marketing...

logobas6/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Closeness centrality
Idea
closer to other nodes = more important

Formally
C (u) =

Xv ∈V ,v 6=u1
d(u, v )(other variants exists)
logobasC. Magnien

7/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Closeness centrality – context

Why?
Epidemics
Transportation networks...

logobasC. Magnien

8/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Betweenness centrality
Idea
is on shortest paths between many nodes = more important

Formally
B(u) =

Xv ,w ∈V ,v ,w 6=uσ(v , w , u)σ(v , w )σ(v , w ): # of shortest paths between v and w
σ(v , w , u): # of shortest paths between v and w involving u logobas
C. Magnien

9/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Betweenness centrality – context

Why?
Identifiy communities/network robustness
Influence/power in collaboration networks...

logobasC. Magnien

10/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

How do we compute those?

Base brick
Breadth-First Search (BFS) to compute the distancefrom one source node
to all other nodes
Complexity O(m)n: number of nodes
m: number of links

logobasC. Magnien

11/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Algorithm
noend 1 Breadth-first search algorithm
1: procedure BFS
Input: Graph G , source node s.
2:
Q ← Empty queue (FIFO)
3:
Add s to Q4:d ← array initialized to ∞5:
while Q is not empty do
6:Remove u from Q
7:for v neighbour of u do
8:
if d[v ] = ∞ then9:d[v ] ← d[u] + 1
10:
Add v to Q
C. Magnienlogobas12/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Closeness computation

For one node
one BFS : O(m)For all nodes
one BFS per node : O(nm)logobasC. Magnien

13/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Betweenness computation
Naive version
For one node u:
one BFS to compute distances from u to all other vertices
one BFS from each other node v to mark nodes on shortest
paths between u and v−→ O(nm) for one node
Brandes’ algorithmO(nm) for all vertices
logobasC. Magnien

14/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Betweenness computation
Naive version
For one node u:
one BFS to compute distances from u to all other vertices
one BFS from each other node v to mark nodes on shortest
paths between u and v−→ O(nm) for one node
Brandes’ algorithmO(nm) for all vertices
logobasC. Magnien

14/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

What is PageRank?

C. Magnien

PageRank is an algorithm used by Google Search to rank websites intheir search engine results.
It counts the number and quality of links to a page.
The underlying assumption is that an important website is likely toreceive links from other important websites.

logobas15/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Eigenvector

Definition: given an n by n matrix M a vector A is an eigenvectorof M if it has at least one non-zero value and if there exists a
scalar λ ∈ R such that
M ×A=λ×A
Definition: a top/dominant eigenvector is an eigenvector A suchthat its associated eigenvalue λ has maximum absolute value.

C. Magnienlogobas16/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

PageRank Computation
Definition: transition matrix T :n by n matrix
for each directed edge (u, v ), Tvu = d out1(u)Definition: the PageRank vector P is given by:
P = (1 − α) × T × P + α × I

I : vector with entries = n1 .

P is eigenvector ofα

n n×n + (1 − α)TlogobasC. Magnien

17/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Other spectral centrality measures

PageRank
Eigenvector centrality
HITS
Katz centrality
Based on walks in the graph

C. Magnienlogobas18/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Centrality in practice

Why different notions?
Different notions of importanceNo ground truth! (in general)logobasC. Magnien

19/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas20/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Taking time into account
I won’t talk about static graphs.
As time passes
new web pages are created and links change
we meet new people
we talk to different persons
we buy things...
How to take this into account?
logobasC. Magnien

21/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Relations vs. Interactions
relations (like friendship)
interactions(like face-to-face contacts)
evolution of relations(like new friends)
Many interesting links between the two.
Interactions important for: Recommender systems, epidemiology,
anomaly detection, message passing, . . .

logobasC. Magnien

22/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Relations vs. Interactions
relations (like friendship)−→ graph/networks
evolution of relations(like new friends)−→ dynamic graphs/networks

interactions(like face-to-face contacts)−→ ?

Many interesting links between the two.
Interactions important for: Recommender systems, epidemiology,
anomaly detection, message passing, . . .
Characteristics: speed of path vs speed of link evolution?
Framework for describing interactions?
C. Magnienlogobas22/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

definition of link streams

C. Magnien

Link stream S = (T , V , E )T : time interval, V : node set
E ⊆T ×V ⊗V(t, uv ) ∈ E ⇔ u and v interact at time t

a
b
c
d

0

2

4

6

8 timeE = [1, 3] × ab ∪ [8, 8] × ab ∪ [2, 3] × bd ∪ [6, 9] × bc
logobas23/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Related work: Describe structure and dynamics?
a
b
c
d
e
f
0

2

4

6

8

10

12

14

16

18

20

22 timetime slices→ graph sequencelogobasC. Magnien

24/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Related work: Describe structure and dynamics?
a
b
c
d
e
f
0

2

4

6

8

10

12

14

16

18

20

22 timetime slices→ graph sequence

information loss
what slices? logobas
C. Magnien

24/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Related work: Describe structure and dynamics

C. Magnien

a
b
c
d
e
f
0

2

4

6

8

10

12

14

16

18

20

22 timetemporal graphs

2−6
18−20

4−8
12−16

...

4−6

TVG

10−12
22−24
8−10
12−14

6−8
20−22
12−22

0−4
10−12
20−24

lossless but graph-oriented+ other more specific contributions logobas

25/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Related work: Describe structure and dynamics
a
b
c
d
e
f
0

2

4

6

8

10

12

14

16

18

20

22 timetemporal graphs

2−6
18−20

4−8
12−16

...

4−6

TVG

10−12
22−24
8−10
12−14

6−8
20−22
12−22

0−4
10−12
20−24

lossless but graph-oriented+ other more specific contributions logobas
C. Magnien

25/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

what we propose
deal with the stream directly

Approachvery careful definition of the most basic concepts,→ building blocks for higher-level concepts+ ensure consistency with graph theory+ ensure classical relations are preserved
logobasC. Magnien

26/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Note on different models
Link streams, time varying graphs (TVG), temporal networks, . . .
FormallySame power of representation

Intuition
Two possible cases
evolving graphsequence of temporal links
logobasC. Magnien

27/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas28/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Paths in link stream
a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

Path from (α, u) to (ω, v ): (t0 , u0 , v0 ), (t1 , u1 , v1 ), . . . (tk , uk , vk ):u0 = u, vk = v
t0 ≥ α, t1 ≤ ω(t1 , ui vi ) ∈ E
ti ≤ ti+1

C. Magnienlogobas29/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Paths in link stream
a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

Path from (α, u) to (ω, v ): (t0 , u0 , v0 ), (t1 , u1 , v1 ), . . . (tk , uk , vk ):Path characteristics
k: path length

C. Magnien

tk : arrival timetk − t0 : path duration

logobas29/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Some remarks

I will consider in generalinstantaneous links only
no two links at the same time
Everything can be extended to the general caselogobasC. Magnien

30/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Path examples
a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

Paths are not symmetrical
No path from d to alogobasC. Magnien

31/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Path examples
a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

Paths are not transitive
No path from a to clogobasC. Magnien

31/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Path examples
a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

Different paths exist between two nodes
logobasC. Magnien

31/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Path examples
a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

Path existence depends on starting timelogobasC. Magnien

31/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Shortest paths
a
b
c
d
e
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Different paths from (1, a) to (7, e)
Length 4 – Length 2 – Length 1: shortest path

C. Magnien

We are not always willing to wait for the shortest path!
logobas32/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Shortest paths
a
b
c
d
e
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Different paths from (1, a) to (7, e)
Length 4 – Length 2 – Length 1: shortest path
We are not always willing to wait for the shortest path!
logobasC. Magnien

32/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Shortest paths
a
b
c
d
e
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Different paths from (1, a) to (7, e)
Length 4 – Length 2 – Length 1: shortest path
We are not always willing to wait for the shortest path!
logobasC. Magnien

32/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Foremost path
a
b
c
d
e
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Different paths from (1, a) to (7, e)
Arrival time 6 – Arrival time 7 – Arrival time 5: foremost path

C. Magnienlogobas33/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Fastest path
a
b
c
d
e
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Different paths from (1, a) to (7, e)Duration 4 – Duration 3 – Duration 1: fastest path

C. Magnienlogobas34/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

No best definition

Relevance for different questions
Foremost paths: quick information/virus spread
Shortest: more robust paths?
Fastest: identify key instants?
We will focus on foremost pathlogobasC. Magnien

35/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Foremost path

Time to reach
Tt (u, v ) = ta − t, with ta :earliest arrival time of a path from u starting at time t to v

Foremost path
Path realizing the time to reachlogobasC. Magnien

36/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas37/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

From path to centrality

How do we go from temporal paths to centrality definitions?
How to take into account path starting and ending times?
Incomplete review of exising definitions

logobasC. Magnien

38/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

From path to centrality

How do we go from temporal paths to centrality definitions?
How to take into account path starting and ending times?
Incomplete review of exising definitions

logobasC. Magnien

38/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

First approach: snapshots[Uddin et al, 2013]
a
b
c
d
e
f
0

2

4

6

8

10

12

14

16

18

20

22 timeAdvantages and drawbacks
Works for any static centrality metrics
Takes data evolution into accountInformation loss
Which snapshot size?
Does not consider all paths
C. Magnienlogobas39/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Temporal paths, first approach[Nicosia et al, 2013]choose a notion of optimal path/centrality
compute centrality/for each nodefor paths starting at time 0
Advantages and drawbacks
uses temporal paths
considers only paths that occur early in the dataset
logobasC. Magnien

40/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Temporal paths, first approach[Nicosia et al, 2013]choose a notion of optimal path/centrality
compute centrality/for each nodefor paths starting at time 0
Advantages and drawbacks
uses temporal paths
considers only paths that occur early in the dataset
logobasC. Magnien

40/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Temporal paths, second approach

Compute centrality values
For all starting times
Aggregate into a single value per nodelogobasC. Magnien

41/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Temporal paths, second approach

Compute centrality values
For all starting times
Aggregate into a single value per nodelogobasC. Magnien

41/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Spectral centrality measures

Possible to extend spectral measures.
Need adjacency/transition matrices!
combine adjacency matrices at different time steps
block matrix: rows/columns correspond to temporal vertices

logobasC. Magnien

42/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Temporal closenessTime to reach
Tt (u, v ) = ta − t, with ta :earliest arrival time of a path from u starting at time t to v

Temporal closeness at time t
Ct (u) =

X
v 6=u

1
Tt (u, v ) + 1
Why +1?
logobasC. Magnien

43/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Temporal closenessTime to reach
Tt (u, v ) = ta − t, with ta :earliest arrival time of a path from u starting at time t to v

Temporal closeness at time t
Ct (u) =

X
v 6=u

1
Tt (u, v ) + 1
Why +1?
logobasC. Magnien

43/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

ExampleCloseness of a
1

a

0.8

b

0.6

c

0.4

0.2

|
1

|
2

|
3

|
4

0

1

1.5

2

2.5

3

3.5

4

1
(4−x)

logobasC. Magnien

44/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

ExampleCloseness of a
1.6

a

1.4
1.2

b

1
0.8

c

0.6
0.4

|
1

|
2

|
3

|
4

0.2
0

1

1.5

2

2.5

3

3.5

4

logobasC. Magnien

44/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Aggregate in a single value
Ct (u): one value for each t −→ what is an important node?
Several possibilities:
maximum value
average value
time during which it has a high rank...
1
C (u) =
ω−αZ ωCt (u)dt
αlogobasC. Magnien

45/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Aggregate in a single value
Ct (u): one value for each t −→ what is an important node?
Several possibilities:
maximum value
average value
time during which it has a high rank...
1
C (u) =
ω−αZ ωCt (u)dt
αlogobasC. Magnien

45/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas46/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in time

Compute earliest arrival times from:a single source node s
to all other nodes
for all starting times
By considering each link once
Complexity O(m)logobasC. Magnien

47/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in time
s
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

|
7

logobasC. Magnien

48/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in times(0,1,1)

b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Triple (t1 , t2 , ta)
For t, t1 < t ≤ t2 , earliest arrival time is ta
logobasC. Magnien

48/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in times(0,1,1)

b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Triple (t1 , t2 , ta)
For t, t1 < t ≤ t2 , earliest arrival time is ta
logobasC. Magnien

48/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in times(0,1,1)bc(0,1,2)

d
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Triple (t1 , t2 , ta)
For t, t1 < t ≤ t2 , earliest arrival time is ta
logobasC. Magnien

48/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in timesb(0,1,1)c(0,1,3)d(0,1,2)
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Triple (t1 , t2 , ta)
For t, t1 < t ≤ t2 , earliest arrival time is ta
logobasC. Magnien

48/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in timesb(0,1,1), (1,4,4)c(0,1,3)d(0,1,2)
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Triple (t1 , t2 , ta)
For t, t1 < t ≤ t2 , earliest arrival time is ta
logobasC. Magnien

48/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in timesb(0,1,1), (1,4,4)c(0,1,3)d(0,1,2)
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Triple (t1 , t2 , ta)
For t, t1 < t ≤ t2 , earliest arrival time is ta
logobasC. Magnien

48/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in timesb(0,1,1), (1,4,4)c(0,1,3), (0,4,5)

d(0,1,2)
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Triple (t1 , t2 , ta)
For t, t1 < t ≤ t2 , earliest arrival time is ta
logobasC. Magnien

48/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in timesb(0,1,1), (1,4,4)c(0,1,3), (0,4,5)

d(0,1,2), (0,4,6)
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Triple (t1 , t2 , ta)
For t, t1 < t ≤ t2 , earliest arrival time is ta
logobasC. Magnien

48/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 1: going forward in timesb(0,1,1), (1,4,4)c(0,1,3), (0,4,5)

d(0,1,2), (0,4,6)
|
1

|
2

|
3

|
4

|
5

|
6

|
7

Triple (t1 , t2 , ta)
For t, t1 < t ≤ t2 , earliest arrival time is ta
logobasC. Magnien

48/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Algorithm (assumes edges are directed)
1: procedure Earliest arrival times

9:

for x ← 1 to |V | do τ [x] = [(tα − 2, tα − 1, ∞)]while there are other edges to be read dolet e ← (x, y , t) be the next edge
τ [s] ← (t − 1, t, t − 1)(lx , rx , ax ) ← last elem. of τ [x](ly , ry , ay ) ← last elem. of τ [y ]if rx > ry thenappend (ry , rx , t) to τ [y ]10:Return τ

2:
3:
4:
5:
6:
7:
8:

C. Magnienlogobas49/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 2: going backwards

C. Magnien

v
w
x
d
|
1

|
2

|
3

|
4

|
5

|
6

logobas50/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 2: going backwardsv(4,6,4)

w
x
d
|
1

|
2

|
3

|
4

|
5

|
6

Triple (t1 , t2 , ts ),For arrival time t, t1 < t ≤ t2 , latest strating time is ts
logobasC. Magnien

50/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 2: going backwardsv(4,6,4)w
x(3,6,3)

d
|
1

|
2

|
3

|
4

|
5

|
6

Triple (t1 , t2 , ts ),For arrival time t, t1 < t ≤ t2 , latest strating time is ts
logobasC. Magnien

50/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 2: going backwardsv(4,6,4)w(3,6,2)x(3,6,3)

d
|
1

|
2

|
3

|
4

|
5

|
6

Triple (t1 , t2 , ts ),For arrival time t, t1 < t ≤ t2 , latest strating time is ts
logobasC. Magnien

50/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 2: going backwardsv(4,6,4)w(3,6,2)x(3,6,3)

d
|
1

|
2

|
3

|
4

|
5

|
6

Triple (t1 , t2 , ts ),For arrival time t, t1 < t ≤ t2 , latest strating time is ts
logobasC. Magnien

50/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 2: going backwardsv(4,6,4), (3,4,1)

w(3,6,2)x(3,6,3)

d
|
1

|
2

|
3

|
4

|
5

|
6

Triple (t1 , t2 , ts ),For arrival time t, t1 < t ≤ t2 , latest strating time is ts
logobasC. Magnien

50/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Two basic algorithmic ideas – 2: going backwardsv(4,6,4), (3,4,1), (0,3,0)w(3,6,2)x(3,6,3)

d
|
1

|
2

|
3

|
4

|
5

|
6

Triple (t1 , t2 , ts ), (t3 , t4 , ts2 )For arrival time t, t1 < t ≤ t2 , latest strating time is ts
For starting time t 0 , ts2 < t 0 ≤ ts 2, earliest arrival time is t1

C. Magnienlogobas50/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Backward Algorithm (assumes edges are directed)
1: procedure Latest starting times

9:

for x ← 1 to |V | do τ [x] = [(ω + 1, ω + 2, ∞)]while there are other edges to be read dolet e ← (x, y , t) be the next edge
τ [d] ← (t, t + 1, t + 1)
(lx , rx , sx ) ← last elem. of τ [x](ly , ry , sy ) ← last elem. of τ [y ]if ly < lx thenappend (ly , lx , t) to τ [x]10:Return τ

2:
3:
4:
5:
6:
7:
8:

C. Magnienlogobas51/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

Data Structure

Link Stream storage:
list of temporal links, ordered by (increasing or decreasing) time
No need to store stream in memory

logobasC. Magnien

52/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas53/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas54/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Global closeness defition

Overall closeness over time1
C (u) =
ω−αZ ωCt (u)dtαα, ω: fist and last time in the stream

logobasC. Magnien

55/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Example
a
b
c
|
1

|
2

Z 3

1
dx = log 3
4−x

C (a) =
1

|
3

|
4

TODO Histoire de la gestion du dernier triplet
logobasC. Magnien

56/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Algorithm - Closeness (assumes edges are directed)
1: procedure Closeness
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
C. Magnien

for x ← 1 to |V | do τ [x] = (tα − 2, tα − 1, ∞)C ←0for edges (x, y , t), t increasing doτ [s] ← (t − 1, t, t − 1)(lx , rx , ax ) ← τ [x](ly , ry , ay ) ← τ [y ]if rx > ry thena −max(α,l )+1
C ← C + ln ayy −max(α,ryy )+1
τ [y ] ← (ry , rx , t)
for x ← 1 to |V | do (lx , rx , ax ) ← τ [x]−max(α,lx )+1
C ← C + log aaxx −max(α,rx )+1CReturn (ω−α)

logobas57/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Complexity

Above algorithmO(m)Must be run for each node
Global complexity O(nm)Untractable in many cases

logobasC. Magnien

58/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Other approach – sampling

General idea: sample paths randomly
Which paths?
Which complexity?

logobasC. Magnien

59/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Back to graphs
1 BFS: Distances from one node to all others

C. Magnien−→ this node’s closeness
2
1

1
2
1
2

3
logobas60/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Compute the contribution of one node to the others’
closeness

C. Magnien

1/2
1

1
1/2
1
1/2

1/3
logobas61/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Nothing changed?

We must compute the contribution
from all nodes
to all nodes
Global complexity is still O(nm)Must we?

logobasC. Magnien

62/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Nothing changed?

We must compute the contribution
from all nodes
to all nodes
Global complexity is still O(nm)Must we?

logobasC. Magnien

62/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Sampling[Cohen et al 2014]
Reduce computation timecompute the contribution of some nodes
Given u, v
1d(u, v )X
C (v ) =C (u, v )C (u, v ) =u6=v

Given X ⊆ Vn X
C (u, v )|X |logobasu∈X

C. Magnien

63/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Back to linkstreams
Closeness of uZ ω
1
C (u) =Ct (u)dt
ω−α α
Z ωX
1
1
C (u) =ω−α αTt (u, d) + 1
d6=uContribution of d to the closeness of uZ ω11
C (u, d) =dt
ω − α α Tt (u, d) + 1
logobasC. Magnien

64/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Estimation

Random node sample X = {x1 , . . . , xh }hnX
C (u) =C (u, xi )
h
X

i=1

h << nlogobasC. Magnien

65/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Contribution – algorithm
1: procedure Contribution
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
C. Magnien

for x ← 1 to |V | do τ [x] = (ω + 1, ω + 2, ∞); S[x] ← ∞C ←0for edges (x, y , t), t decreasing doτ [d] ← (t, t + 1, t + 1); S[d] ← t(lx , rx , sx ) ← τ [x](ly , ry , sy ) ← τ [y ]if ly < lx thenmin(ω,lx )−t+1
C ← C + ln min(ω,lx )−sx +1
τ [x] ← (ly , lx , t); S[x] ← sx

for x ← 1 to |V | do (lx , rx , sx ) ← τ [x]min(ω,lx )−sx +1−α+1
C ← C + log min(ω,l+ log llxx−sx +1x )−S[x]+1
C
Return (ω−α)

logobas66/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Theoretical result

Theorem
If h = |X | = Θ(log n/2 ), then ∀u,|C (u) − C X (u)| ≤  with high probability

logobasC. Magnien

67/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Choice of h to get a good estimate?
Θ(log n/2 ) in practice?
Choice of ?

logobasC. Magnien

68/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Our approach
1

Choose a sample of h nodes

2

Compute the approximated closeness of all nodes

3

Sort by decreasing approximated closeness and select theK > k top nodes

4

Compute their exact closeness5

Rank them and select the k top nodes
In practice h = K = 1024 works for finding the top 100-nodes

Complexity

C. MagnienO(2048 × m)

logobas69/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas70/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Datasets
Link streams from different contexts
Internet topology
Movie actors
Public transportation
Facebook
Twitter
Linux mailing list
20, 000 ≤ n ≤ 3.5 · 106
80, 000 ≤ m ≤ 16 · 106
logobasC. Magnien

71/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Methodology
Compute exact closeness values
For all datasets except Twitterto evaluate the quality of results
Run approximate method with h = 32, 64, 128, 256, 512, 1024
50 times eachlogobasC. Magnien

72/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Running times

C. Magnien

Name
fant
melb
topo
fbwa
come
linu
all
twit

Nodes
34 46419 49334 76146 952
162 30363 400527 535
3 511 241Edges
87 331
1 098 227
154 842876 993
666 568
1 096 400
3 152 994
16 438 790

exact
1 815
6 258
1 649
12 18429 601
19 313484 906∗ 97 553 304

apx-1024
33
380
47
264
203
317
941
28 449*estimated ∼ 3 years
logobas73/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Accuracy

Compare approximate result to exact
Two ways to evaluate accuracy:
absolute error
relative error
Advantages and drawbacks

logobasC. Magnien

74/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Absolute error
Mean absolute error
Xv|C X (u) − C (u)|/n

One value per experiments −→ 50 values for each value of h
We plot
median25% and 75% quartiles
minimum and maximum
logobasC. Magnien

75/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Absolute error, examples
4

come

·10−4

2.5

fbwa

·10−9

melb

·10−6
6

3.5
2

3
2.5

5

1.5

4

1

3

2
1.5
1

2

0.5

0.5

1
0

0
32

64

128

256

512

1024

32

64

128

256

512

1024

32

64

128

256

512

1024

Average closeness: 6.1 · 10−4 , 5.4 · 10−9 , 2.4 · 10−5
Average error and variability decrease with h.

logobasC. Magnien

76/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Absolute error, examples
4

come

·10−4

2.5

fbwa

·10−9

melb

·10−6
6

3.5
2

3
2.5

5

1.5

4

1

3

2
1.5
1

2

0.5

0.5

1
0

0
32

64

128

256

512

1024

32

64

128

256

512

1024

32

64

128

256

512

1024

Average closeness: 6.1 · 10−4 , 5.4 · 10−9 , 2.4 · 10−5
Average error and variability decrease with h.

logobasC. Magnien

76/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Relative error
For a node u and sample X|C X (u) − C (u)|/C (u)Rank nodes according to closenesssmall rank = high closenessWe study relative error with respect to rank
For each rank i
we are interested in the maximum error observed for all ranks ≤ i.
logobasC. Magnien

77/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Relative error, examples
Maximum and average value over 50 experiments, h = 1024
COME

FBWA

1000

100

100
10
10
1

1
0.1

0.1

0.01
0.01
0.001
0.0001

1

10

100

1000

10000

100000

0.001

1

10

100

1000

10000

Relative error can be quite highIs low for top nodes
Note discussion sur pourquoi les nœuds de faible closeness sontmal estimés, sur le fait qu’une erreur relative > 1 veut dire unecloseness sur estimée, n’arrive que pour le max
C. Magnienlogobas78/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Quality of ranking
How do we compare rankings?
Kendall tau-coefficientC (u1 ), . . . , C (ui ), . . . , C (uj ), . . . , C (un )X
C (u1 ), . . . , C X (ui ), . . . , C X (uj ), . . . , C X (un )nodes ui and uj are concordant if
C (ui ) < C (uj )andC X (ui ) < C X (uj )τ=#concordant pairs − #discordant pairs#pairsWe use a variant that puts more weight on top nodes logobas
C. Magnien

79/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Quality of ranking
How do we compare rankings?
Kendall tau-coefficientC (u1 ), . . . , C (ui ), . . . , C (uj ), . . . , C (un )X
C (u1 ), . . . , C X (ui ), . . . , C X (uj ), . . . , C X (un )nodes ui and uj are concordant if
C (ui ) < C (uj )andC X (ui ) < C X (uj )τ=#concordant pairs − #discordant pairs#pairsWe use a variant that puts more weight on top nodes logobas
C. Magnien

79/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Quality of ranking, results

1

1

0.9

0.9

0.8

0.8
topo
fanta
come
all

0.7

0.6

3264 128

256

512

1,024

melb
fbwa
linux
twit

0.7

3264 128

256

512

Twitter: used ranking for h = 1024 as reference
Larger than 0.9 for h = 1024 in all cases

C. Magnienlogobas80/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Quality for top-k

We care only about the first nodes in the order
How to evaluate the quality?
γ(k): maximum approximated rank among the top-k exact nodes
Note : Example au tableaulogobasC. Magnien

81/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

Quality in practice

Results for top-20

C. Magnien

melb

fbwa

come

2,500

700

400

600

2,000

350

500

300

400

250

300

200

200

150

100

100

1,500
1,000
500

50

0
32

64

128

256

512

1024

0
32

64

128

256

512

1024

32

64

128

256

512

1024

logobas82/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

ApproachResults

In practice,use h = 1024
compute approximate ranking,select the top h nodes and compute their exact closenessalways works for finding the top 100 nodes
Open questions
Why do some datasets behave worse than others?
what if edge have travelling time?

logobasC. Magnien

83/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas84/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

How does closeness evolve with time?

Is it enough to study the global closeness?
Are important nodes always important?
Are they important most of the time?
Do unimportant nodes become important?
...

logobasC. Magnien

85/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Need to compute the closenessof all nodes
for all starting times
O(nmT )????
Here
We assume networks not too large
We can store a n × n matrix
logobasC. Magnien

86/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Foremost paths and time to reach
It is possible to compute the time to reach:for all pairs of nodes
for all starting times
in a single reading of the input
O(n2 ) space

C. Magnien[Kossinets, Kleinberg, Watts, 2008]

How would you do it?

logobas87/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Foremost paths and time to reach
It is possible to compute the time to reach:for all pairs of nodes
for all starting times
in a single reading of the input
O(n2 ) space[Kossinets, Kleinberg, Watts, 2008]

How would you do it?

logobasC. Magnien

87/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Algorithm - Principle
Perform the backward in time algorithm
for all destination nodes at once!
In memory datan × n evolving matrix[i][j]: earliest arrival time from i to j
Why not the forward algorithm?

logobasC. Magnien

88/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Algorithm - Principle
Perform the backward in time algorithm
for all destination nodes at once!
In memory datan × n evolving matrix[i][j]: earliest arrival time from i to j
Why not the forward algorithm?

logobasC. Magnien

88/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Algorithm - Principle
Perform the backward in time algorithm
for all destination nodes at once!
In memory datan × n evolving matrix[i][j]: earliest arrival time from i to j
Why not the forward algorithm?

logobasC. Magnien

88/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Algorithm
In memory datan × n evolving matrix[i][j]: earliest arrival time from i to j
Idea
Deal with time from end to beginning
Suppose we computed all t.t.r. for starting times > t
Link (u, v ) at time tu et v can reach each other at time tfor each node x 6= u, v

dux: t.t.r. from u to x, dvx: t.t.r. from v to x
if Tt (u, x) < dt (T , x) then u should go through v to reach x
earlierand conversely

C. Magnienlogobas89/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Datasets (1) – Rollernet experiment[Tournoux et al, 2009]
Proximity networks between individuals
Captured via sensors

Rollerblade tour
62 nodes∼ 3hlogobasC. Magnien

90/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Datasets (1) – Rollernet experiment[Tournoux et al, 2009]
Proximity networks between individuals
Captured via sensors

Rollerblade tour
62 nodes∼ 3hlogobasC. Magnien

90/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Datasets (2) – Enron email

All emails between Enron employees
151 employees
more than three years

logobasC. Magnien

91/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Fraction of reachable pairs
1.1
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0

0.05

0.1

0.15

0.2 0.25 0.3
Time (hours)

0.35

0.4

0.45

Rollernet

0

200

400

600
800
Time (days)

1000

1200

Enron

Compare to linkstream duration
Rollernet: 3 hours
Enron : 3 years
Very different dynamics logobas
C. Magnien

92/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas93/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Temporal efficiency

Efficiency: average closeness
Et (G ) =1X
Ct (v )nv ∈VlogobasC. Magnien

94/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Temporal efficiency - observations
16
14
12
10
8
6
4
2
0

0.1
0.01
0.001
0.0001
1e-05
1e-06
1e-07
1e-08
0

0.5

1

1.5
Time (hours)

2

2.5

3

0

Rollernet

200

400

600
800
Time (days)

1000

1200

Enron

Fluctuates a lot
Global increase over time for Enron
What about individual nodes?
logobasC. Magnien

95/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Temporal efficiency - observations
16
14
12
10
8
6
4
2
0

0.1
0.01
0.001
0.0001
1e-05
1e-06
1e-07
1e-08
0

0.5

1

1.5
Time (hours)

2

2.5

3

0

Rollernet

200

400

600
800
Time (days)

1000

1200

Enron

Fluctuates a lot
Global increase over time for Enron
What about individual nodes?
logobasC. Magnien

95/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Temporal closeness of random nodes
25

0.1

20

0.01

15

0.001

10

0.0001

5

1e-05

0

1e-06
0

0.5

1

1.5
Time (hours)

2

2.5

Rollernet

3

0

200

400

600
800
Time (days)

1000

1200

Enron

Problems
Fluctuates a lot
Difficult to interpretComparison with othernodes ?
C. Magnienlogobas96/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Temporal closeness of random nodes
25

0.1

20

0.01

15

0.001

10

0.0001

5

1e-05

0

1e-06
0

0.5

1

1.5
Time (hours)

2

2.5

Rollernet
Problems
Fluctuates a lot
Difficult to interpretComparison with othernodes ?
C. Magnien

3

0

200

400

600
800
Time (days)

1000

1200

Enron
Global comparison
Compute closeness for all
nodes at all times
Compute rank of node ateach timelogobas96/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Rank evolution
70
60
50
40
30
20
10
0

160
140
120
100
80
60
40
20
0
0

0.5

1

1.5
Time (hours)

2

2.5

Rollernet

3

0

200

400

600
800
Time (days)

1000

1200

Enron
small rank = small closenessObservations
Artefact in Enron: arbitrary rank in case of ties
correlation between closeness and rank, but not perfect
Very different behaviors
C. Magnienlogobas97/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Global statistics

Idea
An important node will often have a high rank
For each nodeCompute time spent with rank in top/bottom 25%

logobasC. Magnien

98/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

1.6
1.4
1.2
1
0.8
0.6
0.4
0.2
0

1200
Top 25% (days)

Top 25% (hours)

Global statistics
1000
800
600
400
200
0
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Bot. 25% (hours)

1

1.1 1.2

Rollernet

0

200

400
600
800
Bot. 25% (days)

1000

1200

Enron
Note that x + y < total duration

Observations
Differences between nodes
Rollernet: no node important or unimportant for more thanhalf dataset duration
Enron: some overall important or unimportant nodes
C. Magnienlogobas99/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Extremes - Rollernet
Rank of nodes with longest time in top 25% ranks - bottom 25%
ranks
70
60
50
40
30
20
10
0

70
60
50
40
30
20
10
0
0

0.5

1

1.5
Time (hours)

2

2.5

3

0

0.5

1

1.5
Time (hours)

2

2.5

3

Observations
Most important (numerically) 6= globally important
No notion of global importance?

logobasC. Magnien

100/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Extremes - Enron
Rank of nodes with longest time in top 25% ranks - bottom 25%
ranks
160
140
120
100
80
60
40
20
0

160
150
140
130
120
110
100
90
80
70
60
50
0

200

400

600
800
Time (days)

1000

1200

0

200

400

600
800
Time (days)

1000

1200

Observations
Bottom node has only two links, yet reaches high rank
Top node has consistently high rank for half the dataset
Globally important 6= always important
C. Magnienlogobas101/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Delta centrality
Impact on a given node on efficiency∆(u) =Et (G ) − Et (G \u)Et (G )−→ for each node, one value per time instantTo evaluate the global impact of a node
Rank for all times
Compute time spent in top/bot 25%
logobasC. Magnien

102/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

1.6
1.4
1.2
1
0.8
0.6
0.4
0.2
0

top 25%bottom 25%

0

0.2

0.4
0.6
0.8
1
1.2
Temp. closeness / time (days)

Rollernet

1.4

1.6

Temp. d.-centr. / time (days)

Temp. d.-centr. / time (days)

Global statistics
1200

top 25%bottom 25%

1000
800
600
400
200
0
0

200
400
600
800
1000
Temp. closeness / time (days)

1200

Enron

Observations
High correlation between high/low closeness and high/low
Delta-centrality
Some nodes have a relatively higher delta-centrality thancloseness−→ high impact on paths logobas
C. Magnien

103/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Observations

Conclusion

Results
Importance does vary with time
Notion of global importance not always meaningful
Different observations for different datasets

logobasC. Magnien

104/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Outline1

Centrality in (static) graphs2

Link streams formalism
Paths in link streams
Some existing definitions of temporal centrality measures
Algorithmic ideas

3

Finding top nodes for global closenessApproachResults

4

Closeness evolution
Observations

5

Other topics

C. Magnienlogobas105/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

More general case – dynamics on nodes

a
b
c
d
0

2

4

6

8 timeNode b is present during [0, 4] ∪ [5, 10]

C. Magnienlogobas106/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Impact on paths

C. Magnien

a
b
c
d
0

2

4

6

8

time

logobas107/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Degree centrality?
Neighborhood of a node?

C. Magnien

a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

logobas108/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Neighborhood

a
b
c
d
0

2

4

6

8

time

Neighborhood of dd’s degree: 9.5

C. Magnienlogobas109/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Betweenness centrality in graphs

C. Magnienshortest paths

B(v ) =Xu∈V ,w ∈V

σ(u, w , v )σ(u, w )|{z}
fraction of all sp
u −→ w
involving v
logobas110/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Betweenness centrality in link streams

C. Magnien

graphs :nodes,
shortest paths,
all u and v

linkstreams :temporal nodes,
shortest fastest paths (sfp),
all (t, u), (t 0 , v )shortest paths

shortest fastest paths

B(t, v ) =Xu∈V ,w ∈VZ

σ((i, u), (j, w ), (t, v ))di dj
σ((i, u), (j, w ))i∈T ,j∈T|{z}fraction of all sfp

logobas111/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Betweenness centrality in link streams
graphs :nodes,
shortest paths,
all u and v

linkstreams :temporal nodes,
shortest fastest paths (sfp),
all (t, u), (t 0 , v )shortest paths

shortest fastest paths

B(t, v ) =Xu∈V ,w ∈VZ

σ((i, u), (j, w ), (t, v ))di dj
σ((i, u), (j, w ))i∈T ,j∈T|{z}fraction of all sfp

C. Magnienlogobas111/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Betweenness Centrality in link streams

C. Magnien

a
b
c
|
1

|
2

|
3

|
4

|
5

|
6

|
7

|
8

|
9

|
10

logobas112/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Connectivity and strong connectivity
In static networks
Connected component
Set of nodes such that there exists a path
between any pair of nodes

logobasC. Magnien

113/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Connectivity and strong connectivity
In static networks
Connected component
Set of nodes such that there exists a path
between any pair of nodes

logobasC. Magnien

113/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Connectivity and strong connectivity
In static directed networks
Strongly connected component
Set of nodes such that there exists a pathfrom any nodeto any other nodelogobasC. Magnien

113/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Connectivity and strong connectivity
In static directed networks
Strongly connected component
Set of nodes such that there exists a pathfrom any nodeto any other nodelogobasC. Magnien

113/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Connectivity and strong connectivity
In static directed networks
Strongly connected component
Set of nodes such that there exists a path

C. Magnienfrom any nodeto any other node

(Strongly) connected component form a partition of nodes logobas

113/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Previous definitions

A link stream is strongly connected if:
There exists a temporal pathfrom any nodeto any other nodelogobasC. Magnien

114/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Previous definitions
A link stream is strongly connected if:
There exists a temporal pathfrom any nodeto any other node
Covers vastly different cases:

C. Magnienabclogobas114/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Previous definitions
A link stream is strongly connected if:
There exists a temporal pathfrom any nodeto any other node
Covers vastly different cases:

C. Magnienabclogobas114/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Previous definitions
A link stream is strongly connected if:
There exists a temporal pathfrom any nodeto any other node
Covers vastly different cases:

C. Magnienabclogobas114/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Connectivity, problem 1
a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

There are paths
from a to b and backfrom a to c and backfrom c to b and backlogobasC. Magnien

they require d! (and no path from d to b) 115/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Connectivity, problem 1
a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

There are paths
from a to b and backfrom a to c and backfrom c to b and backlogobasC. Magnien

they require d! (and no path from d to b) 115/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Connectivity, problem 2
a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

{a, b, c} and {a, c, d} are connected components
Components overlap!
Huge number of components in practice logobas
C. Magnien

116/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Connectivity, problem 2
a
b
c
d
|
1

|
2

|
3

|
4

|
5

|
6

{a, b, c} and {a, c, d} are connected components
Components overlap!
Huge number of components in practice logobas
C. Magnien

116/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

What is a community?
Set of nodes that share something:Affiliation (friends, colleagues, club, ...)
Similar interests (tagging systems, ...)
Similar contents (movies, books, products, web pages, ...)...

What is the connexion with the network structure?

logobasC. Magnien

117/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

What is a community?
Set of nodes that share something:Affiliation (friends, colleagues, club, ...)
Similar interests (tagging systems, ...)
Similar contents (movies, books, products, web pages, ...)...

What is the connexion with the network structure?

logobasC. Magnien

117/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

What is a community?
Set of nodes that share something:Affiliation (friends, colleagues, club, ...)
Similar interests (tagging systems, ...)
Similar contents (movies, books, products, web pages, ...)...

What is the connexion with the network structure?
More densely connected inside than outsidelogobasC. Magnien

117/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Community detection

Goal: Identify communities automatically
Applications:C. Magnien

Understand the structure of a network
Help visualization
Detect specific communities (web pages, proteins, ...)
Improve information retrieval (search engines,
recommendation, ...)

logobas118/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Challenges

Unknown number of communities
Unknown sizes of communities
Scalability

logobasC. Magnien

119/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Challenges

Unknown number of communities
Unknown sizes of communities
Scalability

Many definitions of a community

logobasC. Magnien

119/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

Using betweenness centrality for community detection

C. Magnien[Girvan and Newman, 2002]
Step 1: All nodes are in the same community (initialization)
Step 2: Compute the betweenness of each link
Step 3: Delete the highest betweenness link
Step 4: Iterate from step 1

Use definition of betweenness centrality in link streams?
logobas120/121

Centrality in (static) graphs
Link streams formalism
Finding top nodes for global closeness
Closeness evolution
Other topics

I hope this lecture

C. Magnien

Made you grasp the challenges of dealing with temporal paths
Showed you that digging into the data can be easy
Showed that it is not easy to find relevant indicators. . . and gave you some hints!

logobas121/121