Structural Analysis and Visualization of Networks

Home Assignment #2: Network models

Student: *{Your Name}*


General Information

Due Date: 18.02.2015 23:59 <br > Late submission policy: -0.2 points per day <br >

Please send your reports to mailto:[email protected] and mailto:[email protected] with message subject of the following structure:<br > [HSE Networks 2015] {LastName} {First Name} HA{Number}

Support your computations with figures and comments. <br > If you are using IPython Notebook you may use this file as a starting point of your report.<br > <br >

<hr >

Problems

Task 1

Consider Barabasi and Albert dynamical grow model. Two main ingredients of this model are network growing and prefferential attachment. Implement two restricted B&A-based models: <br >

Model A <br > Lack of prefferential attachment, that is at each time-step form edges uniformly at random while network keeps growing.

Model B <br > Lack of growing, that is fix total number of nodes, on each time-step randomly choose one and form edges with prefferential attachment. <br >

  1. Generate networks according to the models above ($N > 1000$ nodes)
  2. Compute CDF/PDF, describe the distribution and compute\describe its properties.
  3. Illustate the following dependencies:
    • average path length to the number of nodes
    • average clustering coefficient to the number of nodes
    • average node degee to the nodes "age"
  4. Is scale-free property conserved in these models?

Analyse results with respect to various parameter settings


Task 2

Consider the following "Vertex copying model" of growing network.

At every time step a random vertex from already existing vertices is selected and duplicated together with all edges, such that every edge of the vertex

  • is copied with probability $q$
  • is rewired to any other randomly selected vertex with probability $1-q$

Starting state is defined by some small number of randomly connected vertices.

The model can generate both directed and undirected networks.

  1. Generate graphs based on the model ($N > 1000$ nodes)
  2. Compute CDF/PDF, describe the distribution and compute\describe its properties.
  3. Illustate the following dependencies:
    • average path length to the number of nodes
    • average clustering coefficient to the number of nodes
    • average node degee to the nodes "age"

Analyse results with respect to various parameter settings