SlideShare a Scribd company logo
Spatial patterns in evolutionary games on
scale-free networks and multiplexes
Kaj Kolja Kleineberg | kkleineberg@ethz.ch
@KoljaKleineberg | koljakleineberg.wordpress.com
Evolutionary games on structured populations:
It's complicated!
Evolutionary games on structured populations:
It's complicated!
Does heterogeneity always favor cooperation? Spatial
effects in scale-free, clustered networks?
Real complex networks are scale-free and clustered
Clustering implies an underlying geometry
Scale-free clustered networks
can be embedded into hyperbolic space
“Hyperbolic geometry of complex networks” [PRE 82, 036106]
Distribute:
ρ(r) ∝ e
1
2
(γ−1)r
Connect:
p(xij) =
1
1 + e
xij−R
2T
xij = cosh−1
(cosh ri cosh rj
− sinh ri sinh rj cos ∆θij)
Scale-free clustered networks
can be embedded into hyperbolic space
“Hyperbolic geometry of complex networks” [PRE 82, 036106]
Distribute:
ρ(r) ∝ e
1
2
(γ−1)r
Connect:
p(xij) =
1
1 + e
xij−R
2T
xij = cosh−1
(cosh ri cosh rj
− sinh ri sinh rj cos ∆θij)
Scale-free clustered networks
can be embedded into hyperbolic space
“Hyperbolic geometry of complex networks” [PRE 82, 036106]
Distribute:
ρ(r) ∝ e
1
2
(γ−1)r
Connect:
p(xij) =
1
1 + e
xij−R
2T
xij = cosh−1
(cosh ri cosh rj
− sinh ri sinh rj cos ∆θij)
Real networks can be embedded into hyperbolic
space by inverting the model.
Hyperbolic maps of complex networks:
Poincaré disk
Nature Communications 1, 62 (2010)
Polar coordinates:
ri : Popularity (degree)
θi : Similarity
Distance:
xij = cosh−1
(cosh ri cosh rj
− sinh ri sinh rj cos ∆θij)
Connection probability:
p(xij) =
1
1 + e
xij−R
2T
Hyperbolic maps of complex networks:
Poincaré disk
Internet IPv6 topology
Polar coordinates:
ri : Popularity (degree)
θi : Similarity
Distance:
xij = cosh−1
(cosh ri cosh rj
− sinh ri sinh rj cos ∆θij)
Connection probability:
p(xij) =
1
1 + e
xij−R
2T
Hyperbolic maps of complex networks:
Poincaré disk
Internet IPv6 topology
Polar coordinates:
ri : Popularity (degree)
θi : Similarity
Distance:
xij = cosh−1
(cosh ri cosh rj
− sinh ri sinh rj cos ∆θij)
Connection probability:
p(xij) =
1
1 + e
xij−R
2T
Hyperbolic maps of complex networks:
Poincaré disk
Internet IPv6 topology
Polar coordinates:
ri : Popularity (degree)
θi : Similarity
Distance:
xij = cosh−1
(cosh ri cosh rj
− sinh ri sinh rj cos ∆θij)
Connection probability:
p(xij) =
1
1 + e
xij−R
2T
Temperature parameters related clustering
and the strength of the metric space
A: Low temperature (high mean local clustering, ¯c). B: High
temperature (low ¯c).
Individuals collect a payoff form playing with their neighbors
and update their strategy by imitation
Spatial patterns in evolutionary games on scale-free networks and multiplexes
Self-organization into metric clusters
allows cooperators to survive in social dilemmas
A B DC
E F HG
A B C
t
Prisoner’s dilemma, T = 1.2, S = −0.2
We can use the initial conditions
as a proxy of the effectiveness of different structures
Lack of analytical solution → Random initial conditions may not
reveal all possible solutions (no ergodicity)
We can use the initial conditions
as a proxy of the effectiveness of different structures
Lack of analytical solution → Random initial conditions may not
reveal all possible solutions (no ergodicity)
Random Hubs Connected cluster Metric cluster
FullgraphCooperatorsubgraph
Metric clusters can be better in sustaining cooperation than hubs
and heterogeneity can even hinder cooperation
/connected cluster
Prisoner's Dilemma, T=1.5, S=-0.5
Metric clusters can be better in sustaining cooperation than hubs
and heterogeneity can even hinder cooperation
/connected cluster
Prisoner's Dilemma, T=1.5, S=-0.5
Heterogeneity does not always favor—but can even
hinder—cooperation in social dilemmas.
Metric clusters or hubs can be more efficient
in sustaining cooperation depending on network topology
Abundance of intercluster links explains
why and when metric clusters are successful
Intercluster links
Connected cluster Metric cluster
Abundance of intercluster links explains
why and when metric clusters are successful
Intercluster links
Connected cluster Metric cluster
Metric clusters shield cooperators from surrounding
defectors similar to spatial selection.
Metric clusters as initial conditions
might even be more realistic than random ones
Nature Communications 1, 62 (2010)
Formation of metric clusters
in the dynamical navigation game
Cooperator
Defector
Message is sent
Message is lost
SuccessFailure
Source
Target
Sci. Rep. 7, 2897 (2017)
Formation of metric clusters
in the dynamical navigation game
Cooperator
Defector
Message is sent
Message is lost
SuccessFailure
Source
Target
Sci. Rep. 7, 2897 (2017)
Formation of metric clusters
in collective intelligence with minority incentives
Model from PNAS 114, 20:5077–5082
Human interactions take place in different domains:
Multiplex networks
Radial and angular coordinates are correlated
between different layers in many real multiplexes
Arx12
Arx42
Arx41
Arx28
Phys12
Arx52
Arx15
Arx26
Internet
Arx34
CE23
Phys13
Phys23
Sac13
Sac35
Sac23
Sac12
Dro12
CE13
Sac14
Sac24
Brain
Rattus
CE12
Sac34
AirTrain
0.0 0.2 0.4 0.6 0.8 1.0
0.0
0.2
0.4
0.6
Angular correlations (g)
Radialcorrelations(ν)
Model:
- Tune correlations
independently from
constituent layer
topologies
- Similarity (angular)
correlations: g ∈ [0, 1]
- Degree (radial)
correlations: ν ∈ [0, 1]
[Nature Physics 12, 1076–1081
(2016)]
Geometric correlations can lead to the formation
of coherent patterns among different layers
γ
β
GN
ON
+T+S
C D
Layer 1: Evolutionary games
Stag Hunt, Prisoner’s Dilemma
& imitation dynamics
Layer 2: Social influence
Voter model & bias towards
cooperation
Coupling: at each timestep, with probability
(1 − γ) perform respective dynamics in each layer
γ nodes copy their state from one layer to the other
Self-organization into clusters of cooperators
only occurs if angular correlations are present
Overlapping clusters of cooperators
also happen in the mutual prisoner's dilemma
2
1 1
2
1
2
1
2
a) b)
c) d)
Both layers play prisoner’s dilemma with the same coupling as before.
Summary: metric clusters in evolutionary games
on scale-free networks
- Cooperation can be sustained in metric clusters in scale-free
networks
- Metric clusters shield cooperators from surrounding
defectors (similar to spatial selection)
- Survival of metric clusters is favored if:
- The network is less heterogeneous
- The network has a higher clustering coefficient (lower
temperature, stronger metric structure)
- The clusters (networks) are larger
- If started with metric clusters, heterogeneity can even
hinder cooperation
- We find similar clusters for different games and on
correlated multiplexes
Reference:
»Metric clusters in evolutionary games on scale-free networks«
arXiv:1704.00952
K-K. Kleineberg
Kaj Kolja Kleineberg:
• kkleineberg@ethz.ch
• @KoljaKleineberg
• koljakleineberg.wordpress.com
Reference:
»Metric clusters in evolutionary games on scale-free networks«
arXiv:1704.00952
K-K. Kleineberg
Kaj Kolja Kleineberg:
• kkleineberg@ethz.ch
• @KoljaKleineberg ← Slides
• koljakleineberg.wordpress.com
Reference:
»Metric clusters in evolutionary games on scale-free networks«
arXiv:1704.00952
K-K. Kleineberg
Kaj Kolja Kleineberg:
• kkleineberg@ethz.ch
• @KoljaKleineberg ← Slides
• koljakleineberg.wordpress.com ← Data & Model
Ad

