All students are required to do the following home/projects.
Select one project to present
in the class. Write a report on all other home/projects.
Students may team up (maximum 2 students per team)
to work collaboratively on these projects.
- 1. Network Centrality
-
Using the networks provides on Blackboard,
(A) Compute Degree Centraltiy, eigenvector centrality, Betweenness Centrality and closeness centrality for all nodes on at least two networks.
(B)
Plot the results (ranking). The x-axis is the node id and y-axis are the
score.
Plot 4 figures, each figure, the node ordering is different.
1st: sort nodes according to degree.
2st: sort nodes according to eigenvector centrality.
3rd: sort nodes according to betweenness centrality.
4th: sort nodes according to closeness centrality.
- 2. Random walk on chains and graphs.
-
(A) Generate 2000 random walks on infitie chains and finite chain [-20, 20].
Each random walker walks 1000 steps.
(A1) Plot 3 random walks on infinite chain. Plot 3 random walks on finite chain.(A2) Compute the averages of these random walks. Show the frequencies on
each sites in both infinite and finite chains.
(B) Generate 2000 random walks on a network provided on blackboards.
(B1) Plot 3 random paths.
(B2) Average these 2000 random walks to obtain stationary distribution of the
random walker.
(B3) Compute the stationary distribuition from theory. Compare with the
computer simulation results.
Note: this is Google's PageRank.
- 3. Erdos-Renyi random graph.
-
(A) Generate ER random graphs with n=100,200,500 and p=0.8/n, 1/n, 1.2/n
(B) For each parameter set, generate m=100,400,1600 random graph instances.
Compute all connected components (CC) of a random graph.
Compute the average of the size of the largest CC.
Is there a giant component for p=0.8/n, p=1/n?
(C)
Write a code and compute the number of distinct 2-chains of a graph.
Compute this for all random graph instance to get average.
Compare to theoretical expectation.
As n,m increase,
the measured value should match theoretical value.
(D)
Write a code and compute the number of distinct triangles of a graph.
Compute this for all random graph instance to get average.
Compare to theoretical expectation.
As n,m increase,
the measured value should match theoretical value.
- 4. Generate Fixed Degreee Sequence Random Graphs,
-
(A) Generate the first graph.
Sort degrees in decreasing order. Start with the node
with largest degree. Always find "next" available nodes to
attach edges to.
(B)
Rewrie.
Started with the generate graph in (a).
Randomly pick two edges (not connected).
Rewire them in one of the two possible ways.
(C)
Optional. Pick 3 edges and randomly rewire them in of the
eight different ways.
(D)
Input a degree sequence. Generate the initial graph.
Run rewiring algorithm on them many times.
Watch for the disconnected components disappear.
(E)
Write a code and compute the number of distinct 2-chains of a graph.
Compute this for all random graph instance to get average.
Compare to theoretical expectation.
(F)
Write a code and compute the number of distinct triangles of a graph.
Compute this for all random graph instance to get average.
Compare to theoretical expectation.
(G) Input longer degree sequence, n=100. Do more edge rewiring. Repeat
(E) and (F) to see
the measured value should match theoretical value.
- 5. Small World Networks
-
(a)
Input (n,d, p) and generate 1D small world networks.
Here n=number of nodes.
d=degree of each node.
p=percentage of random edges to be added.
(b)
On the 1D small world network,
compute the network diameter and average diameter.
Show that adding random edges reduces the network diameters.
(c)
Input (n,p) and generate 2D small world networks.
Here n=number of nodes.
p=percentage of random edges to be added.
[We suggest you to use n=10-20]
(d)
On the 2D small world network,
compute the network diameter and average diameter.
Show that adding random edges reduces the network diameters.
(e)
On the 2D small world network,
pick one node near lower left corner as the starting node.
pick one node near upper right corner as the destination node.
Compute the optimal path suppose you know all the
edge information. Run Floyd-Warshall (or Dijistra) algorithm.
Print out this number.
(f)
On the 2D small world network,
Compute the realistic optimal path suppose you know
only local information (each node contains
the 4 edges to its neighbors and the random edges if they exist).
Your algorithm does a greedy search to pick one edge such that
the other end of the choosen edge is closest to the destination
node).
Print out this number.
(g)
Repeat steps (c,d,e,f) to observe the
difference between the (unrealistic) global optimal path
and the realistic local-information based path.