Find the broker in a network with NetworkX: the rise of the Medici

The problem

You have a network and want to know which node holds it together: the hub with the most links, or the broker that sits on the routes between everyone else. NetworkX gives you degree, closeness, and betweenness for this, all three defined in NetworkX from the ground up. The example is the 20 marriages among 15 leading families of early fifteenth-century Florence, which ship with NetworkX from Breiger and Pattison (Social Networks, 1986). Padgett and Ansell argued that the Medici rose to power by marrying into families that did not marry each other. Swap in your own edge list: contacts, coauthors, a power grid, or a food web read without direction (the third pitfall says how).

The code

Copy

import networkx as nx
import matplotlib.pyplot as plt

INK, ACCENT, SECOND, MUTED = "#1f2a44", "#c8553d", "#2a7f9e", "#8a8f98"

# ---- network: replace this line with your own graph
G = nx.florentine_families_graph()
# or nx.Graph(pairs) for a list of pairs, nx.read_edgelist(path) for a file with one "a b" per line
print(G)

# ---- three centralities; equal values share a rank, rounding keeps float noise from breaking a tie
measures = {"degree": nx.degree_centrality(G), "closeness": nx.closeness_centrality(G),
            "betweenness": nx.betweenness_centrality(G)}
rank = {m: {n: 1 + sum(round(v, 9) > round(c[n], 9) for v in c.values()) for n in G}
        for m, c in measures.items()}
btw = measures["betweenness"]
print(f"\n{'family':12s} {'links':>5s} {'close':>6s} {'betw':>6s}   rank: deg clo btw")
for n in sorted(G, key=lambda n: (-btw[n], n)):
    print(f"{n:12s} {G.degree[n]:5d} {measures['closeness'][n]:6.3f} {btw[n]:6.3f}"
          f"         {rank['degree'][n]:3d} {rank['closeness'][n]:3d} {rank['betweenness'][n]:3d}")

# ---- what each family holds together: remove it, count the pieces left
pieces = {n: nx.number_connected_components(G.subgraph(G.nodes - {n})) for n in G}
print()
for n in sorted(G, key=lambda n: (-pieces[n], n)):
    if pieces[n] > 1:
        print(f"without {n:9s} {pieces[n]} pieces")
print(f"no split: {sum(p == 1 for p in pieces.values())} families")
BROKER = max(btw, key=btw.get)
print(f"\nthe pieces without the {BROKER}:")
for part in sorted(nx.connected_components(G.subgraph(G.nodes - {BROKER})), key=len, reverse=True):
    print(f"  {len(part):2d}: {', '.join(sorted(part))}")

# ---- plot: the network, and every family's rank by each measure
color = {n: ACCENT if n == BROKER else SECOND if n in ("Strozzi", "Guadagni") else INK for n in G}
pos = nx.spring_layout(G, seed=81)
fig, (ax, bx) = plt.subplots(1, 2, figsize=(8, 4.2), width_ratios=[1.3, 1])
nx.draw_networkx_edges(G, pos, ax=ax, edge_color=MUTED, width=1)
nx.draw_networkx_edges(G, pos, ax=ax, edgelist=list(G.edges(BROKER)), edge_color=ACCENT, width=2)
nx.draw_networkx_nodes(G, pos, ax=ax, node_color=[color[n] for n in G],
                       node_size=[40 + 1200 * btw[n] for n in G])   # area grows with betweenness
below = {"Castellani", "Peruzzi", "Acciaiuoli"}           # names that fit better under their node
at = {n: p + (0, (-1 if n in below else 1) * (0.08 + 0.15 * btw[n])) for n, p in pos.items()}
nx.draw_networkx_labels(G, at, ax=ax, font_size=10, font_color=INK, bbox=dict(fc="white", ec="none", pad=0.5))
ax.text(1, 0, f"{pieces[BROKER]} pieces without the {BROKER}", color=ACCENT, ha="right", transform=ax.transAxes)
ax.set_axis_off()
for n in G:
    ranks = [rank[m][n] for m in measures]
    hi = n in (BROKER, "Strozzi", "Guadagni")
    bx.plot(range(3), ranks, "o-", color=color[n] if hi else MUTED, lw=1.8 if hi else 0.8,
            ms=4, zorder=3 if hi else 2)
    if n in (BROKER, "Guadagni", "Strozzi", "Ridolfi", "Salviati"):
        bx.text(2.08, ranks[2], n, va="center", fontsize=10, color=color[n] if hi else MUTED)
bx.set(xticks=range(3), xticklabels=list(measures), xlim=(-0.2, 2.6), ylim=(15.5, 0.5),
       yticks=[1, 5, 10, 15], ylabel="rank")
bx.spines[["top", "right"]].set_visible(False)
plt.show()

Graph with 15 nodes and 20 edges

