Robustness of complex networks (project): Difference between revisions

Latest revision as of 06:24, 18 June 2012

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 discussion page in CSSS 2012 wiki.

Relevant literature

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]

BA algorithm in Python

Networkx source

BA network + modularity

Networkx source

@@ Line 11: / Line 11: @@
 * ''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://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]'''
@@ Line 31: / Line 34: @@
 == Learning Python ==
 * [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 ==
@@ Line 37: / Line 43: @@
 # [[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==&amp;c=4iKaQQLKYQ-uUaepLzz3_1LdZfwZMM24y5sG4GTjP-4= c...@gmail.com]
+# [[Abigail Horn]] - abbyhorn@mit.edu
+# Nona Karalashvili - nona.karalashvili@gmail.com
+</span>
 == Source Control ==
@@ Line 49: / Line 60: @@
 == 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.<br />
-    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).<br />
-    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. <br />
-    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).<br />
-    This algorithm improves on B-A in the sense that it enables a
-    higher average clustering to be attained if desired. <br />
-    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.<br />
-    References
-    ----------
-    .. [1] P. Holme and B. J. Kim,
-       "Growing scale-free networks with tunable clustering",
-       Phys. Rev. E, 65, 026107, 2002.
-    """<br />
-    if m < 1 or n < m:
-        raise nx.NetworkXError(\
-              "NetworkXError must have m>1 and m<n, m=%d,n=%d"%(m,n))<br />
-    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)    <br />
-    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<br />
-        repeated_nodes.extend([source]*m)  # add source node to list m times
-        source += 1
-    return G