Complex Systems · 6/8 · Series index · Notation

Graph representations and connectivity are developed in Network fundamentals.

Metric definitions and normalization conventions are in Network metrics and algorithms.

Working with NetworkX and Reading Code

The examples use NetworkX 3.x interfaces for constructing graphs, inspecting attributes, computing metrics, and interpreting results.

Dictionaries, Graph Types, and Adding Nodes and Edges

A Python dictionary stores key:value pairs. For example, tel['jack'] retrieves a value and tel['john']=4127 adds or updates an entry. list(tel) or tel.keys() gives the keys, tel.values() gives the values, len(tel) counts entries, and sorted(tel) returns sorted keys. NetworkX uses dictionary-like structures for adjacency and attributes.

nx.Graph() represents an undirected graph and nx.DiGraph() a directed graph. Both allow self-loops but prohibit parallel edges: repeatedly adding the same edge does not create additional edges. The examples here do not add self-loops and are therefore discussed as simple graphs. Use MultiGraph or MultiDiGraph when parallel edges are required. Node identifiers must be hashable, such as integers, strings, or tuples.

1
2
3
4
5
6
7
8
9
10
import networkx as nx
G = nx.Graph()
G.add_node(1)
G.add_nodes_from([2, 3])
G.add_nodes_from([(4, {"color": "red"})])
G.add_edge(1, 2)  # creates missing endpoints automatically
e = (2, 3)
G.add_edge(*e)    # unpack tuple into two arguments
G.add_edges_from([(1, 3), (3, 4)])
G.add_weighted_edges_from([(1, 4, 0.5)])

String trap: add_node("spam") adds one node named "spam"; add_nodes_from("spam") iterates over the string and adds the four nodes 's','p','a','m'. An edge list should contain pairs, or triples that also supply attributes.

Construct a graph directly with nx.Graph([(0,1),(1,2)]), or pass an adjacency dictionary to the constructor. nx.DiGraph(G) replaces each undirected edge by two opposing directed edges. DG.to_undirected() or nx.Graph(DG) ignores direction to form an undirected graph. Such conversions change the problem's meaning; explain why ignoring direction is appropriate when interpreting the result.

Inspection, Attributes, and Deletion

Expression Meaning
G.number_of_nodes() / G.number_of_edges() Numbers of nodes and edges
list(G.nodes), list(G.edges) Node and edge lists; without conversion these are generally dynamic views
list(G.neighbors(i)) / list(G.adj[i]) Neighbours; successors in a directed graph
G.degree[i] / dict(G.degree()) One node's degree / a degree dictionary
G.graph['day']='Monday' Set a graph-level attribute
G.nodes[i]['color']='red' Set a node attribute; the node must already exist
G[i][j]['weight']=2 Set an existing edge's attribute; equivalent access is G.edges[i,j]
G.edges.data('weight') Iterate over (u,v,weight) records
G.adj.items() Nodes and their adjacency dictionaries; each undirected edge is encountered twice
G.remove_node(i), G.remove_edge(i,j) Remove one node or edge; deleting a node also deletes its incident edges
G.remove_nodes_from([...]) Remove multiple nodes; there is a corresponding bulk edge-removal method
G.clear() Remove all nodes, edges, and graph attributes

Attributes can be supplied when adding objects, for example G.add_edge(1,2,weight=4.7). Adding the same edge again can update its attributes. A view differs from an independent data copy: it reflects later graph changes. Convert it to a list or dict for a snapshot. When deleting objects during traversal, iterate over a list snapshot to avoid changing the object being iterated.

Directed and weighted example:

1
2
3
4
5
6
7
8
9
10
DG = nx.DiGraph()
DG.add_weighted_edges_from([(1, 2, 0.5), (3, 1, 0.75)])
DG.out_degree(1)                   # 1
DG.in_degree(1)                    # 1
DG.degree(1)                       # 2 (in + out)
DG.out_degree(1, weight="weight")  # 0.5
DG.degree(1, weight="weight")      # 1.25
list(DG.successors(1))             # [2]
list(DG.neighbors(1))              # [2]
list(DG.predecessors(1))           # [3]

Without weight, degree counts incident edges. With weight, it sums the relevant edge weights, giving strength. In a directed graph, degree is in-degree plus out-degree and need not equal the number of neighbors.

Graph Generators, Drawing, and Randomness

1
2
3
4
5
6
7
8
K5 = nx.complete_graph(5)
K35 = nx.complete_bipartite_graph(3, 5)
B = nx.barbell_graph(10, 10)
L = nx.lollipop_graph(10, 20)
ER = nx.erdos_renyi_graph(100, 0.15, seed=1)
WS = nx.watts_strogatz_graph(30, 4, 0.1, seed=1)
BA = nx.barabasi_albert_graph(100, 5, seed=1)
lobster = nx.random_lobster(100, 0.9, 0.9, seed=1)