family       links  close   betw   rank: deg clo btw
Medici           6  0.560  0.522           1   1   1
Guadagni         4  0.467  0.255           2   5   2
Albizzi          3  0.483  0.212           4   3   3
Salviati         2  0.389  0.143          10   9   4
Ridolfi          3  0.500  0.114           4   2   5
Bischeri         3  0.400  0.104           4   8   6
Strozzi          4  0.438  0.103           2   6   7
Barbadori        2  0.438  0.093          10   6   8
Tornabuoni       3  0.483  0.092           4   3   9
Castellani       3  0.389  0.055           4   9  10
Peruzzi          3  0.368  0.022           4  11  11
Acciaiuoli       1  0.368  0.000          12  11  12
Ginori           1  0.333  0.000          12  13  12
Lamberteschi     1  0.326  0.000          12  14  12
Pazzi            1  0.286  0.000          12  15  12

without Medici    3 pieces
without Albizzi   2 pieces
without Guadagni  2 pieces
without Salviati  2 pieces
no split: 11 families

the pieces without the Medici:
  11: Albizzi, Barbadori, Bischeri, Castellani, Ginori, Guadagni, Lamberteschi, Peruzzi, Ridolfi, Strozzi, Tornabuoni
   2: Pazzi, Salviati
   1: Acciaiuoli

The knobs

Each measure answers its own question, so the one you pick changes the answer. Degree counts a family's marriages and sees nothing beyond them. Closeness, one over the mean distance to every other family, is high for a family that reaches everyone in few steps and would hear news first: the Ridolfi, with three marriages, reach 11 of the other 14 families within two steps and come second, ahead of the Strozzi with four. Betweenness, the share of shortest paths between other pairs that run through a node, is high for a family the others must go through, the broker. A broker ranks far higher by betweenness than by degree: the Salviati are tenth by degree and fourth by betweenness, as the Pazzi's only link to anyone. A hub goes the other way: the Strozzi, tied second by degree, are seventh by betweenness, and nothing falls off without them. The Medici are both. Equal values share a rank, so the six families with three marriages are all fourth. Neither closeness nor betweenness reads an edge attribute unless you name it, distance= for the one and weight= for the other, and both read it as a length; if your ties have strengths, store 1 / weight as a new attribute and pass its name, as the weighted variation of the prerequisite does.

The piece counts are the test of what a node holds together. connected_components returns the pieces of a network, each a set of nodes joined by some path. Without the Medici the marriages fall into three pieces, without the Albizzi, Guadagni, or Salviati into two, and without any of the other 11 families they stay whole. The count says that something falls off, not how much: of the 14 families left without the Medici, 11 still hang together and only three are cut off. Betweenness assumes that whatever travels goes along shortest paths only, which for an alliance that can run through any in-law is a rough model, so trust the ranks and not the third decimal. Padgett and Ansell's argument rests on more than one number, and the three pieces are what the marriage network loses, not what Florence lost.

Pitfalls

Comparing normalized with raw betweenness. The Medici have 0.522 here and 47.5 in an older paper or another program. By default NetworkX divides by the number of pairs among the other nodes, \((n-1)(n-2)/2 = 91\) for 15 families (47.5 is 0.522 times 91), so its betweenness is a fraction, while many sources report the raw sum. Say which one you report, and pass normalized=False before you compare with a raw value:

print(f"raw betweenness of the Medici: {nx.betweenness_centrality(G, normalized=False)['Medici']:.1f}")

raw betweenness of the Medici: 47.5

Trusting a rank from one edge. On 15 nodes, one link moves the ranking. Remove the single marriage between the Medici and the Albizzi and the gap between first and second shrinks from 0.27 to 0.03. Before you report a rank, recompute it with each edge removed in turn:

H = G.copy()
H.remove_edge("Medici", "Albizzi")
b = nx.betweenness_centrality(H)
print(f"without Medici-Albizzi: Medici {b['Medici']:.3f}, Guadagni {b['Guadagni']:.3f}")

first = []
for u, v in G.edges:     # remove each marriage in turn, record who comes out first
    H = G.copy()
    H.remove_edge(u, v)
    b = nx.betweenness_centrality(H)
    first.append(max(b, key=b.get))
print(f"first after each of the {len(first)} single removals: {sorted(set(first))}")

without Medici-Albizzi: Medici 0.456, Guadagni 0.423
first after each of the 20 single removals: ['Medici']

Here the Medici stay first after each of the 20 removals, so their rank holds. A rank that changes hands under one removal rests on a single link in your data, and is not worth reporting.

A directed network such as a food web. If you build an nx.DiGraph yourself, connected_components raises NetworkXNotImplemented: not implemented for directed type; the loaders in the code build an undirected graph and drop the direction without a word. With arrows, reaching is no longer mutual, so a piece comes in two kinds, strong (every node reaches every other along the arrows) and weak (joined once you ignore them), and closeness and betweenness count only paths along the arrows. Decide what you ask. Which species hold the web together as one piece ignores direction: call G = G.to_undirected() once, the pieces become the weak ones, and the recipe runs unchanged. How energy flows from prey to predator needs directed centrality, which this recipe does not do.