Robustness of complex networks (project): Difference between revisions
From Santa Fe Institute Events Wiki
| (30 intermediate revisions by 8 users not shown) | |||
| Line 1: | Line 1: | ||
[[File:Zoo.png|thumb|300px|Fig. 1. Zoo of complex networks (an example). Taken from Sol´e and Valverde, 2001.]] | [[File:Zoo.png|thumb|300px|Fig. 1. Zoo of complex networks (an example). Taken from Sol´e and Valverde, 2001.]] | ||
== Problem statement == | |||
Complex networks have various properties which can be measured in real networks (WWW, social networks, biological networks), e.g. degree distribution, modularity, hierarchy, assortativity etc. Robustness of complex networks is a big question, however only some progress have been done in this direction. For example, it was shown that the scale-free networks are much more topologically robust to random attacks than random networks. Many people claim that various characteristics of complex networks will influence the robustness interdependently. The question I am interested in is how? | Complex networks have various properties which can be measured in real networks (WWW, social networks, biological networks), e.g. degree distribution, modularity, hierarchy, assortativity etc. Robustness of complex networks is a big question, however only some progress have been done in this direction. For example, it was shown that the scale-free networks are much more topologically robust to random attacks than random networks. Many people claim that various characteristics of complex networks will influence the robustness interdependently. The question I am interested in is how? | ||
== Approach == | |||
The idea is to generate continuous topology space of various complex networks (networks with different modularity, degree distribution, hierarchy etc) and use it to measure their robustness (see Fig. 1). There are many approaches to measure the robustness of complex networks. For example we can remove edges of vertices of a complex network graph and look at the size of a giant cluster. We can discuss other possibilities. | The idea is to generate continuous topology space of various complex networks (networks with different modularity, degree distribution, hierarchy etc) and use it to measure their robustness (see Fig. 1). There are many approaches to measure the robustness of complex networks. For example we can remove edges of vertices of a complex network graph and look at the size of a giant cluster. We can discuss other possibilities. | ||
If you are interested you can contact me directly or via my E-mail: krystoferivanov@gmail.com or via my [[Oleksandr Ivanov|discussion page in CSSS 2012 wiki]]. | If you are interested you can contact me directly or via my E-mail: krystoferivanov@gmail.com or via my [[Oleksandr Ivanov|discussion page in CSSS 2012 wiki]]. | ||
== Relevant literature == | |||
* [http://www.barabasilab.com/pubs/CCNR-ALB_Publications/199910-15_Science-Emergence/199910-15_Science-Emergence.pdf BA Scale-free network] | * ''Important papers about network generation are highlighted in bold'' | ||
* [http://people.maths.ox.ac.uk/maini/PKM%20publications/195.pdf How to generate Scale-free modular network using preferential attachment] | * '''[http://www.barabasilab.com/pubs/CCNR-ALB_Publications/199910-15_Science-Emergence/199910-15_Science-Emergence.pdf BA Scale-free network]''' | ||
* '''[http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200201-30_RevModernPhys-StatisticalMech/200201-30_RevModernPhys-StatisticalMech.pdf Statistical mechanics of complex networks]''' | |||
* '''[http://arxiv.org/pdf/cond-mat/0405381v2.pdf Random Networks with Tunable Degree Distribution and Clustering]''' | |||
* '''[http://nlsc.ustc.edu.cn/phpcms/uploadfile/common/research/1.topology%20structure/10.pdf Scale-free small world network with tunable assortative coefficient]''' | |||
* '''[http://people.maths.ox.ac.uk/maini/PKM%20publications/195.pdf How to generate Scale-free modular network using preferential attachment]''' | |||
* '''[http://arxiv.org/pdf/cond-mat/0402009v1.pdf Scale-free networks with tunable degree distribution exponents]''' | |||
* '''[http://arxiv.org/pdf/cond-mat/0110452v1.pdf Scale free networks with tunable clustering]''' | |||
* [http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200007-27_Nature-ErrorAttack/200007-27_Nature-ErrorAttack.pdf Error and attack tollerance of complex networks] | * [http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200007-27_Nature-ErrorAttack/200007-27_Nature-ErrorAttack.pdf Error and attack tollerance of complex networks] | ||
* [http://vw.indiana.edu/netsci06/conference/Ng_Structural.pdf Structural Robustness of Complex networks] | * [http://vw.indiana.edu/netsci06/conference/Ng_Structural.pdf Structural Robustness of Complex networks] | ||
* [http://arxiv.org/pdf/cond-mat/0205405.pdf Assortative mixing in networks] | * [http://arxiv.org/pdf/cond-mat/0205405.pdf Assortative mixing in networks] | ||
| Line 24: | Line 26: | ||
* [http://arxiv.org/ftp/cond-mat/papers/0202/0202410.pdf Attack vulnerability of complex networks] | * [http://arxiv.org/ftp/cond-mat/papers/0202/0202410.pdf Attack vulnerability of complex networks] | ||
* [http://jmvidal.cse.sc.edu/papers/nair11a.pdf Supply Network Topology and Robustness against Disruptions – an investigation using multi agent model] | * [http://jmvidal.cse.sc.edu/papers/nair11a.pdf Supply Network Topology and Robustness against Disruptions – an investigation using multi agent model] | ||
* [http://arxiv.org/abs/cond-mat/0007235 Random graphs with arbitrary degree distributions and their applications] | |||
* [http://www.pnas.org/content/104/1/36 Resolution limit in community detection] - about a typical modularity measure and its limitations | |||
* Add a relevant paper... | * Add a relevant paper... | ||
| Line 29: | Line 34: | ||
== Learning Python == | == Learning Python == | ||
* [http://code.google.com/edu/languages/google-python-class/ Google's Python Class] | * [http://code.google.com/edu/languages/google-python-class/ Google's Python Class] | ||
* [http://networkx.lanl.gov/tutorial/tutorial.html Networkx Python lybrary] | |||
* [http://networkx.lanl.gov/reference/algorithms.html Networkx graph algorithms] | |||
* [http://networkx.lanl.gov/reference/drawing.html Networkx drawing] | |||
== Participants == | |||
# [[Oleksandr Ivanov]] - krystoferivanov@gmail.com | |||
# [[Ian Wood]] - ibwood@indiana.edu | |||
# [[Xin Lu]] - xin.lu@ki.se | |||
# [[Duenas-Esterling Marco-Antonio]] - maduenase@gmail.com | |||
# [[Katrien Beuls]] - katrien@ai.vub.ac.be | |||
# [[Cameron Ray Smith]] - <span class="plainlinks"> [http://www.google.com/recaptcha/mailhide/d?k=01_G1kMsuOrJhiwcXbYs5uYQ==&c=4iKaQQLKYQ-uUaepLzz3_1LdZfwZMM24y5sG4GTjP-4= c...@gmail.com] | |||
# [[Abigail Horn]] - abbyhorn@mit.edu | |||
# Nona Karalashvili - nona.karalashvili@gmail.com | |||
</span> | |||
== Source Control == | |||
I've set up a github repository for any python source we write [https://github.com/ibwood/CSSS-Network-Robustness-Project here]. | |||
To figure out how to use Git look [http://git-scm.com/book here]. Chapters 1,2,3, and 5 are particularly relevant, but I can run through the basics with anyone. It's useful to have a source control for both project coordination and backup, and git is very simple once you get the hang of it. | |||
There is a shared folder on skype, please either sign your email in the participant list or drop a email to [[Xin Lu]] to access the generated network data. Dropbox link [https://www.dropbox.com/sh/y6e5ukftde4yt7x/i4ZZ03Yr_5] | |||
== BA algorithm in Python == | |||
* [http://networkx.lanl.gov/_modules/networkx/generators/random_graphs.html#barabasi_albert_graph Networkx source] | |||
== BA network + modularity == | |||
* [http://networkx.lanl.gov/_modules/networkx/generators/random_graphs.html#powerlaw_cluster_graph Networkx source] | |||
Latest revision as of 06:24, 18 June 2012
Problem statement
Complex networks have various properties which can be measured in real networks (WWW, social networks, biological networks), e.g. degree distribution, modularity, hierarchy, assortativity etc. Robustness of complex networks is a big question, however only some progress have been done in this direction. For example, it was shown that the scale-free networks are much more topologically robust to random attacks than random networks. Many people claim that various characteristics of complex networks will influence the robustness interdependently. The question I am interested in is how?
Approach
The idea is to generate continuous topology space of various complex networks (networks with different modularity, degree distribution, hierarchy etc) and use it to measure their robustness (see Fig. 1). There are many approaches to measure the robustness of complex networks. For example we can remove edges of vertices of a complex network graph and look at the size of a giant cluster. We can discuss other possibilities.
If you are interested you can contact me directly or via my E-mail: krystoferivanov@gmail.com or via my discussion page in CSSS 2012 wiki.
Relevant literature
- Important papers about network generation are highlighted in bold
- BA Scale-free network
- Statistical mechanics of complex networks
- Random Networks with Tunable Degree Distribution and Clustering
- Scale-free small world network with tunable assortative coefficient
- How to generate Scale-free modular network using preferential attachment
- Scale-free networks with tunable degree distribution exponents
- Scale free networks with tunable clustering
- Error and attack tollerance of complex networks
- Structural Robustness of Complex networks
- Assortative mixing in networks
- Mean field theory to study scale-free networks
- Kroneker Graphs
- Exact maximum-likelihood method to detect patterns in real networks
- Biological robustness
- Attack vulnerability of complex networks
- Supply Network Topology and Robustness against Disruptions – an investigation using multi agent model
- Random graphs with arbitrary degree distributions and their applications
- Resolution limit in community detection - about a typical modularity measure and its limitations
- Add a relevant paper...
Learning Python
Participants
- Oleksandr Ivanov - krystoferivanov@gmail.com
- Ian Wood - ibwood@indiana.edu
- Xin Lu - xin.lu@ki.se
- Duenas-Esterling Marco-Antonio - maduenase@gmail.com
- Katrien Beuls - katrien@ai.vub.ac.be
- Cameron Ray Smith - c...@gmail.com
- Abigail Horn - abbyhorn@mit.edu
- Nona Karalashvili - nona.karalashvili@gmail.com
Source Control
I've set up a github repository for any python source we write here. To figure out how to use Git look here. Chapters 1,2,3, and 5 are particularly relevant, but I can run through the basics with anyone. It's useful to have a source control for both project coordination and backup, and git is very simple once you get the hang of it.
There is a shared folder on skype, please either sign your email in the participant list or drop a email to Xin Lu to access the generated network data. Dropbox link [1]