More Related Content

What's hot (18)

Towards a democratic, scalable, and sustainable digital future
Towards a democratic, scalable, and sustainable digital futureTowards a democratic, scalable, and sustainable digital future
Towards a democratic, scalable, and sustainable digital future
Kolja Kleineberg
 
Geographic routing in
Geographic routing inGeographic routing in
Geographic routing in
IMPULSE_TECHNOLOGY
 
A Proposed Algorithm to Detect the Largest Community Based On Depth Level
A Proposed Algorithm to Detect the Largest Community Based On Depth LevelA Proposed Algorithm to Detect the Largest Community Based On Depth Level
A Proposed Algorithm to Detect the Largest Community Based On Depth Level
Eswar Publications
 
Overlapping community detection in Large-Scale Networks using BigCLAM model b...
Overlapping community detection in Large-Scale Networks using BigCLAM model b...Overlapping community detection in Large-Scale Networks using BigCLAM model b...
Overlapping community detection in Large-Scale Networks using BigCLAM model b...
Thang Nguyen
 
The Neighborhood Broadcast Problem in Wireless Ad Hoc Sensor Networks
The Neighborhood Broadcast Problem in Wireless Ad Hoc Sensor NetworksThe Neighborhood Broadcast Problem in Wireless Ad Hoc Sensor Networks
The Neighborhood Broadcast Problem in Wireless Ad Hoc Sensor Networks
graphhoc
 
23
2323
23
IMPULSE_TECHNOLOGY
 
Network sampling, community detection
Network sampling, community detectionNetwork sampling, community detection
Network sampling, community detection
roberval mariano
 
A SIMULATION-BASED PERFORMANCE COMPARISON OF MANETS CDS CREATION ALGORITHMS U...
A SIMULATION-BASED PERFORMANCE COMPARISON OF MANETS CDS CREATION ALGORITHMS U...A SIMULATION-BASED PERFORMANCE COMPARISON OF MANETS CDS CREATION ALGORITHMS U...
A SIMULATION-BASED PERFORMANCE COMPARISON OF MANETS CDS CREATION ALGORITHMS U...
csandit
 
Community detection
Community detectionCommunity detection
Community detection
Scott Pauls
 
Community detection algorithms
Community detection algorithmsCommunity detection algorithms
Community detection algorithms
Alireza Andalib
 
Structure of triadic relations in multiplex (social) networks
Structure of triadic relations in multiplex (social) networksStructure of triadic relations in multiplex (social) networks
Structure of triadic relations in multiplex (social) networks
Emanuele Cozzo
 
Multiplex Networks: structure and dynamics
Multiplex Networks: structure and dynamicsMultiplex Networks: structure and dynamics
Multiplex Networks: structure and dynamics
Emanuele Cozzo
 
E XTENDED F AST S EARCH C LUSTERING A LGORITHM : W IDELY D ENSITY C LUSTERS ,...
E XTENDED F AST S EARCH C LUSTERING A LGORITHM : W IDELY D ENSITY C LUSTERS ,...E XTENDED F AST S EARCH C LUSTERING A LGORITHM : W IDELY D ENSITY C LUSTERS ,...
E XTENDED F AST S EARCH C LUSTERING A LGORITHM : W IDELY D ENSITY C LUSTERS ,...
csandit
 
Community Detection with Networkx
Community Detection with NetworkxCommunity Detection with Networkx
Community Detection with Networkx
Erika Fille Legara
 
Community Detection
Community Detection Community Detection
Community Detection
Kanika Kanwal
 
