[NetworkX] Assignment 2 - Network Connectivity

본 게시물은 Coursera의 Applied Social Network Analysis in Python(by Daniel Romero)를 통해 자습하며 작성한 게시물입니다.

이 Assignment는 Coursera Jupyter 콘솔에서만 제대로 진행할 수 있습니다.

(데이터 파일을 따로 제공하지 않기 때문입니다.)

 

 

개괄 원본

In this assignment you will go through the process of importing and analyzing an internal email communication network between employees of a mid-sized manufacturing company. Each node represents an employee and each directed edge between two nodes represents an individual email. The left node represents the sender and the right node represents the recipient.

개괄 해석 (많은 의역, 생략 및 요약)

사내 이메일 통신 네트워크 분석합니다.

• head email_network.txt
  • Sender: 메일 보낸사람
  • Recipient: 받은사람

 

 

Question 1

Using networkx, load up the directed multigraph from email_network.txt. Make sure the node names are strings.
This function should return a directed multigraph networkx graph.

• email_network.txt를 읽어서 networkx 그래프를 return하는 함수를 만들어라
• 모든 노드의 이름 type은 string으로 해라

• 힌트: nx.read_edgelist()

해결방법

def answer_one():
    
    G = nx.read_edgelist('email_network.txt', nodetype=str, create_using=nx.MultiDiGraph(), data=[('time', int)])
    
    return G
    
# 결과 확인
G = answer_one()
nx.draw_networkx(G)

---

 

Question 2

