[Chapter2]
1. Network Characteristics
One of the goals of network analysis is to find mathematical models that characterize real-world networks and that can then be used to generate new networks with similar properties. In this problem, we will explore two famous models—Erdos-Renyi and Small World—and compare them to real-world data from an academic collaboration network. Note that in this problem all networks are undirected. You may use the starter code in hw1-q1-starter.py for this problem.
Erd ̋os-R ́enyi Random graph (G(n, m) random network): Generate a random instance of this model by using n = 5242 nodes and picking m = 14484 edges at random. Write code to construct instances of this model, i.e., do not call a SNAP function.
Small-World Random Network: Generate an instance from this model as follows: begin with n = 5242 nodes arranged as a ring, i.e., imagine the nodes form a circle and each node is connected to its two direct neighbors (e.g., node 399 is connected to nodes 398 and 400), giving us 5242 edges. Next, connect each node to the neighbors of its neighbors (e.g., node 399 is also connected to nodes 397 and 401). This gives us another 5242 edges. Finally, randomly select 4000 pairs of nodes not yet connected and add an edge between them. In total, this will make m = 5242 · 2 + 4000 = 14484 edges. Write code to construct instances of this model, i.e., do not call a SNAP function.
Real-World Collaboration Network: Download this undirected network from http://snap. stanford.edu/data/ca-GrQc.txt.gz. Nodes in this network represent authors of research papers on the arXiv in the General Relativity and Quantum Cosmology section. There is an edge between two authors if they have co-authored at least one paper together. Note that some edges may appear twice in the data, once for each direction. Ignoring repeats and self-edges, there are 5242 nodes and 14484 edges. (Note: Repeats are automatically ignored when loading an (un)directed graph with SNAP’s LoadEdgeList function).
1.1 Degree Distribution [12 points]
Generate a random graph from both the Erd ̋os-R ́enyi (i.e., G(n, m)) and Small-World models and read in the collaboration network. Delete all of the self-edges in the collaboration network (there should be 14,484 total edges remaining).
Plot the degree distribution of all three networks in the same plot on a log-log scale. In other words, generate a plot with the horizontal axis representing node degrees and the vertical axis representing the proportion of nodes with a given degree (by “log-log scale” we mean that both the horizontal and vertical axis must be in logarithmic scale). In one to two sentences, describe one key difference between the degree distribution of the collaboration network and the degree distributions of the random graph models.
Collaboration Network는 대략적으로 멱급수 분포를 따르며, 차수가 가장 작은 노드들이 가장 많다. 반면에 다른 가장 적은 차수와 가장 많은 차수 사이에 높이 솟은 모양이다. 또한 Collaboration Network는 더 긴 꼬리를 가지고 있다.
1.2 Clustering Coefficient
2. Structural Roles : Rolx and ReFex
2.1, 2.2 Basic Feature and Recursive Features
Recursive Feature Extraction 은 먼저 노드 고유의 Local Feature 를 구한다음에 자기 자신을 포함한 인접한 노드의 셋 (Egonet) 을 점진적으로 더하거나 평균을 구하면서 지수적으로 증가하는 특징을 이야기 한다. 9번쨰의 정점을 중심으로 코싸인 유사도를 비교해본 결과 Local Feature 기반으로 계산한 유사도와 Recursive Feature 을 기반으로 계산한 유사도가 다름을 확인하였다.
인접한 노드의 새로운 특징을 더한여 만들어서 유사도가 다름을 확인하였다.
2.3 Role Discovery
아래 그래프는 9번째 노드를 중심으로 얼마나 유사한지에 따라 노드가 분배되어 있다. 스파이크가 0.9에서 한번 0.65에서 한번 있어서 정점 9번과 0.9만큼의 유사도가 있는 그룹 하나와 0.65만큼의 유사도가 있는 그룹 하나로 총 2가지로 구분할 수 있다.
두 그룹 하나는 A(정점 9와 코싸인 유사도가 0.65보다 크고 0.7보다 작음), 다른하나는 B(코사인 유사도가 0.9보다 크고 0.95보다 작음) 에서 노드 하나씩을 임의로 뽑은 결과 A 집합에서는 1321 (0.667714) 그리고, B 집합에서는 1023 (0.932808) 이다.
Node 1321 | Node 1023 | |
Local Feature | (1,1,1) | (4,10,13) |
K = 1 | (1,1,1,1,1,1,1,1,1) | (4,10,13,6.25,16, 18.5, 25, 64, 74 ) |
K=2
Structural Roles : 정점 9번과 높은 유사도를 노드일수록 더 많은 노드와 연결된다는 것을 알았다. 노드 9번의 Sub Graph를 비교하였을 때 1023 노드 만큼의 간선을 가지고 있음을 확인할 수 있었다.
그런데 Structural Role 이 어떻게 다른지 이야기 할수 있을까?
3. Community Detection using Louvain algorithm
Modularity 란 노드가 커뮤니티에 잘 배정이 되어 있는지 측정할 수 있는 지표이다. Louvain Algorithm은 이 modularity score을 높이는 방향으로 학습시킨다. Modularity를 기반으로한 modularity gain 공식을 사용해서 각각의 노드와 modularity gain을 비교한 다음에 가장 높은 modularity gain 이 나온 노드와 하나의 커뮤니티를 만드는 방식을 반복해나간다. 이 부분은 modularity optimization step 이다. 첫번째 phase가 끝나면 두번째 phase로 가는데 두번째는 community aggregation 이다. 하나의 커뮤니티를 합쳐서 하나의 노드를 만들고 다시 첫번째 phase로 돌아가서 이를 반복한다.
다음 과정은 아래 그래프에 대한 Modularity Optimization 과정이다.
처음 단계에서는 모든 노드는 각각 독립적이라고 가정한다. 따라서 노드의 갯수만큼 커뮤니티의 갯수가 있는 것이다.
위 결과 4개의 정점으로 수렴함을 알 수 있었다. 그 이상으로 군집화 시킬수는 없었다. Modularity Gain이 음수값이 나왔다.
Louvain Algorithm 을 끝낸 후 Modularity 를 측정한 결과 0.4375 가 나왔다. 반면 이 단계에서 인위적으로 클러스터링을 해 버릴경우,
Modularity 가 0.366으로 떨어짐을 알 수 있었다.
위 경우에서는 꽤나 직관적으로 군집화가 이루어졌다. 하지만 노드가 더 많아질경우, 클러스터링 결과는 직관적이지 않다. 위의 그래프를 128개의 노드로 확대해본 결과 군집 결과는 아래와 같다.
군집 결과는 더욱 큰 그래프에서는 직관적이 아닐 수 있다는것을 알아두자!
Last updated
