Abu Bakar Siddique

email: abakarsiddique@[Link]
The University of New Mexico

Symmetries in the time-averaged dynamics

of networks

December 13, 2017

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Collaborators

Francesco Sorrentino
Louis M. Pecora

Siddique A. B., UNM December 13, 2017 2 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Outline

1 Symmetries and the Network Dynamics

Network Topology and Symmetries

2 Dynamical Models
Related research
Evolutionary Game Theory
Time-Averaged Outcomes

3 Quotient Graph Reduction

Definition
Simulation

4 Experimental Realizations

Siddique A. B., UNM December 13, 2017 3 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Outline

1 Symmetries and the Network Dynamics

Network Topology and Symmetries

2 Dynamical Models
Related research
Evolutionary Game Theory
Time-Averaged Outcomes

3 Quotient Graph Reduction

Definition
Simulation

4 Experimental Realizations

Siddique A. B., UNM December 13, 2017 4 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Network

We describe the adjacency of a network G using a matrix A such that,

Ai j =A ji = 1, if node i and node j are neighbors

Ai j =A ji = 0, otherwise

Adjacency matrix, A
4 3

1 2

Siddique A. B., UNM Network Topology and Symmetries December 13, 2017 5 / 28
 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Symmetry
Symmetry
Symmetry is a permutation (π` ) of the network nodes that leaves the network
structure unaltered. For example (1,2)(3,4)(5) is an example of one of the
permutations of the graph G .

Permutation Matrix
We construct the permutation matrix Π such that Πi, j = 1 if node i is
swapped with node j in the permutation and Πi, j = 0 otherwise. All the
permutation matrix hold the identity ΠA = AΠ.

Permutation matrix, Π
4 3

5 π = (1, 2)(3, 4)(5)

1 2

Siddique A. B., UNM Network Topology and Symmetries December 13, 2017 6 / 28
 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Symmetry Group

Automorphism Group
The symmetries (permutations πi ) of the network form a (mathematical)
group G. πi ∈ G describes all the possible permutations of the graph.

Group Orbit
The orbit of a node x ∈ G is defined as, O(x) := {y ∈ G : ∃g ∈ G : y = π ∗ x},
where ∗ denotes the group action. For example, the symmetric orbits of the
network are {1, 2, 3, 4} and {5}.

4 3 4 1 1 3 4 3

5 5 5 =⇒ 5

2 1 3 2 4 2 1 2

Siddique A. B., UNM Network Topology and Symmetries December 13, 2017 7 / 28
 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Outline

1 Symmetries and the Network Dynamics

Network Topology and Symmetries

2 Dynamical Models
Related research
Evolutionary Game Theory
Time-Averaged Outcomes

3 Quotient Graph Reduction

Definition
Simulation

4 Experimental Realizations

Siddique A. B., UNM December 13, 2017 8 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Some previous works

Martin Golubitsky and Ian Stewart., Springer Science & Business
Media, volume 200, 2003.
Martin Golubitsky, Ian Stewart, et al., Springer Science & Business
Media, volume 2, 2012.
Igor Belykh, Enno de Lange, and Martin Hasler., Physical review
letters, 94(18):188101, 2005.
Igor Belykh and Martin Hasler., Chaos: An Interdisciplinary Journal of
Nonlinear Science, 21(1):016106, 2011.
Vladimir N Belykh, Igor V Belykh, and Erik Mosekilde., Physical
Review E, 63(3):036216, 2001.
Louis M Pecora, Francesco Sorrentino, Aaron M Hagerstrom, Thomas
E Murphy, and Rajarshi Roy., Nature communications, 5:304–305,
2014.
Francesco Sorrentino, Louis M Pecora, Aaron M Hagerstrom, Thomas
E Murphy, and Rajarshi Roy., Science Advances 2, 2015.
Francesco Sorrentino and Louis Pecora., Chaos: An Interdisciplinary
Journal of Nonlinear Science, 26(9):094823, 2016
Siddique A. B., UNM Related research December 13, 2017 9 / 28
 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Evolutionary Game Theory

Strategies of the nodes

C
C
C

Cooperators, Si = 1 D
D
Defectors, Si = 0
C D

Payoff matrix of an interaction between two nodes

c = Cost of cooperation
b = Benefit from cooperation

Cooperator Defector
Cooperator b−c −c
Defector b 0

Siddique A. B., UNM Evolutionary Game Theory December 13, 2017 10 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Evolutionary Game Theory (cont.)

Total Payoff

ξi = ∑ Ai j bS j − ki cSi
j

ki : Node degree

Fitness function 1

fi = 1 − ω + ωξi
0 ≤ ω ≤ 1 measures the intensity of selection

1Hisashi Ohtsuki, Christoph Hauert, Erez Lieberman, and Martin A Nowak. Nature,
441(7092):502–505, 2006.
Siddique A. B., UNM Evolutionary Game Theory December 13, 2017 11 / 28
 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Evolutionary Game Theory (cont.)

Evolution of Death-Birth Updating

C C C
C C C
C C C

D D D
D ? C

C D C D C D

D D D

Strategy selection function2

σ (xi ) = γxi + ε
xi = (FCi − FDi )
γ > 0 and ε are two arbitrary constants.
0≤σ ≤1
2Abu Bakar Siddique, Louis M Pecora, and Francesco Sorrentino. arXiv:1710.05251, 2017.
Siddique A. B., UNM Evolutionary Game Theory December 13, 2017 12 / 28
 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Symmetries affect the results

Karate Club Bellsouth Random ER

Frequency of being cooperator vs. node degree

Siddique A. B., UNM Time-Averaged Outcomes December 13, 2017 13 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Outline

1 Symmetries and the Network Dynamics

Network Topology and Symmetries

2 Dynamical Models
Related research
Evolutionary Game Theory
Time-Averaged Outcomes

3 Quotient Graph Reduction

Definition
Simulation

4 Experimental Realizations

Siddique A. B., UNM December 13, 2017 14 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Network Quotient
For each pair of orbits (O x , O y ), we define a quotient C ×C matrix Q such
that
Qxy = ∑ Ai j , i ∈ O x , x, y = 1, 2, . . .C
j∈O y

where C is the number of the clusters in the partition of G .

2 2
2

4 4
2
2
2
4
2

2
2 2
4

Siddique A. B., UNM Definition December 13, 2017 15 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Symmetry in Real Networks

The table below is an excerpt from the data on the symmetries of real
networks, reported by MacArthur et al3.

Network No of nodes No of edges No of symmetries Reduction Ratio

BioGRID Drosophila (BGDros) 7, 371 25, 043 3.0687 × 10493 0.87
Yeast Protein Interactions (Yeast) 1, 458 1, 948 1.0667 × 10254 0.70
Internet (AS Level) (IntAS) 22, 332 45, 392 1.2822 × 1011298 0.51
www [Link] subnet (EPA) 4, 253 8, 897 1.2772 × 102321 0.52
US Airports (USAir) 332 2, 126 2.5916 × 1024 0.83
Media ownership (Media) 4, 475 4, 652 3.3638 × 104818 0.20
PhD network (PhD) 1, 025 1, 043 2.9810 × 10292 0.50
PGP users network (PGP) 10, 680 24, 316 4.4963 × 101251 0.74

No of nodes in the quotient network

Reduction Ratio =
No of nodes in the original network

3Ben D MacArthur, Rubén J Sánchez-García, and James W Anderson. Discrete Applied

Mathematics, 156(18):3525–3531, 2008.
Siddique A. B., UNM Definition December 13, 2017 16 / 28
 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Quotient Network Simulation

Evolutionary Game Theory

We have adapted the dynamics of the full network to simulate that on it’s
quotient network as
Cooperators, Ŝi = 1
Defectors, Ŝi = 0
The selection probability of a node of the quotient network is directly
proportional to the cardinality of the corresponding orbit of the full
network.
Payoff and the fitness equations are adapted for the weighted links of
the quotient network.

ξˆi = ∑ Qi j bŜ j − ck̂iin Ŝi

j

Siddique A. B., UNM Simulation December 13, 2017 17 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Results of Quotient Graph Simulations

0.95
Evolutionary game theory
Full network
Frequency of being cooperator

0.9 Network quotient

0.85

0.8

0.75

0.7

0.65

0.6

0.55

0.5

0.45
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
3
3
3
3
4
4
4
4
4
5
5
5
5
16
18
Source node degrees

Siddique A. B., UNM Simulation December 13, 2017 18 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Terminologies

Reduction Ratio, ρg = C/N

A smaller value of the ratio ρg indicates higher reduction of the number of
nodes in the quotient graph with respect to the original graph.

CPU time ratio ρt = tq /t f

t f = the CPU time for an iteration of full network
tq = the CPU time for an iteration of quotient network.

Convergence Time Ratio

We define settling time as the average dynamics of a node does not change
more than 5% over time and
max{settling time of the nodes of quotient network}
Convergence time ratio =
max{settling time of the nodes of full network}

Siddique A. B., UNM Simulation December 13, 2017 19 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Terminologies (cont.)

Relative Error, ∆

ˆ |
1 N |hSii − hSii
∆= ∑ ,
N i hSii
ˆ are the time-averaged frequency of cooperation of node i
where hSii and hSii
and its corresponding node in the quotient network, respectively.

Siddique A. B., UNM Simulation December 13, 2017 20 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

CPU time ratio

CPU time ratio, ρt

0.8 (a)
0.6

0.4
Media Owners Group
EPA Gov
0.2 Bellsouth
Karate club
US airports 97
0 ER

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Reduction coefficient, ρg

Siddique A. B., UNM Simulation December 13, 2017 21 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Convergence ratio

Convergence time ratio, ρc

0.8
(b)
0.6

0.4 Media Owners Group

EPA Gov
Bellsouth
0.2 Karate club
US airports 97
ER
0
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Reduction coefficient, ρg

Siddique A. B., UNM Simulation December 13, 2017 22 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Relative error

0.1
Media Owners Group
0.08 (c) EPA Gov
Bellsouth
Karate club
0.06 US airports 97
Error, ∆

ER

0.04

0.02

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Reduction coefficient, ρg

Siddique A. B., UNM Simulation December 13, 2017 23 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Outline

1 Symmetries and the Network Dynamics

Network Topology and Symmetries

2 Dynamical Models
Related research
Evolutionary Game Theory
Time-Averaged Outcomes

3 Quotient Graph Reduction

Definition
Simulation

4 Experimental Realizations

Siddique A. B., UNM December 13, 2017 24 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Experimental Realizations

4 10

1 7

8 9

3 5

2 6
Arduino UNO R3 + NRF24L01

Game Controller Computer

Siddique A. B., UNM December 13, 2017 25 / 28

 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Experimental Realizations (Contd.)

4 10

1 7 2 2 3 4

1 2 3
8 9 2
3

3 5 5

2 6

1 1
Frequency of cooperation

Frequency of cooperation
0.9 0.9

0.8 0.8

0.7 0.7

0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1

Time steps ·105 Time steps ·105

Relative error = 0.035

Siddique A. B., UNM December 13, 2017 26 / 28
 Symmetries and the Network Dynamics Dynamical Models Quotient Graph Reduction Experimental Realizations

Abu Bakar Siddique, Louis M Pecora, and Francesco Sorrentino.

Symmetries in the time-averaged dynamics of networks: reducing
unnecessary complexity through minimal network models.
arXiv preprint arXiv:1710.05251, 2017.

Siddique A. B., UNM December 13, 2017 27 / 28

 Questions and Answers

Thank you

Questions?

Siddique A. B., UNM December 13, 2017 28 / 28