ER's second parameter is the edge probability for each node pair. BA's second parameter is the number of edges attached to each new node. WS starts from a regular local ring and rewires edges; its second parameter specifies the initial neighbourhood, with the even value four used here for a straightforward interpretation. A barbell joins two complete graphs with a path; a lollipop joins a complete graph to a path; the random-lobster generator produces a random tree structure. Parameters from different models are not interchangeable. A random seed reproduces a particular sample; it does not make that sample equal to the model average.

1
2
3
4
5
6
import matplotlib.pyplot as plt
G = nx.petersen_graph()
pos = nx.spring_layout(G, seed=1)
nx.draw(G, pos, with_labels=True, node_size=300)
plt.savefig("network.png", dpi=200)
plt.close()

Random, circular, spectral, and shell layouts provide alternative node placements; shell layers are supplied through nlist. A layout changes drawing coordinates, not adjacency or graph metrics. Two nodes drawn nearby need not have a short graph distance, and crossing drawn edges do not create a node at the crossing. Gephi is a separate tool for exploring and visualizing large networks. Social-media networks illustrate the large size and heterogeneous connectivity of real systems; their drawing coordinates are not intrinsic graph properties.

Functions and Preconditions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Components and paths
list(nx.connected_components(G))  # undirected
list(nx.strongly_connected_components(DG))
list(nx.weakly_connected_components(DG))
nx.shortest_path(G, source=1, target=4)
nx.shortest_path_length(G, source=1, target=4)
nx.average_shortest_path_length(G)
nx.eccentricity(G)
nx.diameter(G); nx.radius(G)
nx.center(G); nx.periphery(G)

# Centrality (returns dictionaries keyed by node)
nx.degree_centrality(G)
nx.closeness_centrality(G)
nx.betweenness_centrality(G)
nx.eigenvector_centrality(G, max_iter=1000)
nx.katz_centrality(G, alpha=0.1, beta=1.0)
nx.pagerank(G, alpha=0.85, weight=None)

# Cohesion and communities
nx.core_number(G)
nx.k_core(G, k=2)
nx.clustering(G); nx.average_clustering(G)
nx.transitivity(G)
nx.degree_assortativity_coefficient(G)
groups = nx.community.louvain_communities(G, seed=1, weight=None)
nx.community.modularity(G, groups, weight=None)

PageRank, Louvain, and modularity explicitly use weight=None here to match the unweighted formulas. The karate-club graph contains edge weights, which these functions generally use when that argument is omitted.

These are interface examples, not a sequence guaranteed to work on every input graph. Check connectivity before computing whole-graph distances, and use the appropriate strong/weak component functions for directed graphs. Iterative eigenvector, Katz, and PageRank calculations may require adjustments to the iteration limit or convergence tolerance; Katz also requires its spectral-radius condition. Calling nx.k_core(G) without kk returns the core corresponding to the largest core number. Distance is unweighted by default; weighted paths require an explicit argument such as weight='weight'. For weighted closeness, the corresponding parameter is called distance.

A Complete Reproducible Check

The following example uses the triangle-with-one-leaf graph from the preceding section and shows the complete path from input to results.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import networkx as nx
G = nx.Graph([(1, 2), (1, 3), (2, 3), (3, 4)])
n = G.number_of_nodes()
M = G.number_of_edges()
print(dict(G.degree()))       # {1: 2, 2: 2, 3: 3, 4: 1}
print(2 * M / n)              # 2.0
print(nx.density(G))          # 2/3
print(nx.average_shortest_path_length(G))  # 4/3
print(nx.center(G), nx.periphery(G))      # [3], [1,2,4]
print(nx.betweenness_centrality(G))        # node 3: 2/3
print(nx.average_clustering(G))           # 7/12
print(nx.transitivity(G))                 # 3/5
print(nx.core_number(G))      # {1: 2, 2: 2, 3: 2, 4: 1}
print(nx.community.modularity(G, [{1, 2, 3}, {4}]))
# -0.03125 = -1/32

H = G.copy()
H.remove_node(3)
print(list(nx.connected_components(H)))   # [{1,2}, {4}]

The printed ordering of sets or dictionaries is not part of the mathematical result. To extract the largest connected component as an independent subgraph, use

1
2
nodes = max(nx.connected_components(G), key=len)
largest = G.subgraph(nodes).copy()

Code-reading checklist: directed or undirected graph →\to strings split into separate nodes →\to repeated or weighted edges →\to weighted or unweighted degree →\to connectivity requirements →\to output type: scalar, path, set, or dictionary.

← Network metrics and algorithms · Series index · Comprehensive practice →