Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Flow of knowledge in information networks
Jean-François B AFFIER1
1 Japan Society for the Promotion of Science
French National Center for Scientific Research
Hosted at the Tokyo Institute of Technology

Monday, December 18, 2018
Network Optimization course

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 20181 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Table of contents

1

Introduction

2

Information Networks

3

Flow of knowledge

4

Multiplex Networks

5

Cycles, connected component and ethics

6

Conclusion

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 20182 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Contextualization

A not very funny joke
Three scientits, one in computer science, one in humanities, and one in biology enter acafé. . .

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 20183 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Contextualization

A not very funny joke
Three scientits, one in computer science, one in humanities, and one in biology enter acafé. . .
⇒ They have the same number of citations !
J.-F. Baffier (2018)

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 20183 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Contextualization

A not very funny joke
Three scientits, one in computer science, one in humanities, and one in biology enter acafé. . .
⇒ They have the same number of citations !
J.-F. Baffier (2018)
The analyzis of academic citation networks depends strongly on
Research field, era, host institution, fundings, . . .
Network size, its shape, . . . so its structure
Analytical tools used !

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 20183 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Comment en suis-je arrivé lá ?

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 2018

4 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Table of contents

1

Introduction

2

Information Networks

3

Flow of knowledge

4

Multiplex Networks

5

Cycles, connected component and ethics

6

Conclusion

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 2018

5 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

The value of the transmission of knowledge

Education is the transmission of civilization.
(Areil and Will D URANT — 1968)

Structure is more important than content in the transmission of information.
(The medium is the message)(Abbie H OFFMAN — 1968)

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 2018

6 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

An academic citations network

F IGURE – Arxiv HEP-TH (high energy physics theory) : 27770 nodes (articles) — 352807 arcs (citations)Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 20187 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

An academic citations network

Expected properties :Directed(Pseudo-)Acyclic
Dynamic
Stable nodes (articles) : the papers are not modified after publication
Large et complex
According to the University of Ottawa, in 2009 the amount of 50 millions of academic
publications was reached (starting from 1665). Currently there is about 2.5 millions of
new publications per year.
With the constant growth in the number of researcher and the global growing population,
it is believed that the total number of publications will double every 9 years.

Unweighted (on the links)
Information is generated on each node (or at least on many)

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 20187 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Other information networks

F IGURE – Réseaux d’interconnections des domaines et disciplines dans Wikipédia
Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 20188 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Other information networks

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 20188 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Other information networks
Game of Thrones Family Ties
Node color:
House Baratheon
House Frey
House Greyjoy
House Lannister
House Martell
House Stark
House Targaryen
House Tully
House Tyrell

OlyvarFrey

Benfrey
Frey

Bethany
Rosby
WalderFrey

Merrett
Frey

Amerei
Frey

Obara
Sand

Perra
Royce
WillemFrey

Ellaria
Sand

RoslinFrey
OberynMartell

Dorea
Sand

Jeyne
Darry

Walda
Frey
daughterofMerrett

LancelLannister

Elia
Sand

Walder
Frey
son
of
Emmon

Sarella
Sand

Emmon
Frey

Doran
Martell

Dorna
Swyft

Ermesande
HayfordPrincessof
Dorne

Edmure
Tully

LyonelFrey

Maron
MartellRhaenys
TargaryendaughterofRhaegar

Hizdahr
zo
Loraq

Arya
Stark

Elys
Waynwood

LucionLannister

RickonStark
TalisaStark

ShieraCrakehall

Robb
Stark

Sansa
Stark
Bran
Stark

Jeyne
Westerling

Ella
Lannister

LyannaStark

Brandon
Stark

Tywin
Lannister

LyarraStark

LynaraStark

Viserys
Targaryen

Brandon
Stark
son
of
CreganTyrionLannister

Jason
Lannister

Jaehaerys
II
Targaryen

Cersei
Lannister

Daven
Lannister
MyrandaLefford

Myrcella
Baratheon

Cerenna
Lannister

Myrielle
Lannister
LyannaGloverJoffrey Tommen
BaratheonBaratheon

LysaraKarstark

Aegon
V
Targaryen

RobertBaratheon

WillasTyrellMargaeryTyrellBetha
Blackwood

SteffonBaratheon

RhaelleTargaryen

MaekarI
Targaryen

TyboltLannister
Teora
Kyndall

Stafford
Lannister

Melantha
Blackwood

