Efficient computation of Harmonic Centrality on large networks: theory and practice

Eugenio Angriman

Monday 10th October, 2016

Advisors: Prof. Geppino Pucci

Prof. Andrea Pietracaprina

Università degli Studi di PadovaScuola di Ingegneria

Corso di Laurea Magistrale in Ingegneria Informatica

Centrality

✤ In a huge network: identify the most central nodes

✤ Locate the most reliable web pages, the most influential people inside a certain community…

Given a graph G = (V, E), ∀ v ∈ V:

✤ Trivial approach: computes APSP (too expensive)

h(v) =1

|V |− 1

!

w∈V,w =v

1

d(v, w)

Harmonic Centrality

0.68

0.59

Overview

✤ Efficient Harmonic Centrality approximation

✤ Fast top-k exact Harmonic centralities computation

✤ Conclusion and future developments

Eppstein et al.

✤ Undirected networks

✤ Select k = Θ (logn/ε2) sample nodes

✤ Solve SSSP problem using each sample as source

✤ Estimate the Closeness Centrality for each node using a centrality estimator:

Target nodec(v) =1

!ki=1

nd(vi,v)k(n−1)

✤ Theorem: given an undirected, connected graph, α ≥ 1

✤ Proof: uses Chernoff Hoeffding’s concentration bounds

Eppstein et al. for the Harmonic Centrality

h(v) =n

k(n− 1)

k!

i=1

1

d(vi, v)

Pr

!"

"

"

"

"

#

k

i=ixi

k− µ

"

"

"

"

"

≥ ξ

$

≤ 2e−

2k2ξ2!k

i=1 (bi−ai)2

Pr!"

"

"h(v)− h(v)

"

"

"≥ ϵ

#

≤1

nα

Eppstein et al. - time performances

Authorship networks

Gain = tn − ta

tn

tn: time to compute all centralitiesta: time required by Eppstein et al.

Eppstein et al. - comparison with Borassi et al.

Gai

n

-1000

-750

-500

-249

1

k = 1 k = 50 k = 500

-38.4 -10.5 0.677

-116.36-33.26 0.372

-979

-285

-7ε = 0.05 ε = 0.15 ε = 0.3

Eppstein et al. - precision

h(v) ∈ [0, 1]

Eppstein et al. - samples / 4

h(v) ∈ [0, 1]

Eppstein et al. - top-k analysis

Wiktionary (de)

ratio =k + k

k

: number of above-k ranked centralities we considered in order to obtain the actual top-k centralities

k

Okamoto et al.

Top-k Closeness centralities exact computation

Eppstein et al. for ClosenessCentrality approximation

Create a candidate set Swith k’ > k nodes

Compute the exact ClosenessCentrality for each node in S

top-k approximated most central nodes

further samples incandidate set S

actual top-k most central nodes

✤ Theorem: if we select samples, the Okamoto algorithm correctly ranks the top-k Harmonic Centralities with high probability

✤ Proof:

Okamoto et al. for Harmonic Centrality

Θ(n2/3 log1/3 n)

Pr!"

"

"h(v)− h(v)

"

"

"≥ ϵ

#

≤1

n2

Pr

!

¬

"

#

v∈T

hv ≥ hvk− f(l) ≥ hvk

− 2f(l)

$%

≤k

n2

Okamoto et al. - time performances

Number of vertexes

Gai

n

Conclusions

✤ Two new efficient randomized algorithms for the Harmonic Centrality

✤ Experimental analysis:

Eppstein et al. approximation algorithm: remarkable precision and time performances

Eppstein et al. downsampling: faster and not great precision loss. Suitable for Okamoto et al.

Future work

✤ In-depth study of the Okamoto et al. algorithm time

✤ Study a new approach for directed networks

✤ Multithreaded implementation

Thanks for your attention