COMPARATIVE PERFORMANCE ANALYSIS OF RNSC AND MCL ALGORITHMS ON POWER-LAW DIST...
COMPARATIVE PERFORMANCE ANALYSIS OF RNSC AND MCL ALGORITHMS ON POWER-LAW DIST...COMPARATIVE PERFORMANCE ANALYSIS OF RNSC AND MCL ALGORITHMS ON POWER-LAW DIST...
COMPARATIVE PERFORMANCE ANALYSIS OF RNSC AND MCL ALGORITHMS ON POWER-LAW DIST...
acijjournal
 
Scalable community detection with the louvain algorithm
Scalable community detection with the louvain algorithmScalable community detection with the louvain algorithm
Scalable community detection with the louvain algorithm
Navid Sedighpour
 
Towards optimal broadcast in wireless networks
Towards optimal broadcast in wireless networks Towards optimal broadcast in wireless networks
Towards optimal broadcast in wireless networks
LogicMindtech Nologies
 
Towards a democratic, scalable, and sustainable digital future
Towards a democratic, scalable, and sustainable digital futureTowards a democratic, scalable, and sustainable digital future
Towards a democratic, scalable, and sustainable digital future
Kolja Kleineberg
 
A Proposed Algorithm to Detect the Largest Community Based On Depth Level
A Proposed Algorithm to Detect the Largest Community Based On Depth LevelA Proposed Algorithm to Detect the Largest Community Based On Depth Level
A Proposed Algorithm to Detect the Largest Community Based On Depth Level
Eswar Publications
 
Overlapping community detection in Large-Scale Networks using BigCLAM model b...
Overlapping community detection in Large-Scale Networks using BigCLAM model b...Overlapping community detection in Large-Scale Networks using BigCLAM model b...
Overlapping community detection in Large-Scale Networks using BigCLAM model b...
Thang Nguyen
 
The Neighborhood Broadcast Problem in Wireless Ad Hoc Sensor Networks
The Neighborhood Broadcast Problem in Wireless Ad Hoc Sensor NetworksThe Neighborhood Broadcast Problem in Wireless Ad Hoc Sensor Networks
The Neighborhood Broadcast Problem in Wireless Ad Hoc Sensor Networks
graphhoc
 
Network sampling, community detection
Network sampling, community detectionNetwork sampling, community detection
Network sampling, community detection
roberval mariano
 
A SIMULATION-BASED PERFORMANCE COMPARISON OF MANETS CDS CREATION ALGORITHMS U...
A SIMULATION-BASED PERFORMANCE COMPARISON OF MANETS CDS CREATION ALGORITHMS U...A SIMULATION-BASED PERFORMANCE COMPARISON OF MANETS CDS CREATION ALGORITHMS U...
A SIMULATION-BASED PERFORMANCE COMPARISON OF MANETS CDS CREATION ALGORITHMS U...
csandit
 
Community detection
Community detectionCommunity detection
Community detection
Scott Pauls
 
Community detection algorithms
Community detection algorithmsCommunity detection algorithms
Community detection algorithms
Alireza Andalib
 
Structure of triadic relations in multiplex (social) networks
Structure of triadic relations in multiplex (social) networksStructure of triadic relations in multiplex (social) networks
Structure of triadic relations in multiplex (social) networks
Emanuele Cozzo
 
Multiplex Networks: structure and dynamics
Multiplex Networks: structure and dynamicsMultiplex Networks: structure and dynamics
Multiplex Networks: structure and dynamics
Emanuele Cozzo
 
E XTENDED F AST S EARCH C LUSTERING A LGORITHM : W IDELY D ENSITY C LUSTERS ,...
E XTENDED F AST S EARCH C LUSTERING A LGORITHM : W IDELY D ENSITY C LUSTERS ,...E XTENDED F AST S EARCH C LUSTERING A LGORITHM : W IDELY D ENSITY C LUSTERS ,...
E XTENDED F AST S EARCH C LUSTERING A LGORITHM : W IDELY D ENSITY C LUSTERS ,...
csandit
 
Community Detection with Networkx
Community Detection with NetworkxCommunity Detection with Networkx
Community Detection with Networkx
Erika Fille Legara
 
Community Detection
Community Detection Community Detection
Community Detection
Kanika Kanwal
 
COMPARATIVE PERFORMANCE ANALYSIS OF RNSC AND MCL ALGORITHMS ON POWER-LAW DIST...
COMPARATIVE PERFORMANCE ANALYSIS OF RNSC AND MCL ALGORITHMS ON POWER-LAW DIST...COMPARATIVE PERFORMANCE ANALYSIS OF RNSC AND MCL ALGORITHMS ON POWER-LAW DIST...
COMPARATIVE PERFORMANCE ANALYSIS OF RNSC AND MCL ALGORITHMS ON POWER-LAW DIST...
acijjournal
 
Scalable community detection with the louvain algorithm
Scalable community detection with the louvain algorithmScalable community detection with the louvain algorithm
Scalable community detection with the louvain algorithm
Navid Sedighpour
 
Towards optimal broadcast in wireless networks
Towards optimal broadcast in wireless networks Towards optimal broadcast in wireless networks
Towards optimal broadcast in wireless networks
LogicMindtech Nologies
 

Similar to Spatial patterns in evolutionary games on scale-free networks and multiplexes (20)

An Introduction to Networks
An Introduction to NetworksAn Introduction to Networks
An Introduction to Networks
Francesco Gadaleta
 
CLIM Program: Remote Sensing Workshop, Multilayer Modeling and Analysis of Co...
CLIM Program: Remote Sensing Workshop, Multilayer Modeling and Analysis of Co...CLIM Program: Remote Sensing Workshop, Multilayer Modeling and Analysis of Co...
CLIM Program: Remote Sensing Workshop, Multilayer Modeling and Analysis of Co...
The Statistical and Applied Mathematical Sciences Institute
 
Higher-order clustering coefficients
Higher-order clustering coefficientsHigher-order clustering coefficients
Higher-order clustering coefficients
Austin Benson
 