Artos
Stark

DyannaDayne

CerissaBrax

Damon
Lannister

Jaime
Lannister
WillamStark

ShaeraTargaryen

GeroldLannister

Marla
Prester

Lorra
Royce

Myriame
Manderly

RohanneWebberJoannaLannister

Marna
Locke
Edwyle
Stark

Beron
Stark

Antario
Jast

Alysanne
FarmanRodrikStark
BenjenStarkRodrik
Stark
son
of
Beron

Lanna
Lannister

Alys
Stackspear
Tysha

Arya
Flint

Aerys
II
Targaryen

Alys
Karstark

DamionLannister

Damon
Lannister
son
of
Jason

RickardStark
RhaellaTargaryen

Rodwell
Stark

Alys
Arryn

Catelyn
Stark

Eddard
Stark

Jon
Snow
BrandonStark
BurnerRhaegar
Targaryen
Daenerys
Targaryen

Robyn
Ryswell

JasperArryn

RowenaArryn

RamsayBoltonAegon
Targaryensonof
Rhaegar

Drogo

JonnelStark

Jeyne
MarbrandTytos
Lannister

Elia
Martell

Cregan
Stark

Jon
Arryn

Hoster
Tully

GerionLannister

Arra
Norrey

Jeyne
Royce

Robert
Arryn

Lysa
Arryn

MinisaWhent

Darlessa
MarbrandTygettLannister

Gilliane
GloverPetyr
BaelishMelesaCrakehall

Genna
Lannister

Roose
BoltonKevan
Lannister
Tyrek
LannisterMors
Martellbrotherof
DoranRickonStark
sonof
Benjen

Tywin
Frey

Cleos
Frey

Tion
Frey
WillemLannister

Mellarioof
NorvosPerwynFrey

Amarei
Crakehall

MariyaDarry
ObellaSand

LorezaSand

Edge color:fatherfather/mothermotherspouseJyannaFrey

Willamen
Frey

Marissa
Frey

WalderFreysonofMerrett

Pate
of
the
Blue
Fork

Nymeria
Sand

Tyene
Sand

Cassana
Baratheon

Mace
TyrellOrmundBaratheon

StannisBaratheon

LuthorTyrell
son
of
Moryn

Leo
Blackbar

SelyseFlorent
Mina
TyrellHobberRedwyneShireenBaratheon

ElinorTyrellOlene
Tyrell

UnknownmotherTyrellLuthorTyrellTheodore
TyrellElyn
Norridge

Moryn
Tyrell

Unknown
fatherTyrellOlennaRedwyneLia
Serry

MedwickTyrellLoras
TyrellDuncanTargaryen

Jennyof
Oldstones

LuthorTyrellsonof
Theodore

Leonette
Fossoway
GarlanTyrellAlerieHightower

Renly
Baratheon

PaxterRedwyneRodrikGreyjoy

Horas
RedwyneVictarion
GreyjoyRobin
Greyjoy

Lady
of
House
Piper

Donel
Greyjoy

Lady
of
House
Stonetree

Erik
Ironmaker
Asha(Yara)
Greyjoy

Alannys
Harlaw
Balon
Greyjoy

UrrigonGreyjoy
Lady
of
House
Sunderly

QuellonGreyjoy

HarlonGreyjoy

Aeron
Greyjoy

Maron
Greyjoy
Theon
GreyjoyEuron
Greyjoy

QuentonGreyjoy

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 20188 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Table of contents

1

Introduction

2

Information Networks

3

Flow of knowledge

4

Multiplex Networks

5

Cycles, connected component and ethics

6

Conclusion

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 2018

9 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

The h-index

The Hirsch index aims to quantify
the impact of a publication (orauthor).
Quick computation
Improvement over the simple
metric of the number of direct
citations
Reference metric (goodmetric. . . on average)

F IGURE – Short exercise : what is the value of h here ?

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201810 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

The h-index

The Hirsch index aims to quantify
the impact of a publication (orauthor).
Quick computation
Improvement over the simple
metric of the number of direct
citations
Reference metric (goodmetric. . . on average)
Only consider a small part ofthe citation network

F IGURE – Short exercise : what is the value of h here ?

Jean-François B AFFIER JSPS — CNRSIs it actually useful to evaluate(to grade) the agents creatingknowledge ?

Flow of knowledge in information networks

