import networkx as nx
import networkx.convert_matrix as nxm
import pandas as pd
dati = pd.read_csv (r'from_to.csv')
print (dati)
info = pd.read_csv (r'info.csv')
print (info)
df = dati.pivot_table(index=['From','To'], values=['To'], aggfunc=['count'])
print (df)
Creare Network¶
G = nx.DiGraph()
#aggiungere nodi
for i in range(len(info['Node'])):
G.add_node(info['Node'][i])
#aggiungere edge
for i in range(len(df.index)):
G.add_edge(df.index[i][0], df.index[i][1],weight=df.ix[df.index[i]][0])
# aggiungere attributi
nx.set_node_attributes(G, info['Age'], 'Age')
nx.set_node_attributes(G, info['Department'], 'Department')
nx.set_node_attributes(G, info['Job'], 'Job')
print(G)
Calcolo Misure¶
density = nx.density(G)
print("Network density:", density)
A_B_path = nx.shortest_path(G, source="A", target="B")
print("Shortest path between A and B:", A_B_path)
print("Length of that path:", len(A_B_path)-1)
triadic_closure = nx.transitivity(G)
print("Triadic closure:", triadic_closure)
Degree¶
The simplest measure of centrality in a social network is the degree. It is the simplest and most common way to find important nodes. The degree of a node is the sum of its edges. If, for example, a node has three lines extending from it to other nodes, its degree is three.
There are two types of degree centrality: indegree and outdegree.
- Indegree is the count of the total number of incoming connections to a node. In the language of friendship, indegree can be thought of as "popularity" centrality. The node is popular because many other nodes nominate it as a node with which they have a certain type of relationship.
- Outdegree is the total number of outgoing connections from a node. The outdegree can be considered as the level of gregariousness of a node. Nodes with higher levels have many outgoing connections. In directed graphs one can distinguish indegree and outdegree, but in an undirected graph (without arrows) we can simply measure degree centrality.
degree_centrality(G) Compute the degree centrality for nodes.
in_degree_centrality(G) Compute the in-degree centrality for nodes.
out_degree_centrality(G) Compute the out-degree centrality for nodes.
degree_dict = dict(G.degree(G.nodes()))
print(degree_dict)
nx.set_node_attributes(G, degree_dict, 'degree')
Closeness¶
The second measure we will discuss is called Closeness. There are also other names for it; sometimes it is called access centrality. In short, Closeness centrality captures the average distance from the focal node to all other nodes in the social network. The mathematical representation of closeness is the following:
\[l_i = \frac{1}{n-1} \sum_j d_{i,j}\]We are trying to compute the closeness of the node to all other nodes in the network; hence Closeness. The numerator is the sum of all pairwise distances between node i and all other nodes j (excluding i). The sum of distances is then divided by the total number of nodes in the network \(n\) minus 1 (to adjust the count to exclude node i). Now we have farness, which is the average distance of node i from all other nodes in the network. Taking the reciprocal gives us closeness.
\[C_i = \frac{1}{l_i} = \frac{n-1}{\sum_j d_{i,j}}\]closeness_dict = nx.closeness_centrality(G)
print(closeness_dict)
nx.set_node_attributes(G, closeness_dict, 'closeness')
Betweenness¶
It is perhaps one of the most powerful measures of centrality and is closely related to the idea of structural holes. Betweenness can be calculated as:
\[b_i = \sum_{s, t} w_{s,t}^{i} = \sum_{s, t} \frac{n_{s,t}^{i}}{n_{s,t}}\]Betweenness is the measure by which one understands whether a node acts as a bridge between other nodes in the network. It is calculated by looking at all pairs of nodes in the network and examining the frequency with which i, the focal node, lies on the shortest paths between nodes j and k.
In simpler terms, it is the extent to which a node lies on paths between other nodes. Nodes with a high level of betweenness can have considerable influence within a network by virtue of their control over the information that passes between others. They are also those whose removal from the network will most disrupt communications between other nodes because they lie on the greatest number of paths followed by messages.
betweenness_dict = nx.betweenness_centrality(G)
print(betweenness_dict)
nx.set_node_attributes(G, betweenness_dict, 'betweenness')
Eigenvector¶
A natural extension of degree centrality is eigenvector centrality. Degree centrality gives a centrality point for every link received by a node. But not all vertices are equivalent: some are more relevant than others and, reasonably, endorsements from important nodes count more. The thesis of eigenvector centrality states: A node is important if it is connected to other important nodes. Eigenvector centrality differs from degree centrality: a node that receives many links does not necessarily have high eigenvector centrality (it is possible that all linkers have low or zero eigenvector centrality). Moreover, a node with high eigenvector centrality is not necessarily highly connected (the node may have few but important linkers).
Let \(A = (a_ {i, j})\) be the adjacency matrix of a graph. The eigenvector centrality \(x_ {i}\) of node \(the\) is given by: \[x_i = \frac {1} {\lambda} \sum_k a_ {k, i} \, x_k\] where \(\lambda \neq 0\) is a constant. In matrix form we have: \[\lambda x = x A\]
Thus the centrality vector \(x\) is the left eigenvector of the adjacency matrix \(A\) associated with the eigenvalue \(\lambda\). It is wise to choose \(\lambda\) as the largest eigenvalue in absolute value of the matrix \(A\). By virtue of the Perron-Frobenius theorem, this choice guarantees the following desirable property: if the matrix \(A\) is irreducible, or equivalently if the graph is (strongly) connected, then the eigenvector solution \(x\) is both unique and positive. Let \(m (v)\) denote the signed component of maximum magnitude of vector \(v\). If there is more than one maximum component, let \(m (v)\) be the first one. For example, \(m (-3,3,2) = -3\). Let \(x ^ {(0)}\) be an arbitrary vector. For \(k \geq 1\): repeatedly compute \(x ^ {(k)} = x ^ {(k-1)} A\); normalize \(x ^ {(k)} = x ^ {(k)} / m (x ^ {(k)})\); until reaching the desired precision. It follows that \(x ^ {(k)}\) converges to the dominant eigenvector of \(A\) and \(m (x ^ {(k)})\) converges to the dominant eigenvalue of \(A\). If the matrix \(A\) is sparse, each vector-matrix product can be performed in linear time in the size of the graph.
The method converges when the dominant eigenvalues (the largest) and the sub-dominant ones (the second largest) of \(A\), respectively denoted by \(\lambda_1\) and \(\lambda_2\), are separated, i.e. differ in absolute value, thus when \(| \lambda_1 | > | \lambda_2 |\). The rate of convergence is the rate at which \((\lambda_2 / \lambda_1) ^ k\) goes to \(0\). Quindi, if l'autovalue secondario sub-dominante is piccolo with respect a that dominante, the method converge rapidamente.
eigenvector_dict = nx.eigenvector_centrality(G)
print(eigenvector_dict)
nx.set_node_attributes(G, eigenvector_dict, 'eigenvector')
Rappresentazione¶
edges = G.edges()
weights = [G[u][v]['weight'] for u,v in edges]
options = {
'node_size': 600,
'width': 1,
'arrowstyle': '-|>',
'arrowsize': 12,
}
nx.draw(G, widht=weights, arrows=True, node_shape='D',
with_labels=True,
edge_color='green',
node_color=range(len(G)), **options)
Python in Practice
Below we demonstrate network analysis concepts using NetworkX on Zachary's Karate Club graph.
1. Building and Exploring a Network
import networkx as nx
import numpy as np
G = nx.karate_club_graph()
print(f"Nodes: {G.number_of_nodes()}")
print(f"Edges: {G.number_of_edges()}")
print(f"Density: {nx.density(G):.4f}")
print(f"Average clustering coefficient: {nx.average_clustering(G):.4f}")
print(f"Diameter: {nx.diameter(G)}")
# Output:
# Nodes: 34
# Edges: 78
# Density: 0.1390
# Average clustering coefficient: 0.5706
# Diameter: 5
2. Centrality Measures
degree_c = nx.degree_centrality(G)
betweenness_c = nx.betweenness_centrality(G)
closeness_c = nx.closeness_centrality(G)
print("Top 5 nodes by centrality measure:")
print("\nDegree:")
for n in sorted(degree_c, key=degree_c.get, reverse=True)[:5]:
print(f" Node {n}: {degree_c[n]:.3f}")
print("\nBetweenness:")
for n in sorted(betweenness_c, key=betweenness_c.get, reverse=True)[:5]:
print(f" Node {n}: {betweenness_c[n]:.3f}")
# Output:
# Top 5 nodes by centrality measure:
#
# Degree:
# Node 33: 0.515
# Node 0: 0.485
# Node 32: 0.364
# Node 2: 0.303
# Node 1: 0.273
#
# Betweenness:
# Node 0: 0.437
# Node 33: 0.304
# Node 32: 0.145
# Node 2: 0.143
# Node 31: 0.138
3. Community Detection
from networkx.algorithms.community import greedy_modularity_communities
communities = list(greedy_modularity_communities(G))
print(f"Number of communities detected: {len(communities)}")
for i, comm in enumerate(communities):
print(f" Community {i+1} ({len(comm)} nodes): {sorted(list(comm))[:8]}...")
modularity = nx.community.modularity(G, communities)
print(f"\nModularity: {modularity:.4f}")
# Output:
# Number of communities detected: 3
# Community 1 (18 nodes): [0, 1, 2, 3, 7, 9, 11, 12]...
# Community 2 (11 nodes): [23, 24, 25, 27, 28, 29, 30, 31]...
# Community 3 (5 nodes): [4, 5, 6, 10, 16]...
#
# Modularity: 0.3806
Results