ICPSR - Complex Systems Models in the Social Sciences - Lecture 3 - Professor...
ICPSR - Complex Systems Models in the Social Sciences - Lecture 3 - Professor...ICPSR - Complex Systems Models in the Social Sciences - Lecture 3 - Professor...
ICPSR - Complex Systems Models in the Social Sciences - Lecture 3 - Professor...
Daniel Katz
 
Higher-order clustering coefficients at Purdue CSoI
Higher-order clustering coefficients at Purdue CSoIHigher-order clustering coefficients at Purdue CSoI
Higher-order clustering coefficients at Purdue CSoI
Austin Benson
 
Quantum persistent k cores for community detection
Quantum persistent k cores for community detectionQuantum persistent k cores for community detection
Quantum persistent k cores for community detection
Colleen Farrelly
 
Using Spectral Clustering to find Successful Hero Combinations in DOTA 2
Using Spectral Clustering to find Successful Hero Combinations in DOTA 2Using Spectral Clustering to find Successful Hero Combinations in DOTA 2
Using Spectral Clustering to find Successful Hero Combinations in DOTA 2
Roderick Cox
 
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
Christopher Morris
 
Higher-order clustering coefficients
Higher-order clustering coefficientsHigher-order clustering coefficients
Higher-order clustering coefficients
Austin Benson
 
Socialnetworkanalysis (Tin180 Com)
Socialnetworkanalysis (Tin180 Com)Socialnetworkanalysis (Tin180 Com)
Socialnetworkanalysis (Tin180 Com)
Tin180 VietNam
 
Participation costs dismiss the advantage of heterogeneous networks in evolut...
Participation costs dismiss the advantage of heterogeneous networks in evolut...Participation costs dismiss the advantage of heterogeneous networks in evolut...
Participation costs dismiss the advantage of heterogeneous networks in evolut...
Naoki Masuda
 
Interpretation of the biological knowledge using networks approach
Interpretation of the biological knowledge using networks approachInterpretation of the biological knowledge using networks approach
Interpretation of the biological knowledge using networks approach
Elena Sügis
 
08 Exponential Random Graph Models (2016)
08 Exponential Random Graph Models (2016)08 Exponential Random Graph Models (2016)
08 Exponential Random Graph Models (2016)
Duke Network Analysis Center
 
08 Exponential Random Graph Models (ERGM)
08 Exponential Random Graph Models (ERGM)08 Exponential Random Graph Models (ERGM)
08 Exponential Random Graph Models (ERGM)
dnac
 
Topology ppt
Topology pptTopology ppt
Topology ppt
Daksh Bapna
 
Contextual ontology alignment may 2011
Contextual ontology alignment may 2011Contextual ontology alignment may 2011
Contextual ontology alignment may 2011
Mariana Damova, Ph.D
 
240401_JW_labseminar[LINE: Large-scale Information Network Embeddin].pptx
240401_JW_labseminar[LINE: Large-scale Information Network Embeddin].pptx240401_JW_labseminar[LINE: Large-scale Information Network Embeddin].pptx
240401_JW_labseminar[LINE: Large-scale Information Network Embeddin].pptx
thanhdowork
 