Monday, December 18, 201810 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Strahler’s flow
The flow of Strahler is a first simple way to consider
the influence (here the river flow) of an agent on theothers.
How to extend it to the context of the transmission ofknowledge ?
Information should possibly be evaluated on an
ascendant way
Classic metrics (i.e. direct citation number,h-index, etc.) should be compatible
Algorithmic cost should be reasonablenSize/Speed ration2n3

F IGURE – A Strahler flow example to evaluate the

2n

10
100

100
104

1000
106

≈ 1000≈ 1030

1000

106

109

≈ 10300

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

influence of each tributary river in the formation of the main river.
Strahler number (4 here) measure thecomplexity of the branching factor of theriver.

Monday, December 18, 201811 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

A general framework

Definition
For a publication p, its in-neighborhood N − (p) is the set of all the publications
referring to p. The size of N − (p) is simply its in-degree d − (p). The corollary implies
that N + (p), the out-neighboorhood of p, corresponds to all publications to which p isreferring to (with a size d + (p), its out-degree).

(K (p) =

λ, if N + (p) = ∅F (K (s1 ), . . . , K (sd + (p) )), otherwise,(1)

where λ designates a constant for terminal cases (leafs, often λ = 1), si ∈ N + (p)represents the successors of node p, and F is an application depending on the values
K (s1 ), . . . , K (sd + (p) ). To simplify the notations, we denote
F (N + (p)) = F (K (s1 ), . . . , K (sd + (p) )).

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201812 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

A general framework

Strahler Flow

F (N − (p)) =−
1, if d (p) = 0
(K (q)) +
 max
−
q∈N

(p)

(
d − (p) − 1 if all values K (q) are equald − (p) − 2 otherwise(1)

h-index
0, if d + (p) = 0
F (N (p)) =+ max min(d (q), |X |)+(2)

X ⊂N + (p) q∈X

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201812 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Definitions

Definition (Related)
Two articles p and q are said to be related if and only if there exist a path from p to q orfrom q to p. They are k -related if they are related and if the shortest path between
them is at most of length k .
Definition (k -diffuse)A measure of a node p is k -diffuse when it limits its computation to a subgraphcomposed of the k -related nodes of p

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201813 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

A first straightforward ascending flow
11
6

1

+ 12

1

1

7
3

+ 13

+ 12

11
6

+ 67

+ 12

+ 12
1

+ 76

+ 13

+ 13
1

1

1

1

3

1

6

+3
3

3

7
3

1
Jean-François B AFFIER JSPS — CNRS

7
3

1

1

1

Flow of knowledge in information networks

1

1
Monday, December 18, 201814 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

A first straightforward ascending flow

ALGORITHM 1: ascending flow
input : A citation network with nodes (articles) and arcs (citations)
An empty dequeue Q (FIFO)
output: The ascending flow on each node (article) and each arc (citation)
Initialize each article v a with flow value αv = 1
Color each arc in white
3 Add all leaves in Q
4 while Q is not empty do
5v ← pop_first(Q)6
for each w son of v do
7
Color each (v , w) in blue
8
αw ← αw + αv /d − (v )9if all incoming arcs of w are blue then10
Q ← push_last(w)
11
end
12
end
13 end12Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201814 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

A first straightforward ascending flow

F IGURE – An ascending flow example (publications with a high h-index)
Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201814 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

A first straightforward ascending flow
2.5
flow
1flow
2flow
5flow

2

Speed

1.5

1

0.5

0
0

0.5

1

1.5
2
]Publications

2.5

3

·104

In terms of computation, from k = 2, the ranks obtained by the k -flow are rs = 0.99
similar of those of the regular flow so when a gain of computation is needed, one canuse k -diffuse version of the algorithm .
Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201814 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Table of contents

1

Introduction

2

Information Networks

3

Flow of knowledge

4

Multiplex Networks

5

Cycles, connected component and ethics

6

Conclusion

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201815 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

The intrication of data

a
a

a

a

b

a

a,b
b

c

a,b

a,c
b,c
d

a,b,c
e

f

F IGURE – Illustration of the previous citation network transformed to a multiplex network, each citation creates its
own layer of interaction.

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201816 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

The intrication of data

Definition
A citation subgraph Gp = (Vp , Ep ) is induced by a node p such as
Vp = p ∪ N − (p) ⊂ V , and Ep ⊂ E is such that, ∀(q, r ) ∈ Vp2 , ∃a(q, r ) ∈ E.
Let consider, for each publication p, its induced citation subgraph Gp = (Vp , Ep ) of G,
the multiplex citation network G results in combining all individual subgraphs Gp
together.
Definition
A multiplex network
S G = (V , E, L) connects nodes (p, q) on different layers l such asarcs a(p, q, l) ∈ l∈L El . A multiplex citation network G = (V , E, L) is defined such as
SS
Ep and L = V .
G = p∈V
Gp , hence E = p∈Vpp
Note that an arc a(p, q, l) exists if and only if both p and q cite l or if l = q. As aconsequence, the multiplex network once “flattened”, has the exact same topology as
the original citation network. The difference lies in the multiple edges.

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201816 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

The intrication of dataIn our multiplex citation network, the notion of neighborhood remains the same as in
the monoplex case. However we can refer to a different notion of multiplex degreesδ + (p) and δ − (p) that takes into account the number of arcs connecting a node to its
neighborhood.
Definition
Denote the multiplex out-degree δ + (p) (respectively the multiplex in-degree δ − (p)) a
node p in the multiplex network G.
δ + (p) = |a(p, q, l)|, ∀q ∈ V , ∀l ∈ L, s.a. ∃a(p, q, l) ∈ E (respectively
δ − (p) = |a(q, p, l)|)The degrees d + (p) and d − (p) still refer to the degree in the monoplex network G, i.e.
the size of the neighborhood. We then introduce the degrees dl+ (p) and dl− (p)corresponding to the degree in the subgraph Gl , i.e. the number of arc adjacent to p on
the layer l.
Definition
Denote the layer out-degree δl+ (p) (respectively the layer in-degree δl− (p)) a node p in
the subgraph Gl . δl+ (p) = |a(p, q, l)|, ∀q ∈ V , s.a. ∃a(p, q, l) ∈ E (respectively
δl− (p) = |a(q, p, l)|)Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201816 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Aggregated Flow
3
2

1
1
+6

1
+3

1

17
+ 18

1 1
+6+6

5
3

1
+3
1 1
+3+3

1 1 1
+6+6+6

1

17
6

17 17
+ 18 + 18

1 1
+3+3

1

1

1

1

1

22
9
32
+ 9

6

32
9

3.56

17
6

1

1

2.83

1

Jean-François B AFFIER JSPS — CNRS

1

1

Flow of knowledge in information networks

1

1
Monday, December 18, 201817 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Aggregated Flow
ALGORITHM 2: Aggregated flow (multiplex)
input : A citation network with nodes (articles) and arcs (citations)
An empty dequeue Q (FIFO)
A function αinit over the nodes
output: The ascending flow on each node (article) and each arc (citation)
Initialize each article p with a flow value λp = λinit (p)(= 1 by default)
Color each arc in white
3 Add all leaves in Q
4 while Q is not empty do
5p ← pop_first(Q)6
for each q son of p do
7
for each layer l ∈ Lp do
8
Color a(p, q, l) in blue9
λq ← λq + λp /δ + (p)
10
end
11
if all incoming arcs of q are blue then12
Q ← push_last(q)
13
end
14
end
15 end12Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201817 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Aggregated Flow

General framework formulationq∈N − (p)F (N − (p)) =X

K (kq )/δ + (kq ) + λp

(3)q

The complexity of the monoplex ascending flow is Θ(m) where m is the number ofcitations. Since the input is a multiplex network, in the worst case the number of links inthe networks is equal to the number of nodes (layers) times the number of citations.
Thus, the time-complexity of this aggregated flow is Θ(mn).

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201817 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Sum FlowThis second extension of the ascending flow to a multiplex network consists incombining multiple monoplex versions of the ascending flow.
Recall the definition of the ascending flow, adapted to a subgraph Gl :q∈N − (p)FGl (N − (p)) =X

KGl (kq )/dG+ (kq ) + λ(p,l)

(4)

l

q

The sum flow will simply sum ascending flows over all subgraphs composed of one
layer, determined for a node p by :l∈L(p)FG (p) =X

FGl (N − (p))(5)

l

λ(p,l) =λp|L(p)|

If we set the parameter λ(p,l) = 1, the contribution of one publication to the wholesystem will be exactly its number of citations, and a publication that cites lots of work
will produce a lot of flow. In order to maintain constant the unit of contribution of aPl∈L(p) 1
publication of a work, we set λp = 1 hence l= 1 such as a publication|L(p)|
brings exactly 1 unit of contribution to the system.
Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201818 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Sum Flow
Initial weights
1
1 1
2+2
1 1 1
3+3+3
1 1 1
3+3+3

1 1 1
3+3+3

1 1 1 1
4+4+4+4

Sum over each layer
17
12

17
12

13
16

+

5
8
1
3

1
4

1
3

1
3

1
4

1

1
4

2.73

=

1
3
1
3

1
3

2.42
1
2

+

5
4

+

5
8

2.83
1
3

Jean-François B AFFIER JSPS — CNRS

1
4

1
Flow of knowledge in information networks

1

1
Monday, December 18, 201818 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Sum Flow

ALGORITHM 3: Sum flow (multiplex)
input : A citation network with nodes (articles) and arcs (citations)
output: The sum flow on each node (article) and each arc (citation)
Initialize each article p with a flow value λp = 0
for each article p do
3Construct the citation subgraph Gp
1
4
F ← ascending-flow(Gp ) with ∀q ∈ Vp , λinit (q) = d + (q)+1

1
2

for each article q ∈ Vp do
λq ← λq + F (q)
end

5
6
7
8

end

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201818 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Selective Flow11
1 13
+ 2 + 2 ( 36 )

1
+3

1
+2

1
1
+2

1
1
+4
1
+4

1
+4

1

1
+6

1
+9

1
+4

1
+6

1 + 5613
1+ 4 + 1( 36 )1
1 13
+ 4 + 2 ( 36 )1 + 43
1
+9

1
+9

1

11
6

1

1

1

181
72

1

3.91

9
+1+ 23

1 + 3155
1656

2.91

2.83

1

2.33

1

Jean-François B AFFIER JSPS — CNRS

1

1

Flow of knowledge in information networks

1

1
Monday, December 18, 201819 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Selective Flow
input : A citation network with nodes (articles) and arcs (citations)
An empty dequeue Q (FIFO)
output: The selective flow on each node (article) and each arc (citation)
Initialize each article p with the color white and the value λp = 1
Color all leaves in red and push them into Q
3 while Q is not empty do
4q ← pop_first(Q)5for each r son of q do
6
if r is white then7
Construct Gr and initialize all λ(a(q, r , l)) to 0
8
push_last(Q, r )9Color r in red
10
end
11
end
12
for each layer l ∈ Lq do
13
Initialize λl,q = 0
14
for each parent p of q do
15
λl,q ← λl,q + λ(a(p, q, l))
16
end
17
for each son r of q do
1

2

1
λ(a(p, q, l)) ← d + (q)×(1+|L(q,r
+
)|)

18

end
λq ← λq + λl,q

19
20
21

λl,q
d + (q)lend

22 endJean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201819 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Selective Flowq∈N − (p)FGl (N − (p)) = λ(p,l) +X

KGl (kq )qdG+ (kq )ll∈L(p)FG (p) =X

FGl (N − (p))(4)

lj∈N + (p)α(p,l) =X
j

Jean-François B AFFIER JSPS — CNRS

λpd + (p) × |L(p, j)|Flow of knowledge in information networks

Monday, December 18, 201819 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Table of contents

1

Introduction

2

Information Networks

3

Flow of knowledge

4

Multiplex Networks

5

Cycles, connected component and ethics

6

Conclusion

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201820 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

What ethics in influence measures

We can define some criteria to guarantee an ethic that we hope flows naturally
Equity between articles
Metrics with bounded values in pratice
A network (or sub-network) with consistent content : for instance articles from asame field or institute.
These criteria are put to the test by the mere presence of cycles within the network.
That is, the existence of a couple of nodes (items here) that are descended from eachother.
We say that a sub-network is a (strongly) connected component if every vertex isreachable from every other vertex.

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201821 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

A costly solution, decycling (with drawings)

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201822 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

A costly solution, decycling (with drawings)

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201822 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

A costly solution, decycling (with drawings)

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201822 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Solving the time/accuracy ratio in Information Networks

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201823 / 24

Introduction

Information Networks

Flow of knowledge

Multiplex Networks

Cycles, connected component and ethics

Conclusion

Conclusion

Solutions to the Big Data Science problems are inherently cross-domain.
(Jean-françois B AFFIER — 2018)

Jean-François B AFFIER JSPS — CNRS

Flow of knowledge in information networks

Monday, December 18, 201824 / 24