How many employees and emails are represented in the graph from Question 1?
This function should return a tuple (#employees, #emails).

• Question1로 만든 그래프에서 사람수, 이메일 수를 알아내는 함수를 만들어라
• (사람수, 이메일수) 형태의 튜플을 return해라

• 힌트: G.number_of_nodes(), G.number_of_edges()

해결방법

def answer_two():
        
    G = answer_one()
    n_employees = G.number_of_nodes()
    n_emails = G.number_of_edges()
    
    return (n_employees, n_emails)
    
# 결과확인
answer_two()  # (167, 82927)

 

---

 

Question 3

Part 1. Assume that information in this company can only be exchanged through email.
When an employee sends an email to another employee, a communication channel has been created, allowing the sender to provide information to the receiver, but not vice versa.
Based on the emails sent in the data, is it possible for information to go from every employee to every other employee?

Part 2. Now assume that a communication channel established by an email allows information to be exchanged both ways.
Based on the emails sent in the data, is it possible for information to go from every employee to every other employee?

This function should return a tuple of bools (part1, part2).

• 이 회사에서는 오로지 이메일로만 소통할 수 있다.
•  
• Part1 : 사람A가 사람B한테 메일을 보내면 A→B 소통창구가 생기지만 그 반대(B→A)로는 못간다.
• 이때, 모든 사람이 다른 모든사람한테 연락을 보낼 수 있는가?
•  
• Part2 : 이번에는 반대로도 갈 수 있다.(B→A)
• 이때, 모든 사람이 다른 모든사람한테 연락을 보낼 수 있는가?
•  
• (part1정답, part2정답) 형태의 튜플을 return해라
• 각 정답은 bools(True or False)다.

• 힌트: nx.is_strongly_connected(), nx.is_weakly_connected()

해결방법

def answer_three():
    
    G = answer_one()
    p1 = nx.is_strongly_connected(G)
    p2 = nx.is_weakly_connected(G)
    
    return (p1,p2)
    
# 결과확인
answer_three()  # (False, True)

---

 

Question 4

How many nodes are in the largest (in terms of nodes) weakly connected component?
This function should return an int.

• 약연결 연결성분 중 가장 많은 노드를 가지고 있는 연결성분은? 그 연결성분의 노드 개수는?
• 노드개수만 return하는 함수 만들어라

• 힌트: max(   ,key=len)

해결방법

def answer_four():
    
    G = answer_one()
    max_component = max(nx.weakly_connected_components(G), key=len)
    N = len(max_component)
    
    return N
    
# 결과확인
answer_four()  # 167

---

 

Question 5

How many nodes are in the largest (in terms of nodes) strongly connected component?
This function should return an int

• 강연결 연결성분 중 가장 많은 노드를 가지고 있는 연결성분은? 그 연결성분의 노드 개수는?
• 노드개수만 return하는 함수 만들어라

• 힌트: max(   ,key=len)

해결방법

def answer_five():
        
    G = answer_one()
    max_component = max(nx.strongly_connected_components(G), key=len)
    N = len(max_component)
    
    return N

# 결과확인
answer_five()  # 126

---

 

Question 6

Using the NetworkX function strongly_connected_component_subgraphs, find the subgraph of nodes in a largest strongly connected component. Call this graph G_sc.
This function should return a networkx MultiDiGraph named G_sc.

• 가장 큰 강연결 연결성분 G_sc 그래프를 return해라
• strongly_connected_component_subgraphs()를 사용해라

• 힌트: max(   ,key=len)

해결방법

def answer_six():
        
    G = answer_one()
    G_sc = max(nx.strongly_connected_component_subgraphs(G), key=len)
    
    return G_sc
    
# 결과확인
G_sc = answer_six()
nx.draw_networkx(G_sc)

---

 

Question 7

What is the average distance between nodes in G_sc?
This function should return a float.

• G_sc의 평균거리는?

• 힌트: nx.average_shortest_path_length()

해결방법

def answer_seven():
        
    G_sc = answer_six()
    d = nx.average_shortest_path_length(G_sc)
    
    return d
    
# 결과확인
answer_seven()  # 1.6461587301587302

---

 

Question 8

What is the largest possible distance between two employees in G_sc?
This function should return an int.

• G_sc에서 두 사람 간 가능한가장 긴 거리는?

• 힌트: nx.diameter()

해결방법

def answer_eight():
        
    G_sc = answer_six()
    d = nx.diameter(G_sc)
    
    return d

# 결과확인
answer_eight()  # 3

---

 

Question 9

What is the set of nodes in G_sc with eccentricity equal to the diameter?
This function should return a set of the node(s)..

• 이심률이 지름과 같은 노드의 집합은?

• 힌트: nx.periphery()

(이심률이라는 단어가 아직 낯설다면 아래의 글을 참고해주세요!)

[NetworkX] 그래프를 거리(length)로 설명하는 방법(평균거리, 지름, 반지름, 둘레, 이심률)

해결방법

def answer_nine():
       
    G_sc = answer_six()
    nodes = nx.periphery(G_sc)
    
    return set(nodes)
    
# 결과확인
answer_nine()  # {'129', '134', '97'}

---

 

Question 10

What is the set of node(s) in G_sc with eccentricity equal to the radius?
This function should return a set of the node(s).

• 이심률이 반지름과 같은 노드의 집합은?

• 힌트: nx.center()

해결방법

def answer_ten():
       
    G_sc = answer_six()
    nodes = nx.center(G_sc)
    
    return set(nodes)
    
# 결과확인
answer_ten()  # {'38'}

---

 

Question 11

Which node in G_sc is connected to the most other nodes by a shortest path of length equal to the diameter of G_sc?
How many nodes are connected to this node?
This function should return a tuple (name of node, number of satisfied connected nodes).

• G_sc에서 어떤 노드가 다음의 조건을 만족하는가?
• "다른 노드들과 연결할때의 가장 짧은 길이가 지름과 똑같은 경우"가 가장 많은 노드는?
• (노드이름, 조건을 만족하는 노드의 수)를 return해라

• 힌트:지름과 같은 길이의 연결을 가지려면 가장 가장자리(periphery)에 위치한 노드겠죠?

해결방법

def answer_eleven():
        
    G_sc = answer_six()
    d = nx.diameter(G_sc)
    peripheries = nx.periphery(G_sc)

    dic = {}

    for node in peripheries:
        length_to_all = nx.shortest_path_length(G_sc, node).values()
        equal_count = list(length_to_all).count(d)
        dic[node] = equal_count

    max_key = max(dic, key=dic.get)
    max_value = max(dic.values())
    
    return (max_key, max_value)
    
# 결과확인
answer_eleven()  # ('97', 63)

---

 

Question 12

Suppose you want to prevent communication from flowing to the node that you found in the previous question from any node in the center of G_sc, what is the smallest number of nodes you would need to remove from the graph (you're not allowed to remove the node from the previous question or the center nodes)?
This function should return an integer.

• Question11에서 찾은 노드랑 G_sc의 중앙(center) 노드 중 아무 노드랑 소통하는걸 방해하려 한다.
• 이때 제거해야하는 노드의 최소 개수는?

• 힌트:nx.minimum_node_cut()

해결방법

def answer_twelve():
        
    G_sc = answer_six()
    center = nx.center(G_sc)[0]
    node = answer_eleven()[0]
    prevent_N = len(nx.minimum_node_cut(G_sc, center, node))
    
    return prevent_N
    
# 결과확인
answer_twelve()  # 5

---

 

Question 13

Construct an undirected graph G_un using G_sc (you can ignore the attributes).
This function should return a networkx Graph.

• G_sc에서 방향성을 무시한 그래프 G_un을 return해라

• 힌트: G.to_undirected()

해결방법

def answer_thirteen():
        
    G_sc = answer_six()
    undir_subgraph = G_sc.to_undirected()
    G_un = nx.Graph(undir_subgraph)
    
    return G_un

---

 

Question 14

What is the transitivity and average clustering coefficient of graph G_un?
This function should return a tuple (transitivity, avg clustering).

• G_un의 전이성(transitivity)와 평균집단화계수(avg clustering)

• 힌트: G.to_undirected()

해결방법

def answer_fourteen():
        
    G_un = answer_thirteen()
    transitivity = nx.transitivity(G_un)
    avg_clustering = nx.average_clustering(G_un)
    
    return (transitivity, avg_clustering)
    
# 결과확인
answer_fourteen() # (0.570111160700385, 0.6975272437231419)