240708_JW_labseminar[struc2vec: Learning Node Representations from Structural...
240708_JW_labseminar[struc2vec: Learning Node Representations from Structural...240708_JW_labseminar[struc2vec: Learning Node Representations from Structural...
240708_JW_labseminar[struc2vec: Learning Node Representations from Structural...
thanhdowork
 
Spectral clustering with motifs and higher-order structures
Spectral clustering with motifs and higher-order structuresSpectral clustering with motifs and higher-order structures
Spectral clustering with motifs and higher-order structures
David Gleich
 
Clique-based Network Clustering
Clique-based Network ClusteringClique-based Network Clustering
Clique-based Network Clustering
Guang Ouyang
 
Higher-order clustering coefficients
Higher-order clustering coefficientsHigher-order clustering coefficients
Higher-order clustering coefficients
Austin Benson
 
ICPSR - Complex Systems Models in the Social Sciences - Lecture 3 - Professor...
ICPSR - Complex Systems Models in the Social Sciences - Lecture 3 - Professor...ICPSR - Complex Systems Models in the Social Sciences - Lecture 3 - Professor...
ICPSR - Complex Systems Models in the Social Sciences - Lecture 3 - Professor...
Daniel Katz
 
Higher-order clustering coefficients at Purdue CSoI
Higher-order clustering coefficients at Purdue CSoIHigher-order clustering coefficients at Purdue CSoI
Higher-order clustering coefficients at Purdue CSoI
Austin Benson
 
Quantum persistent k cores for community detection
Quantum persistent k cores for community detectionQuantum persistent k cores for community detection
Quantum persistent k cores for community detection
Colleen Farrelly
 
Using Spectral Clustering to find Successful Hero Combinations in DOTA 2
Using Spectral Clustering to find Successful Hero Combinations in DOTA 2Using Spectral Clustering to find Successful Hero Combinations in DOTA 2
Using Spectral Clustering to find Successful Hero Combinations in DOTA 2
Roderick Cox
 
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
Christopher Morris
 
Higher-order clustering coefficients
Higher-order clustering coefficientsHigher-order clustering coefficients
Higher-order clustering coefficients
Austin Benson
 
Socialnetworkanalysis (Tin180 Com)
Socialnetworkanalysis (Tin180 Com)Socialnetworkanalysis (Tin180 Com)
Socialnetworkanalysis (Tin180 Com)
Tin180 VietNam
 
Participation costs dismiss the advantage of heterogeneous networks in evolut...
Participation costs dismiss the advantage of heterogeneous networks in evolut...Participation costs dismiss the advantage of heterogeneous networks in evolut...
Participation costs dismiss the advantage of heterogeneous networks in evolut...
Naoki Masuda
 
Interpretation of the biological knowledge using networks approach
Interpretation of the biological knowledge using networks approachInterpretation of the biological knowledge using networks approach
Interpretation of the biological knowledge using networks approach
Elena Sügis
 
08 Exponential Random Graph Models (ERGM)
08 Exponential Random Graph Models (ERGM)08 Exponential Random Graph Models (ERGM)
08 Exponential Random Graph Models (ERGM)
dnac
 
Contextual ontology alignment may 2011
Contextual ontology alignment may 2011Contextual ontology alignment may 2011
Contextual ontology alignment may 2011
Mariana Damova, Ph.D
 
240401_JW_labseminar[LINE: Large-scale Information Network Embeddin].pptx
240401_JW_labseminar[LINE: Large-scale Information Network Embeddin].pptx240401_JW_labseminar[LINE: Large-scale Information Network Embeddin].pptx
240401_JW_labseminar[LINE: Large-scale Information Network Embeddin].pptx
thanhdowork
 
240708_JW_labseminar[struc2vec: Learning Node Representations from Structural...
240708_JW_labseminar[struc2vec: Learning Node Representations from Structural...240708_JW_labseminar[struc2vec: Learning Node Representations from Structural...
240708_JW_labseminar[struc2vec: Learning Node Representations from Structural...
thanhdowork
 
Spectral clustering with motifs and higher-order structures
Spectral clustering with motifs and higher-order structuresSpectral clustering with motifs and higher-order structures
Spectral clustering with motifs and higher-order structures
David Gleich
 
Clique-based Network Clustering
Clique-based Network ClusteringClique-based Network Clustering
Clique-based Network Clustering
Guang Ouyang
 
Ad

More from Kolja Kleineberg (9)

Catastrophic instabilities in interacting networks and possible remedies
Catastrophic instabilities in interacting networks and possible remediesCatastrophic instabilities in interacting networks and possible remedies
Catastrophic instabilities in interacting networks and possible remedies
Kolja Kleineberg
 
(Digital) networks and the science of complex systems
(Digital) networks and the science of complex systems(Digital) networks and the science of complex systems
(Digital) networks and the science of complex systems
Kolja Kleineberg
 
Towards a democratic, scalable, and sustainable digital future (a complex sys...
Towards a democratic, scalable, and sustainable digital future (a complex sys...Towards a democratic, scalable, and sustainable digital future (a complex sys...
Towards a democratic, scalable, and sustainable digital future (a complex sys...
Kolja Kleineberg
 
Re-inventing society in the digital age: Catastrophic instabilities in intera...
Re-inventing society in the digital age: Catastrophic instabilities in intera...Re-inventing society in the digital age: Catastrophic instabilities in intera...
Re-inventing society in the digital age: Catastrophic instabilities in intera...
Kolja Kleineberg
 
Is bigger always better? How local online social networks can outperform glob...
Is bigger always better? How local online social networks can outperform glob...Is bigger always better? How local online social networks can outperform glob...
Is bigger always better? How local online social networks can outperform glob...
Kolja Kleineberg
 
Ecology 2.0: Coexistence and domination among interacting networks
Ecology 2.0: Coexistence and domination among interacting networksEcology 2.0: Coexistence and domination among interacting networks
Ecology 2.0: Coexistence and domination among interacting networks
Kolja Kleineberg
 
A 1:1000 scale model of the digital world
A 1:1000 scale model of the digital worldA 1:1000 scale model of the digital world
A 1:1000 scale model of the digital world
Kolja Kleineberg
 
From the Evolution of Online Social Networks to Digital Ecology in a Nutshell
From the Evolution of Online Social Networks to Digital Ecology in a NutshellFrom the Evolution of Online Social Networks to Digital Ecology in a Nutshell
From the Evolution of Online Social Networks to Digital Ecology in a Nutshell
Kolja Kleineberg
 
Evolution and Ecology of the Digital World
Evolution and Ecology of the Digital WorldEvolution and Ecology of the Digital World
Evolution and Ecology of the Digital World
Kolja Kleineberg
 
Catastrophic instabilities in interacting networks and possible remedies
Catastrophic instabilities in interacting networks and possible remediesCatastrophic instabilities in interacting networks and possible remedies
Catastrophic instabilities in interacting networks and possible remedies
Kolja Kleineberg
 
(Digital) networks and the science of complex systems
(Digital) networks and the science of complex systems(Digital) networks and the science of complex systems
(Digital) networks and the science of complex systems
Kolja Kleineberg
 
Towards a democratic, scalable, and sustainable digital future (a complex sys...
Towards a democratic, scalable, and sustainable digital future (a complex sys...Towards a democratic, scalable, and sustainable digital future (a complex sys...
Towards a democratic, scalable, and sustainable digital future (a complex sys...
Kolja Kleineberg
 
Re-inventing society in the digital age: Catastrophic instabilities in intera...
Re-inventing society in the digital age: Catastrophic instabilities in intera...Re-inventing society in the digital age: Catastrophic instabilities in intera...
Re-inventing society in the digital age: Catastrophic instabilities in intera...
Kolja Kleineberg
 
Is bigger always better? How local online social networks can outperform glob...
Is bigger always better? How local online social networks can outperform glob...Is bigger always better? How local online social networks can outperform glob...
Is bigger always better? How local online social networks can outperform glob...
Kolja Kleineberg
 
Ecology 2.0: Coexistence and domination among interacting networks
Ecology 2.0: Coexistence and domination among interacting networksEcology 2.0: Coexistence and domination among interacting networks
Ecology 2.0: Coexistence and domination among interacting networks
Kolja Kleineberg
 
A 1:1000 scale model of the digital world
A 1:1000 scale model of the digital worldA 1:1000 scale model of the digital world
A 1:1000 scale model of the digital world
Kolja Kleineberg
 
From the Evolution of Online Social Networks to Digital Ecology in a Nutshell
From the Evolution of Online Social Networks to Digital Ecology in a NutshellFrom the Evolution of Online Social Networks to Digital Ecology in a Nutshell
From the Evolution of Online Social Networks to Digital Ecology in a Nutshell
Kolja Kleineberg
 
Evolution and Ecology of the Digital World
Evolution and Ecology of the Digital WorldEvolution and Ecology of the Digital World
Evolution and Ecology of the Digital World
Kolja Kleineberg
 
Ad

Recently uploaded (20)

Evidence for a polar circumbinary exoplanet orbiting a pair of eclipsing brow...
Evidence for a polar circumbinary exoplanet orbiting a pair of eclipsing brow...Evidence for a polar circumbinary exoplanet orbiting a pair of eclipsing brow...
Evidence for a polar circumbinary exoplanet orbiting a pair of eclipsing brow...
Sérgio Sacani
 
Secondary metabolite ,Plants and Health Care
Secondary metabolite ,Plants and Health CareSecondary metabolite ,Plants and Health Care
Secondary metabolite ,Plants and Health Care
Nistarini College, Purulia (W.B) India
 
Proprioceptors_ receptors of muscle_tendon
Proprioceptors_ receptors of muscle_tendonProprioceptors_ receptors of muscle_tendon
Proprioceptors_ receptors of muscle_tendon
klynct
 
Batteries and fuel cells for btech first year
Batteries and fuel cells for btech first yearBatteries and fuel cells for btech first year
Batteries and fuel cells for btech first year
MithilPillai1
 
Pharmacologically active constituents.pdf
Pharmacologically active constituents.pdfPharmacologically active constituents.pdf
Pharmacologically active constituents.pdf
Nistarini College, Purulia (W.B) India
 
An upper limit to the lifetime of stellar remnants from gravitational pair pr...
An upper limit to the lifetime of stellar remnants from gravitational pair pr...An upper limit to the lifetime of stellar remnants from gravitational pair pr...
An upper limit to the lifetime of stellar remnants from gravitational pair pr...
Sérgio Sacani
 
Black hole and its division and categories
Black hole and its division and categoriesBlack hole and its division and categories
Black hole and its division and categories
MSafiullahALawi
 
Components of the Human Circulatory System.pptx
Components of the Human  Circulatory System.pptxComponents of the Human  Circulatory System.pptx
Components of the Human Circulatory System.pptx
autumnstreaks
 
Reticular formation_groups_organization_
Reticular formation_groups_organization_Reticular formation_groups_organization_
Reticular formation_groups_organization_
klynct
 
Top 10 Biotech Startups for Beginners.pptx
Top 10 Biotech Startups for Beginners.pptxTop 10 Biotech Startups for Beginners.pptx
Top 10 Biotech Startups for Beginners.pptx
alexbagheriam
 
anatomy of larynx , trachea and bronchi ppt.
anatomy of larynx , trachea and bronchi ppt.anatomy of larynx , trachea and bronchi ppt.
anatomy of larynx , trachea and bronchi ppt.
EmanHamada5
 
Sleep_physiology_types_duration_underlying mech.
Sleep_physiology_types_duration_underlying mech.Sleep_physiology_types_duration_underlying mech.
Sleep_physiology_types_duration_underlying mech.
klynct
 
Siver Nanoparticles syntheisis, mechanism, Antibacterial activity.pptx
Siver Nanoparticles syntheisis, mechanism, Antibacterial activity.pptxSiver Nanoparticles syntheisis, mechanism, Antibacterial activity.pptx
Siver Nanoparticles syntheisis, mechanism, Antibacterial activity.pptx
PriyaAntil3
 
Study in Pink (forensic case study of Death)
Study in Pink (forensic case study of Death)Study in Pink (forensic case study of Death)
Study in Pink (forensic case study of Death)
memesologiesxd
 
MC III Prodrug Medicinal Chemistry III PPT
MC III Prodrug Medicinal Chemistry III PPTMC III Prodrug Medicinal Chemistry III PPT
MC III Prodrug Medicinal Chemistry III PPT
HRUTUJA WAGH
 
Discrete choice experiments: Environmental Improvements to Airthrey Loch Lake...
Discrete choice experiments: Environmental Improvements to Airthrey Loch Lake...Discrete choice experiments: Environmental Improvements to Airthrey Loch Lake...
Discrete choice experiments: Environmental Improvements to Airthrey Loch Lake...
Professional Content Writing's
 
Somato_Sensory _ somatomotor_Nervous_System.pptx
Somato_Sensory _ somatomotor_Nervous_System.pptxSomato_Sensory _ somatomotor_Nervous_System.pptx
Somato_Sensory _ somatomotor_Nervous_System.pptx
klynct
 
SULPHONAMIDES AND SULFONES Medicinal Chemistry III.ppt
SULPHONAMIDES AND SULFONES Medicinal Chemistry III.pptSULPHONAMIDES AND SULFONES Medicinal Chemistry III.ppt
SULPHONAMIDES AND SULFONES Medicinal Chemistry III.ppt
HRUTUJA WAGH
 
Cleaned_Expanded_Metal_Nanoparticles_Presentation.pptx
Cleaned_Expanded_Metal_Nanoparticles_Presentation.pptxCleaned_Expanded_Metal_Nanoparticles_Presentation.pptx
Cleaned_Expanded_Metal_Nanoparticles_Presentation.pptx
zainab98aug
 
Seismic evidence of liquid water at the base of Mars' upper crust
Seismic evidence of liquid water at the base of Mars' upper crustSeismic evidence of liquid water at the base of Mars' upper crust
Seismic evidence of liquid water at the base of Mars' upper crust
Sérgio Sacani
 
Evidence for a polar circumbinary exoplanet orbiting a pair of eclipsing brow...
Evidence for a polar circumbinary exoplanet orbiting a pair of eclipsing brow...Evidence for a polar circumbinary exoplanet orbiting a pair of eclipsing brow...
Evidence for a polar circumbinary exoplanet orbiting a pair of eclipsing brow...
Sérgio Sacani
 
Proprioceptors_ receptors of muscle_tendon
Proprioceptors_ receptors of muscle_tendonProprioceptors_ receptors of muscle_tendon
Proprioceptors_ receptors of muscle_tendon
klynct
 
Batteries and fuel cells for btech first year
Batteries and fuel cells for btech first yearBatteries and fuel cells for btech first year
Batteries and fuel cells for btech first year
MithilPillai1
 
An upper limit to the lifetime of stellar remnants from gravitational pair pr...
An upper limit to the lifetime of stellar remnants from gravitational pair pr...An upper limit to the lifetime of stellar remnants from gravitational pair pr...
An upper limit to the lifetime of stellar remnants from gravitational pair pr...
Sérgio Sacani
 
Black hole and its division and categories
Black hole and its division and categoriesBlack hole and its division and categories
Black hole and its division and categories
MSafiullahALawi
 
Components of the Human Circulatory System.pptx
Components of the Human  Circulatory System.pptxComponents of the Human  Circulatory System.pptx
Components of the Human Circulatory System.pptx
autumnstreaks
 
Reticular formation_groups_organization_
Reticular formation_groups_organization_Reticular formation_groups_organization_
Reticular formation_groups_organization_
klynct
 
Top 10 Biotech Startups for Beginners.pptx
Top 10 Biotech Startups for Beginners.pptxTop 10 Biotech Startups for Beginners.pptx
Top 10 Biotech Startups for Beginners.pptx
alexbagheriam
 
anatomy of larynx , trachea and bronchi ppt.
anatomy of larynx , trachea and bronchi ppt.anatomy of larynx , trachea and bronchi ppt.
anatomy of larynx , trachea and bronchi ppt.
EmanHamada5
 
Sleep_physiology_types_duration_underlying mech.
Sleep_physiology_types_duration_underlying mech.Sleep_physiology_types_duration_underlying mech.
Sleep_physiology_types_duration_underlying mech.
klynct
 
Siver Nanoparticles syntheisis, mechanism, Antibacterial activity.pptx
Siver Nanoparticles syntheisis, mechanism, Antibacterial activity.pptxSiver Nanoparticles syntheisis, mechanism, Antibacterial activity.pptx
Siver Nanoparticles syntheisis, mechanism, Antibacterial activity.pptx
PriyaAntil3
 
Study in Pink (forensic case study of Death)
Study in Pink (forensic case study of Death)Study in Pink (forensic case study of Death)
Study in Pink (forensic case study of Death)
memesologiesxd
 
MC III Prodrug Medicinal Chemistry III PPT
MC III Prodrug Medicinal Chemistry III PPTMC III Prodrug Medicinal Chemistry III PPT
MC III Prodrug Medicinal Chemistry III PPT
HRUTUJA WAGH
 
Discrete choice experiments: Environmental Improvements to Airthrey Loch Lake...
Discrete choice experiments: Environmental Improvements to Airthrey Loch Lake...Discrete choice experiments: Environmental Improvements to Airthrey Loch Lake...
Discrete choice experiments: Environmental Improvements to Airthrey Loch Lake...
Professional Content Writing's
 
Somato_Sensory _ somatomotor_Nervous_System.pptx
Somato_Sensory _ somatomotor_Nervous_System.pptxSomato_Sensory _ somatomotor_Nervous_System.pptx
Somato_Sensory _ somatomotor_Nervous_System.pptx
klynct
 
SULPHONAMIDES AND SULFONES Medicinal Chemistry III.ppt
SULPHONAMIDES AND SULFONES Medicinal Chemistry III.pptSULPHONAMIDES AND SULFONES Medicinal Chemistry III.ppt
SULPHONAMIDES AND SULFONES Medicinal Chemistry III.ppt
HRUTUJA WAGH
 
Cleaned_Expanded_Metal_Nanoparticles_Presentation.pptx
Cleaned_Expanded_Metal_Nanoparticles_Presentation.pptxCleaned_Expanded_Metal_Nanoparticles_Presentation.pptx
Cleaned_Expanded_Metal_Nanoparticles_Presentation.pptx
zainab98aug
 
Seismic evidence of liquid water at the base of Mars' upper crust
Seismic evidence of liquid water at the base of Mars' upper crustSeismic evidence of liquid water at the base of Mars' upper crust
Seismic evidence of liquid water at the base of Mars' upper crust
Sérgio Sacani
 

Spatial patterns in evolutionary games on scale-free networks and multiplexes

  • 1. Spatial patterns in evolutionary games on scale-free networks and multiplexes Kaj Kolja Kleineberg | kkleineberg@ethz.ch @KoljaKleineberg | koljakleineberg.wordpress.com
  • 2. Evolutionary games on structured populations: It's complicated!
  • 3. Evolutionary games on structured populations: It's complicated! Does heterogeneity always favor cooperation? Spatial effects in scale-free, clustered networks?
  • 4. Real complex networks are scale-free and clustered Clustering implies an underlying geometry
  • 5. Scale-free clustered networks can be embedded into hyperbolic space “Hyperbolic geometry of complex networks” [PRE 82, 036106] Distribute: ρ(r) ∝ e 1 2 (γ−1)r Connect: p(xij) = 1 1 + e xij−R 2T xij = cosh−1 (cosh ri cosh rj − sinh ri sinh rj cos ∆θij)
  • 6. Scale-free clustered networks can be embedded into hyperbolic space “Hyperbolic geometry of complex networks” [PRE 82, 036106] Distribute: ρ(r) ∝ e 1 2 (γ−1)r Connect: p(xij) = 1 1 + e xij−R 2T xij = cosh−1 (cosh ri cosh rj − sinh ri sinh rj cos ∆θij)
  • 7. Scale-free clustered networks can be embedded into hyperbolic space “Hyperbolic geometry of complex networks” [PRE 82, 036106] Distribute: ρ(r) ∝ e 1 2 (γ−1)r Connect: p(xij) = 1 1 + e xij−R 2T xij = cosh−1 (cosh ri cosh rj − sinh ri sinh rj cos ∆θij) Real networks can be embedded into hyperbolic space by inverting the model.
  • 8. Hyperbolic maps of complex networks: Poincaré disk Nature Communications 1, 62 (2010) Polar coordinates: ri : Popularity (degree) θi : Similarity Distance: xij = cosh−1 (cosh ri cosh rj − sinh ri sinh rj cos ∆θij) Connection probability: p(xij) = 1 1 + e xij−R 2T
  • 9. Hyperbolic maps of complex networks: Poincaré disk Internet IPv6 topology Polar coordinates: ri : Popularity (degree) θi : Similarity Distance: xij = cosh−1 (cosh ri cosh rj − sinh ri sinh rj cos ∆θij) Connection probability: p(xij) = 1 1 + e xij−R 2T
  • 10. Hyperbolic maps of complex networks: Poincaré disk Internet IPv6 topology Polar coordinates: ri : Popularity (degree) θi : Similarity Distance: xij = cosh−1 (cosh ri cosh rj − sinh ri sinh rj cos ∆θij) Connection probability: p(xij) = 1 1 + e xij−R 2T
  • 11. Hyperbolic maps of complex networks: Poincaré disk Internet IPv6 topology Polar coordinates: ri : Popularity (degree) θi : Similarity Distance: xij = cosh−1 (cosh ri cosh rj − sinh ri sinh rj cos ∆θij) Connection probability: p(xij) = 1 1 + e xij−R 2T
  • 12. Temperature parameters related clustering and the strength of the metric space A: Low temperature (high mean local clustering, ¯c). B: High temperature (low ¯c).
  • 13. Individuals collect a payoff form playing with their neighbors and update their strategy by imitation
  • 15. Self-organization into metric clusters allows cooperators to survive in social dilemmas A B DC E F HG A B C t Prisoner’s dilemma, T = 1.2, S = −0.2
  • 16. We can use the initial conditions as a proxy of the effectiveness of different structures Lack of analytical solution → Random initial conditions may not reveal all possible solutions (no ergodicity)
  • 17. We can use the initial conditions as a proxy of the effectiveness of different structures Lack of analytical solution → Random initial conditions may not reveal all possible solutions (no ergodicity) Random Hubs Connected cluster Metric cluster FullgraphCooperatorsubgraph
  • 18. Metric clusters can be better in sustaining cooperation than hubs and heterogeneity can even hinder cooperation /connected cluster Prisoner's Dilemma, T=1.5, S=-0.5
  • 19. Metric clusters can be better in sustaining cooperation than hubs and heterogeneity can even hinder cooperation /connected cluster Prisoner's Dilemma, T=1.5, S=-0.5 Heterogeneity does not always favor—but can even hinder—cooperation in social dilemmas.
  • 20. Metric clusters or hubs can be more efficient in sustaining cooperation depending on network topology
  • 21. Abundance of intercluster links explains why and when metric clusters are successful Intercluster links Connected cluster Metric cluster
  • 22. Abundance of intercluster links explains why and when metric clusters are successful Intercluster links Connected cluster Metric cluster Metric clusters shield cooperators from surrounding defectors similar to spatial selection.
  • 23. Metric clusters as initial conditions might even be more realistic than random ones Nature Communications 1, 62 (2010)
  • 24. Formation of metric clusters in the dynamical navigation game Cooperator Defector Message is sent Message is lost SuccessFailure Source Target Sci. Rep. 7, 2897 (2017)
  • 25. Formation of metric clusters in the dynamical navigation game Cooperator Defector Message is sent Message is lost SuccessFailure Source Target Sci. Rep. 7, 2897 (2017)
  • 26. Formation of metric clusters in collective intelligence with minority incentives Model from PNAS 114, 20:5077–5082
  • 27. Human interactions take place in different domains: Multiplex networks
  • 28. Radial and angular coordinates are correlated between different layers in many real multiplexes Arx12 Arx42 Arx41 Arx28 Phys12 Arx52 Arx15 Arx26 Internet Arx34 CE23 Phys13 Phys23 Sac13 Sac35 Sac23 Sac12 Dro12 CE13 Sac14 Sac24 Brain Rattus CE12 Sac34 AirTrain 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 Angular correlations (g) Radialcorrelations(ν) Model: - Tune correlations independently from constituent layer topologies - Similarity (angular) correlations: g ∈ [0, 1] - Degree (radial) correlations: ν ∈ [0, 1] [Nature Physics 12, 1076–1081 (2016)]
  • 29. Geometric correlations can lead to the formation of coherent patterns among different layers γ β GN ON +T+S C D Layer 1: Evolutionary games Stag Hunt, Prisoner’s Dilemma & imitation dynamics Layer 2: Social influence Voter model & bias towards cooperation Coupling: at each timestep, with probability (1 − γ) perform respective dynamics in each layer γ nodes copy their state from one layer to the other
  • 30. Self-organization into clusters of cooperators only occurs if angular correlations are present
  • 31. Overlapping clusters of cooperators also happen in the mutual prisoner's dilemma 2 1 1 2 1 2 1 2 a) b) c) d) Both layers play prisoner’s dilemma with the same coupling as before.
  • 32. Summary: metric clusters in evolutionary games on scale-free networks - Cooperation can be sustained in metric clusters in scale-free networks - Metric clusters shield cooperators from surrounding defectors (similar to spatial selection) - Survival of metric clusters is favored if: - The network is less heterogeneous - The network has a higher clustering coefficient (lower temperature, stronger metric structure) - The clusters (networks) are larger - If started with metric clusters, heterogeneity can even hinder cooperation - We find similar clusters for different games and on correlated multiplexes
  • 33. Reference: »Metric clusters in evolutionary games on scale-free networks« arXiv:1704.00952 K-K. Kleineberg Kaj Kolja Kleineberg: • kkleineberg@ethz.ch • @KoljaKleineberg • koljakleineberg.wordpress.com
  • 34. Reference: »Metric clusters in evolutionary games on scale-free networks« arXiv:1704.00952 K-K. Kleineberg Kaj Kolja Kleineberg: • kkleineberg@ethz.ch • @KoljaKleineberg ← Slides • koljakleineberg.wordpress.com
  • 35. Reference: »Metric clusters in evolutionary games on scale-free networks« arXiv:1704.00952 K-K. Kleineberg Kaj Kolja Kleineberg: • kkleineberg@ethz.ch • @KoljaKleineberg ← Slides • koljakleineberg.wordpress.com ← Data & Model
  翻译: