[[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?

== 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 [[Oleksandr Ivanov|discussion page in CSSS 2012 wiki]].

== Relevant literature ==
* ''Important papers about network generation are highlighted in bold''
* '''[http://www.barabasilab.com/pubs/CCNR-ALB_Publications/199910-15_Science-Emergence/199910-15_Science-Emergence.pdf BA Scale-free network]'''
* '''[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://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://www.cis.upenn.edu/~mkearns/teaching/NetworkedLife/prefatt.pdf Mean field theory to study scale-free networks]
* [http://www.graphanalysis.org/SIAM-PP08/Leskovic.pdf Kroneker Graphs]
* [http://www.lem.sssup.it/WPLem/files/2011-07.pdf Exact maximum-likelihood method to detect patterns in real networks]
* [http://www-users.york.ac.uk/~lsdc1/SysBiol/kitano.robustness.naturegenetics.2004.pdf Biological robustness]
* [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://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...

== Learning Python ==
* [http://code.google.com/edu/languages/google-python-class/ Google's Python Class]

== Participants ==
# [[Oleksandr Ivanov]] - krystoferivanov@gmail.com
# [[Ian Wood]] - ibwood@indiana.edu
# [[Xin Lu]] - xin.lu@ki.se
# [[Duenas-Esterling Marco-Antonio]] - maduenase@gmail.com

== 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]
* ''Caution! when you copy this to the Python delete one space from the first line, i.e., before def''

def barabasi_albert_graph(n, m, seed=None):
"""Return random graph using Barabási-Albert preferential attachment model.
A graph of n nodes is grown by attaching new nodes each with m
edges that are preferentially attached to existing nodes with high
degree.

Parameters
----------
n : int
Number of nodes
m : int
Number of edges to attach from a new node to existing nodes
seed : int, optional
Seed for random number generator (default=None). 
Returns
-------
G : Graph

Notes
-----
The initialization is a graph with with m nodes and no edges. 
References
----------
.. [1] A. L. Barabási and R. Albert "Emergence of scaling in
random networks", Science 286, pp 509-512, 1999.
""" 
if m < 1 or m >=n:
raise nx.NetworkXError(\
"Barabási-Albert network must have m>=1 and m<n, m=%d,n=%d"%(m,n))
if seed is not None:
random.seed(seed) 
# Add m initial nodes (m0 in barabasi-speak)
G=empty_graph(m)
G.name="barabasi_albert_graph(%s,%s)"%(n,m)
# Target nodes for new edges
targets=list(range(m))
# List of existing nodes, with nodes repeated once for each adjacent edge
repeated_nodes=[]
# Start adding the other n-m nodes. The first node is m.
source=m
while source<n:
# Add edges to m nodes from the source.
G.add_edges_from(zip([source]*m,targets))
# Add one node to the list for each new edge just created.
repeated_nodes.extend(targets)
# And the new node "source" has m edges to add to the list.
repeated_nodes.extend([source]*m)
# Now choose m unique nodes from the existing nodes
# Pick uniformly from repeated_nodes (preferential attachement)
targets = _random_subset(repeated_nodes,m)
source += 1
return G

== BA network + modularity ==
* [http://networkx.lanl.gov/_modules/networkx/generators/random_graphs.html#powerlaw_cluster_graph Networkx source]
* ''Caution! when you copy this to the Python delete one space from the first line, i.e., before def''
def powerlaw_cluster_graph(n, m, p, seed=None):
"""Holme and Kim algorithm for growing graphs with powerlaw
degree distribution and approximate average clustering. 
Parameters
----------
n : int
the number of nodes
m : int
the number of random edges to add for each new node
p : float,
Probability of adding a triangle after adding a random edge
seed : int, optional
Seed for random number generator (default=None). 
Notes
-----
The average clustering has a hard time getting above
a certain cutoff that depends on m. This cutoff is often quite low.
Note that the transitivity (fraction of triangles to possible
triangles) seems to go down with network size. 
It is essentially the Barabási-Albert (B-A) growth model with an
extra step that each random edge is followed by a chance of
making an edge to one of its neighbors too (and thus a triangle). 
This algorithm improves on B-A in the sense that it enables a
higher average clustering to be attained if desired. 
It seems possible to have a disconnected graph with this algorithm
since the initial m nodes may not be all linked to a new node
on the first iteration like the B-A model. 
References
----------
.. [1] P. Holme and B. J. Kim,
"Growing scale-free networks with tunable clustering",
Phys. Rev. E, 65, 026107, 2002.
""" 
if m < 1 or n < m:
raise nx.NetworkXError(\
"NetworkXError must have m>1 and m<n, m=%d,n=%d"%(m,n)) 
if p > 1 or p < 0:
raise nx.NetworkXError(\
"NetworkXError p must be in [0,1], p=%f"%(p))
if seed is not None:
random.seed(seed) 
G=empty_graph(m) # add m initial nodes (m0 in barabasi-speak)
G.name="Powerlaw-Cluster Graph"
repeated_nodes=G.nodes() # list of existing nodes to sample from
# with nodes repeated once for each adjacent edge
source=m # next node is m
while source<n: # Now add the other n-1 nodes
possible_targets = _random_subset(repeated_nodes,m)
# do one preferential attachment for new node
target=possible_targets.pop()
G.add_edge(source,target)
repeated_nodes.append(target) # add one node to list for each new link
count=1
while count<m: # add m-1 more new links
if random.random()<p: # clustering step: add triangle
neighborhood=[nbr for nbr in G.neighbors(target) \
if not G.has_edge(source,nbr) \
and not nbr==source]
if neighborhood: # if there is a neighbor without a link
nbr=random.choice(neighborhood)
G.add_edge(source,nbr) # add triangle
repeated_nodes.append(nbr)
count=count+1
continue # go to top of while loop
# else do preferential attachment step if above fails
target=possible_targets.pop()
G.add_edge(source,target)
repeated_nodes.append(target)
count=count+1 
repeated_nodes.extend([source]*m) # add source node to list m times
source += 1
return G

2012-05-31T13:26:10Z

Xinl:

Xin is a PhD student at the Department of Public Health Sciences, Karolinska Institutet, He works most of the time at the Department of Sociology, Stockholm University.
He is working on evaluating and improving Respondent-driven sampling method (RDS), a '''network-based sampling''' strategy for HIV-related high-risk population surveys. He also works on '''cell phone-data''' based population tracking during earthquakes, network-based epidemic modeling of sexual transmitted diseases (STI), and designing of outbreak detection models for '''Symdromic Surveillance Systems''' in rural China.

He is looking forward to collaboration oppotunities from CSSS12. Examples of his recent works:

"Predictability of population displacement after the 2010 Haiti earthquake". '''''PNAS''''', 2012, in press.

"The sensitivity of respondent-driven sampling". '''''Journal of the Royal Statistical Society: Series A (Statistics in Society)''''', 2012, 175: 191–216.

"Improved Response to Disasters and Outbreaks by Tracking Population Movements with Mobile Phone Network Data: A Post-Earthquake Geospatial Study in Haiti". '''''PLoS Medicine''''', 2011; 8 (8): e1001083.

"Finding the Shortest Paths by Node Combination". '''''Applied Mathematics and Computation''''', 2011, 217 (13) pp. 6401-6408.

Have a look at his Blog: http://xin-lu.blogspot.se/

or his work on mobile phone data analysis: http://www.flowminder.org/

or his work on Symdromic Surveillance Systems: http://www.issc-eu.com/

or his short official page at Karolinska Institutet: http://ki.se/ki/jsp/polopoly.jsp?d=37885&a=119016&l=en

Looking forward to see all of you at CSSS12!

Xin Lu

2012-05-31T13:23:23Z

Xinl: Created page with 'Xin is a PhD student at the Department of Public Health Sciences, Karolinska Institutet, He works most of the time at the Department of Sociology, Stockholm University. He is wor…'