Week 4 of 8 · Networks half

Communities and seeing networks

Week 3 zoomed in on the single node. This week we zoom out one level, to communities. The groups of nodes that hang together: your family, workplace book club, and soccer team.

1 · Communities

Communities are in the middle in the network. The smallest parts are nodes, we also have the whole network. And communities are in between. They are groups of nodes. We all have intuitions for them. Families, classmates, friend groups, workplaces, and so on, are all groups.

There are communities in other networks too, but we'll focus on social networks. Communities are so important that I've already kind of used them in the class. In week 1, when we talked about network visualization, I included communities in the visualization. And the cliques from last week are a kind of super-connected communities (more on that later).

Because I want to work on a network with strong community structure, we're dropping the Marvel network this week and switching to philosophers. The Marvel network does have community structure, but it's not super strong (Section 4 has the numbers), I'd like to find a network where you can actually see the groups.

The network I've chosen consists of every philosopher born before 1900 on Wikipedia's lists of philosophers by century. There's 1,444 of them, with a link wherever one article links to another, just as before.

The giant component holds 1,374 philosophers and 9,139 links, and the communities in it are systems of philosophy that you may have heard of: Greek antiquity, the medieval scholastics, German idealism, Indian and Chinese philosophy. Data, incl. a weight on every link, can be found on the data page.

There are thousands of papers on finding communities. Part of the reason is that nobody has ever agreed on a definition, so people can always just come up with a new one and write a paper. For years people argued that a community is a set of nodes that is densely interconnected and weakly connected to the rest of the network. (I've actually shown that sometimes even the mild definition above is too strict. It's actually only about being densely interconnected. But I'm getting ahead of myself. More on that later.)

But why are we even looking for communities? There are three reasons.

• Summary: The level of individual nodes is too detailed. The whole network is too broad. Eight or nine communities is a way to organize how the information in the network is structured.
• Meaning: A community helps you understand what's going on in the network. In the philosopher network we already discussed how the communities are the different systems (or schools) of philosophy.
• Visualization: When we color by community, that somehow helps us parse the network visually. And it looks cool ;)

A lecture that captures the spine of this page: it covers five ideas in order, and Sections 2–6 below follow the same order (edge betweenness, modularity, optimizing modularity, k-clique communities, link communities, which take up about the second half). The video uses different example networks; treat it as the guided tour, the text below as the map. It's OK to watch it AFTER reading.

2 · Cutting the bridges: edge betweenness

Origin story. Even though we're not using the Marvel network, it's time for an origin story. I'm going to let you in on how community detection started. And there's a nice connection to last week: betweenness.

Back in 2002, Michelle Girvan and Mark Newman had an idea. As you recall from last week, betweenness is based on the number of shortest paths that run through a node. Give the same count to a link and you have edge betweenness: the number of shortest paths that run along it.

Girvan and Newman were trying to think about a network made of groups. Trying to think about how they could split it into the groups in an automated way. And they realized that links between groups would have high edge betweenness.

Here is the reason. Paths between two members of the same group stay inside the group, spread over its many links. Paths between two groups carry all of the "traffic" going between the two groups. So the bridges will all have high edge betweenness.

So the idea was this:

• Compute the edge betweenness of every link.
• Remove the link with the highest value.
• Recompute every value (because a removal reroutes the traffic: the paths that used the cut link now crowd onto the remaining bridges).
• Repeat.

As you run this simple algorithm, the network falls apart into groups, the biggest cuts first, and if you record the order in which groups split you get a tree, a dendrogram: the network's hierarchy of groups, from one blob at the root down to single nodes at the leaves.

A benchmark network with three planted communities of 28, 32 and 40 nodes. The violet link carries the most shortest paths (286.4) and goes first. Press Step a few times and watch the readout: every cut is a link between two planted groups, and as the bridges thin out the survivors carry more and more (by cut 13 the top value is over 1,000). Press Next split: cut 15 is the last link between a group of 68 and a group of 32, and it carries exactly $68 \times 32 = 2{,}176$ shortest paths, one for every pair across. Right after the split the recomputed values drop to 183. Press Next split again: cut 27 leaves the three planted groups, and the strip under the dendrogram marks that level as the best one, $Q = 0.571$ (Section 3 explains $Q$). Then Play, and watch the groups crumble.

The Zachary Saga. The first network Girvan and Newman tested it on is the most famous small network there is, and it deserves its own digression. In the early 1970s the anthropologist Wayne Zachary spent three years watching a university karate club. It had 34 members, an instructor known in the paper as Mr. Hi, and a president, and the two of them had a serious disagreement over the price of lessons.

As an anthropologist, Zachary had hit the jackpot. He had chosen to study a random karate club, and then something really exciting happened. The club split into two factions. Now Zachary had an exciting paper to write.

But from the perspective of network science Zachary also brought something to the table. He had recorded who was friends with whom outside the club: 34 nodes, 78 links. And he asked his network nodes who they supported in the feud. And you can see it right there in the network. Two communities, split right down the middle.

Anecdote 1: The network structure only got it almost right. It got 33 of the 34 right. The one miss was a member who sided with the instructor for a reason no network could see: he was three weeks from his black-belt exam and did not want to start over.

Girvan–Newman's first cut on the club is the friendship between Mr. Hi (member 0) and member 31, with edge betweenness 71.4, far ahead of the next link at 43.8. After 11 cuts the club has fallen into two groups of 19 and 15, wrong about only two members, one of them the black-belt student. You can see the network down in Section 3's explorable.

And this network somehow became the "fruit fly" of community detection, used in hundreds upon hundreds of papers. In part because it had ground truth. Zachary had labeled the two communities, so we knew what the groups should be. That information usually is not available for most networks.

Anecdote 2: In fact, the network became so overused that network scientists started a running joke: at any network conference, the first speaker to put the karate club on a slide is inducted into the Zachary Karate Club Club and handed a trophy to keep until the next conference. The idea was Aaron Clauset's; the tradition began in 2013 at the Santa Fe Institute, and the first holder was the physicist Cristopher Moore.

Inductee #3 collects the prize: my friend and collaborator YY Ahn (left) takes the trophy from Mason Porter (right, inductee #2) for putting the karate club on a slide at the Oxford Workshop on Time-Dependent and Multiplex Networks, July 2013. Photo: the Zachary Karate Club Club.

The Girvan–Newman algorithm is beautiful, so why didn't people just use that and be done with it? See if you can guess. The answer is that it is slow. Way too slow to use in practice.

Every cut needs a full recomputation of edge betweenness, which means a shortest-path search from every node, and there is one cut per link: $O(m^2 n)$ in total. On the karate club that is nothing. On the philosophers, a single edge-betweenness pass takes about five seconds in networkx on my laptop which is pretty decent, and a full run needs one pass for each of the 9,139 links: hours of computing to find groups that Section 4 finds in a second. It's available in networkx as girvan_newman.

3 · A dendrogram isn't really communities: modularity

A dendrogram isn't really communities. If you look at the explorable up in Section 2, you'll see that what you really get is a recipe for splitting up the network part by part. So what's the best way to split it up, where should you cut the dendrogram?

In a follow-up paper in 2004, Newman and Girvan proposed a measure of how community-like a specific partitioning of a network is so you can decide in a quantitative way. A recipe to score the groups at every single level, and cut where the score is highest. The number is modularity, and it turned out to do its job well. So well in fact, that it became a whole thing in its own right — much more than Girvan and Newman originally thought it would be (much more on this below).

Modularity is a way to score a proposed split. To get started, let's take the karate club, where we know the answer, and count the links that fall inside groups: in Zachary's real split, 67 of the 78 friendships stay within a faction, and only 11 cross. That sounds like a lot, but (as last week) compared to what? If you shuffled the friendships at random while keeping everyone's number of friends (the degree-preserving null from week 2, the configuration model), how many would land inside the same two groups by chance alone?

The expected number of links between nodes $i$ and $j$ under that null is $k_ik_j/2m$. If you subtract that number from the actual number of links, you have modularity:

$$Q = \frac{1}{2m}\sum_{ij}\left(A_{ij} - \frac{k_ik_j}{2m}\right)\delta(c_i, c_j),$$

where $\delta(c_i, c_j)$ is 1 when $i$ and $j$ are in the same community and 0 otherwise.

In words modularity is the fraction of links inside communities, minus the fraction you would expect within communities by chance, given the degrees. For hand computation the same quantity per community $c$ is

$$Q = \sum_c \left[\frac{\ell_c}{m} - \left(\frac{d_c}{2m}\right)^2\right],$$

where $\ell_c$ is the number of links inside community $c$ and $d_c$ the sum of the degrees of its members.

And modularity has some nice properties. Putting all nodes inside a single community gives $Q = 0$ exactly; a random assignment of nodes into communities also gives you $Q \approx 0$, and a partition where links are only inside groups and rarely cross can yield a $Q$ up to a theoretical 1. Real networks with clear groups tend to land somewhere between 0.3 and 0.7 depending on the network.

Zachary's real split scores $Q = 0.358$.

With modularity in place, we have a strategy for how to cut the dendrogram. We simply check the value for every single partition and pick the best one. On the karate club, Girvan–Newman's two groups score $Q = 0.360$, but the best level of its dendrogram is five groups, $Q = 0.401$, after 24 cuts. More in the explorable below. (On the benchmark in Section 2's explorable, the best level is exactly the three planted groups.)

The club, colored by Zachary's real split: $Q = 0.358$, 67 of 78 friendships inside the two groups, 39 expected by chance. Click member 2 to move them across and $Q$ drops to $0.329$; click member 8, the one Zachary's model got wrong, and it rises to $0.372$; click member 0 (Mr. Hi himself) and it collapses to $0.166$. Press Best two-way split for the partition that beats the real one, and Louvain for four groups the club never had, at $Q = 0.420$. Then Shuffle members and see where chance lands. The strip on the right is the landscape you are walking on.

There are two important things that the explorable shows that the formula does not. First, $Q$ is not maximized by Zachary's ground truth. Moving member 8 to the other side raises $Q$ (he has more friends there; remember that the black-belt exam was the reason he stayed), and a four-group split scores higher than the real two factions (because each faction had an inner circle). Modularity measures how grouped a partition is, not how right it is; there is no "right" inside the number. Second, the landscape is full of near-ties: many different partitions have almost the same modularity. In other words, in spite of many nice qualities, modularity has lots of issues and isn't necessarily always used to detect communities nowadays. We will discuss those issues in detail below.

4 · Optimizing modularity: from greedy merging to Louvain

At some point Mark Newman realized that you don't need the dendrogram at all. If $Q$ is a measure of how good communities are, why not just find the split of the network that optimizes $Q$ directly? It turns out that this is a really difficult optimization problem because there are many ways to split up a network into partitions. For our example network with the philosophers, the number of ways to partition 1,374 nodes is a number with 2,804 digits, and finding the maximum exactly is NP-hard.

So Newman didn't attempt to truly optimize $Q$. In a second 2004 paper, instead, the idea is to basically run Girvan–Newman backward. Start with every node in its own community. Of all the pairs of communities that share a link, merge the pair whose merge raises $Q$ the most. Record $Q$, and repeat until everything is one community; then keep the level where $Q$ was highest. That is a dendrogram built bottom-up, where Section 2's was top-down, and it is fast, because the change in $Q$ from one merge depends only on the two communities involved. It is also greedy: a merge is never undone, so an early merge that looked good locks in its mistake.

On the philosophers, networkx's version (greedy_modularity_communities, a faster implementation of the same rule by Clauset, Newman and Moore) finds 15 communities with $Q = 0.416$: three giant blobs of 550, 481 and 262 philosophers, one of them Heraclitus and Plotinus together with Bertrand Russell and Albert Einstein, plus a dozen small groups. Greedy optimization is almost never great. In this case, early merges snowball, and the big communities cannot be taken apart again.

So I mentioned there were a lot of modularity papers, and many of those are simply clever ways to climb the modularity landscape without seeing all of it.

But in 2008, researchers came up with a method that is good enough. It is the algorithm everybody still uses, and the team behind it was Vincent Blondel and three colleagues at the Université catholique de Louvain, in Belgium, and the algorithm is named after the town. One of the three, Renaud Lambiotte, was a guest on my podcast; the Louvain story starts at 28:38, t-shirt included. It is embarrassingly simple and super fast, and I think the speed has something to do with its popularity. The Louvain algorithm also fixes greedy merging's worst habit by allowing single nodes to change community. It works like this.

Phase 1: move nodes. Start with every node in its own community. Visit the nodes one by one. For each node, try moving it into the community of each of its neighbors, compute the change in $Q$ each move would cause, and make the best move if it raises $Q$; otherwise leave the node where it is. Sweep through all nodes, then sweep again, until a whole sweep moves nobody.

Phase 2: aggregate. Collapse each community into a single super-node. Links between two communities become one weighted link (weight = how many links crossed); links inside a community become a weighted self-loop. Now you have a smaller network. Go back to phase 1 and run it on that.

Repeat until phase 1 moves nothing. The communities of the last level, unpacked back to the original nodes, are the answer. Because each move only touches one node and its neighbors, one sweep costs about as much as reading the edge list once, and Louvain runs on networks with hundreds of millions of links. Watch it work on the philosophers:

Press Step a few times: one philosopher at a time joins a neighbor's community and $Q$ ticks up. Then press Sweep twice: two passes over all 1,374 philosophers make 1,794 moves and leave 165 groups at $Q = 0.380$, past the dashed line at $0.228$ that a shuffled network reaches (the line is crossed at move 1,226). Press Aggregate: phase 1 finishes (65 groups, $Q = 0.458$) and the groups collapse into 65 super-nodes. Then Play: the second level needs only 73 more moves, and the third just two, to reach 8 communities and $Q = 0.506$, where no single move can improve anything.

Run to the end, the explorable finds 8 communities with $Q = 0.506$. If we name them after their highest-degree member (as the legend does), we can now read and see a connection to the history of philosophy. Aristotle's group is Greek and Roman antiquity (Plato, Cicero, Heraclitus, Socrates). Thomas Aquinas's is Christian thought from Augustine through Dante to Luther and Erasmus. Immanuel Kant's is German philosophy from Schelling and Hegel to Marx and Nietzsche. René Descartes's is early modern Europe and the Enlightenment (Leibniz, Spinoza, Locke, Hume, Voltaire). Bertrand Russell's is the generation that founded 20th-century philosophy (William James, Peirce, Bergson, Wittgenstein, and Albert Einstein). The Buddha's is Indian philosophy, and Confucius's is Chinese philosophy, Mao Zedong included. The group named after Avicenna puts the medieval Islamic and Jewish philosophers (Averroes, Maimonides, al-Ghazali) together with Galileo, Copernicus and Francis Bacon, which is not a school anyone would name. You can construct a story for the communities we found (Greek science reached the Renaissance through Arabic translations and commentaries), but notice that you would be constructing it. That's a key distinction: the names are labels of the partition, while the story is what one tells afterward as we interpret the data.

Compared to what? Louvain finds $Q = 0.51$ on the philosophers. Is that a lot? I did say that values between 0.3 and 0.7 were what we would find in networks with community structure. But we can do better.

Can we use the null models that I introduced in Week 2? Let's shuffle and see. We can take the same 1,374 philosophers and 9,139 links, rewire them with the degree-preserving shuffle, and run Louvain on the result. Twenty shuffles give $Q = 0.228 \pm 0.002$. A completely random network with the same $n$ and $m$ gives $0.233$.

You can learn two things from this. Firstly, what we set out to learn. The philosopher network does indeed have communities. But, secondly, we see that the modularity of a random network is not zero!

A random network has no communities by construction, and Louvain still finds a partition with $Q = 0.23$, because with thousands of links there is always some way to draw group borders that cross fewer links than expected, and an optimizer is built to find it. (Roger Guimerà, Marta Sales-Pardo and Luís Amaral pointed this out in 2004, and it is still the most common mistake in reports that quote a modularity; Marta and Roger are an episode of my podcast, on Bayesian statistics and how they became scientists.) And how high can a network with no communities score? Much higher than $0.23$, it turns out: the sparser the network, the easier it is to find borders that few links cross, and a random network with an average degree of 2 reaches $Q \approx 0.8$. Exercise 4.6 has you map this out, and it is why Section 3's "0.3 to 0.7" is a rule of thumb and not a test.

How stable? If we run Louvain on the philosophers with ten different seeds (the order nodes are visited in phase 1 is random) we get different solutions. Somewhere around 8, 9 or 10 communities with $Q$ between $0.500$ and $0.508$.

Notice that $Q$ is almost the same in spite of quite different splits of the network (partitions).

To understand this phenomenon, we need a number for how much two partitions agree, and the standard one is the normalized mutual information (NMI). It is calculated as follows: treat each partition as a labeling of the nodes, compute how much knowing one label tells you about the other, and scale so that identical partitions give 1 and independent ones give 0. In symbols: with $n$ nodes, $n_x$ the size of community $x$ in the first partition, $n_y$ the size of community $y$ in the second, and $n_{xy}$ the number of nodes in both, the mutual information is $I = \sum_{x,y} \frac{n_{xy}}{n} \log \frac{n\, n_{xy}}{n_x n_y}$, and $\mathrm{NMI} = 2I / (H_1 + H_2)$, where $H = -\sum_x \frac{n_x}{n} \log \frac{n_x}{n}$ is each partition's entropy (the mutual information of a partition with itself). networkx has no NMI function; use sklearn.metrics.normalized_mutual_info_score(labels_a, labels_b), whose default is exactly this formula. Between two Louvain runs on the philosophers (seeds 0 and 1), NMI is $0.76$; across all 45 pairs of the ten runs it ranges from $0.65$ to $0.83$.

The runs agree on most of the split of the network, but disagree at the borders of communities. Descartes and Locke share a community in eight runs out of ten, Avicenna and Galileo in three (and in the explorable's run), and in one run Aristotle leaves Plato for Thomas Aquinas and the scholastics.

On Marvel, NMI between two runs is $0.59$: the partitions agree about as much as they disagree. That is one reason this week uses the philosophers rather than Marvel. Here's another key thing to remember. Because many different partitions can have similar modularity, never think of a partition as the "truth," it's more like a sample of what communities could be. Consensus between many runs is more stable and powerful. The sparse random networks from before make the point sharply: a random network with an average degree of 5 scores $Q = 0.45$, squarely in the range of real networks, and two Louvain runs on it agree at an NMI of about $0.2$. A high $Q$ with a low NMI is a score without a structure behind it (exercise 4.6 again).

Ground truth revisited Remember that part of what made Zachary's network popular was the ground truth communities? Well, here's an idea for how to use ground truth about communities.

When you have ground-truth labels, you can compare your partition to the ground truth labels via NMI. The philosophers come with a kind of label: the node file's era column says which century list each philosopher is on. NMI between the partition and the century is $0.40$, so we can learn that the communities are traditions, not centuries. Wikidata's "movement" label (stoicism, scholasticism, German idealism, for the 315 philosophers who have one) does better, $0.49$. And that's a finding about metadata, or "ground truth": it's not really the truth either. It is more like someone else's reading of the same people. If three checks on one number feels like a lot of patching, you are not alone: the Goodies box Peixoto's war on modularity makes the case for dropping modularity altogether, and says what to use instead.

5 · Overlap I: k-clique communities

But modularity isn't the only way to find communities. It's just one way of thinking about them. Below we discuss the first steps in a new direction.

$k$-clique communities. Everything so far assumed that a node belongs to exactly one community. But is that really the case in real networks? Take Aristotle. He is the center of Greek philosophy. But he is also the authority of the medieval scholastics (Aquinas calls him simply "the Philosopher"), and he turns up in almost every tradition since. Any partition of the nodes has to put him in only one of those and get the others wrong. And the same is true of people in real social networks: you are part of a family, a workplace, a soccer team, and placing you in only one of those communities would be just plain wrong.

The first method built for overlap is based on cliques. It was proposed by Gergely Palla, Imre Derényi, Illés Farkas and Tamás Vicsek in 2005. You need one more concept beyond the clique, clique adjacency. Let's call a clique of size $k$ a $k$-clique. Then we say that two $k$-cliques are adjacent if they share $k - 1$ nodes.

And we define a k-clique community as a connected set of adjacent $k$-cliques.

At $k = 3$, press Step: a triangle tips onto a neighbor it shares a side with, and the community grows one clique at a time. E ends up in both communities (two colors), K in none. Then switch to $k = 4$, $5$ and $6$ and watch who drops out.

For $k = 3$, picture a triangle tipping over one of its sides onto the next triangle. Two triangles that share only a single node are not adjacent, so that node can sit in two communities at once; and a node that is in no $k$-clique is in no community at all. The result is not a partition twice over: communities overlap, and some nodes are left out. The group released the method as software, CFinder, which finds the communities and draws them; in Python it is networkx.community.k_clique_communities(G, k). Note that this definition also means that not every node is a part of a community. In 3-clique communities you have to be part of a triangle, etc.

The size $k$ acts as a kind of community resolution. Let me illustrate via the philosophers:

At $k = 3$ almost everything is connected in one giant community: triangles are everywhere, many of them share a dyad. It is a percolation transition, the same kind as week 2's random graph, and that is how Palla and colleagues described it. At $k = 4$ separate traditions break off: 31 Chinese philosophers, 16 Islamic theologians, 8 of the Vedanta school. At $k = 5$ the rest are small, sharp schools: the Church Fathers, the Legalists of ancient China (Han Fei, Shang Yang), the Russian religious philosophers, the Neo-Confucians. At $k = 6$ fewer than a quarter of the philosophers are in any community. And the overlap nodes are the hubs: at $k = 5$, Aristotle is in six communities, Augustine, Aquinas and Nietzsche in five each. There is no right $k$; report the one you chose, as you would any parameter.

6 · Overlap II: link communities

My favorite road to overlap, comes from a 2010 paper by Yong-Yeol Ahn, James Bagrow and Sune Lehmann (yes, that one). There's something appealing about that author team, can't quite put my finger on it. YY is also the trophy-holder in Section 1 and my guest on the podcast about doing research with Claude Code). What we notice in that paper is that while a nodes often participate in many contexts, link are typically much more unambigous.

So what happens if we cluster the links? Family links with family links, work links with work links, etc.

In the paper we argue that two links that share a node, $i$–$k$ and $j$–$k$, are similar if the neighborhoods of $i$ and $j$ overlap (a kind of Jaccard-style score: the neighbors they share, over the neighbors either has).

Now that we have a similarity, we can cluster links by that similarity, and each cluster of links is a link community. Then every node inherits all the communities its links belong to. A node with links in three link communities is in three communities, at no extra cost, and the overlap is a natural part of the method instead of being bolted on. The second half of the video lecture in Section 1 is this method, so you can get details there.

When we do hierarchical clustering we get a dendrogram, this time of links, and once again we have to decide where to cut it. Modularity is defined for groups of nodes, so in the paper, we introduce a score for groups of links, partition density. A link community $c$ with $n_c$ nodes needs at least $n_c - 1$ links to hang together (a tree) and can have at most $n_c(n_c - 1)/2$ (a clique); its density is how far its $m_c$ links sit between the two, and $D$ averages that over the communities, weighted by their number of links:

$$D = \frac{2}{M}\sum_c m_c\,\frac{m_c - (n_c - 1)}{(n_c - 2)(n_c - 1)}$$

with $M$ the total number of links. In the 2010 paper we cut the dendrogram where $D$ is highest.

But with a brilliant student, I actually just updated and improved the idea. Here's what the new paper does. I realized that one cut height for the whole tree is a simplification. In the new paper we let every branch of the dendrogram have its own height (instead of a single cut) and that way we can get significantly better partition density and modularity across more than 200 real networks (Louis Boucherie, Yong-Yeol Ahn and Sune Lehmann, Adaptive cut reveals multiscale complexity in networks, arXiv:2512.08741).

Remember how we defined communities as densely interconnected with weak connections between communities. Highly overlapping communities are very different form that image. If every node is the member of many communities, then every community has more outgoing links than incoming ones. In a really interesting way, the network is locally super dense (the link communities are natually very clique-like), but can still be quite sparse at a global level. That means that link communities are especially suited for very dense networks. So if one wanted to analyze communties in the Marvel network, it might be worthwhile looking at link clustering over Louvain (see the explorable below). But don't link-cluster everything: Louvain is probably more appropriate for the philosophers ... and for any other network with visible network structure in the network plot.

Every block in the dendrogram is one link community, and every link on the network belongs to exactly one. Press Next community to walk through the teams (the X-Men, the Spider-Women, Blade's supernatural corner) and watch Spider-Man light up in 23 of them. One cut is the single height where $D$ peaks; Adaptive cut lets every branch choose its own, and the Goodies box explains it. Switch to Philosophers for Section 4's network.

What this explorable shows is also the weakness of most overlapping methods ($k$-cliques, link clustering). They are not great at parts of the network that are sparse and not overlapping. Those sparse parts end up with a lot of non-community nodes or single-community links. So they are effectively not assigned to any meaningful community. Sometimes that's a problem, sometimes it's not, depending on what you are trying to learn about the network. The overall lesson is that no tool is perfect, and you need to think and choose wisely.

7 · Weights: strong ties and weak ties

Phew. That's a lot of info on communities. Now take a break, a beat, a pause. Maybe a deep breath. Look up and focus your eyes away from the screen.

I'm asking for a pause because these last two parts are a whole new topic, that I'd also like to squeeze in before we get to the NLP part of the course.

Until now we have mainly considered unweighted networks. But before we wrap up the network part of the course, I want to put some tools and ideas about weighted networks on your radar.

Even though we've ignored it, the philosophers' edge file actually carries a weight on each link: the number of times A's article links to B's. Most pairs link once; a few link over and over, because the two philosophers' lives or ideas are entangled. Summed over both directions, the weights run from 1 to 24, while 5,899 of the 9,139 links have weight 1.

Weights change three things.

First, in weighted networks nodes have both degree and strength: $s_i = \sum_j w_{ij}$. Strength is just the sum of the total weight on a node's links. On the philosophers, strength and degree rank nodes almost identically (Spearman $0.96$; Aristotle leads both rankings with strength 521 based on a degree of 300). But the exceptions are the interesting part: Diogenes Laertius has only the 15th-highest degree (91) but the fifth-highest strength (230). If you're a philosophy buff, you'll realize that this is because his book Lives of the Eminent Philosophers is the source of a lot of knowledge about ancient philosophers, so the wiki articles of many ancient philosophers cite him again and again.

Second, the strongest ties often tell a story: Erasmus–Thomas More (24, close friends; Erasmus wrote The Praise of Folly in More's house), John Adams–Thomas Jefferson (22, fifty years of rivalry and letters, and death on the same day), Alfred North Whitehead–Bertrand Russell (19, Principia Mathematica). A weight of 24 between two pages says something a single link does not.

Third, paths are counted differently in weighted networks. Because a strong tie can be thought of as a short distance, network scientists often use $1/w_{ij}$ as the "length" of a link (and run an algorithm called Dijkstra's algorithm to estimate path lengths instead of BFS). David Hume and Karl Marx are two hops apart on the unweighted network, through any of 22 middlemen (Adam Smith, for one). The shortest strong-tie route between them is Hume → Kant → Hegel → Marx, one hop longer, over links of weight 7, 7 and 10. And it's not just shorter when you measure length as $1/w$, I'd argue that there's important information in the shortest weighted path: that's the route a history-of-philosophy lecture would take.

Weights and communities. Both modularity and Louvain can include weights without big changes. Simply replace $A_{ij}$ by $w_{ij}$, degrees by strengths, and $m$ by the total weight. Weighted Louvain on the philosophers finds 9 communities with a weighted $Q$ of $0.55$. That is higher than the unweighted $0.50$, but do not compare the two numbers: they are answers to different questions, and the strong ties concentrate inside groups almost by definition, so the weighted score has a higher ceiling. As always, to understand a value, compare it against the appropriate shuffled network.

For some reason that is not clear to me, the unweighted communities often seem more intuitive than the weighted ones, though.

8 · Seeing structure in the hairball: backbones

Sune's quick take on backbones: why the hairball happens, the naive threshold and its failure, and the disparity filter with its null model.

Week 1 ended with a warning: a force layout of a big network is often an uninformative hairball. The presence of a hairball does not imply the absence of structure. It could be there because the network is so large that you can't calculate a good layout. It could be there because the network is full of overlapping communities. It could be there because there's a giant hub somewhere obscuring all the structure. Etc., etc.

By now you have the tools to dig into the hairball and understand the structure that it hides. But what if you want to visualize it anyway? Backbones are a way to begin to see structure in weighted networks that is obscured by many low-weight links.

A global threshold. If we start with philosophers, that network's giant component has 9,139 links. Most of them have weight 1, and a good fraction of those are a single passing mention on one page. If you could keep only the links that matter, the drawing would perhaps show some meaningful structure.

The set of links with large weights is the quintessential backbone of a network. The backbone of the most important links. This global threshold, where we keep every link with $w \ge 3$, for example, is quintessential, but also naive. And it has the problem that it throws away too much data.

On the philosophers that keeps 1,572 links and 863 philosophers. The problem is who it throws away. A weight of 2 is nothing for Aristotle (strength 521) and the strongest tie a minor philosopher has. A global threshold keeps a hub's fiftieth-strongest link and discards a small node's only meaningful one, so in many networks, the backbone based on weights becomes the hubs talking to each other, and everyone else disappears.

The disparity filter. In 2009 Serrano, Boguñá and Vespignani came up with an idea to fix this with yet another null model. But the twist this time is that the model is per node. In their model, for node $i$ with degree $k_i$ and strength $s_i$, each link carries a share $p_{ij} = w_{ij}/s_i$ of the node's strength. Serrano et al. compare that to the following null: the node's strength is spread over its $k_i$ links uniformly at random. Under that null, the probability that one link ends up with a share of at least $p_{ij}$ is $(1 - p_{ij})^{k_i - 1}$. That means that a link is significant for node $i$ when that probability is below a level $\alpha$ that we can adjust:

$$(1 - p_{ij})^{\,k_i - 1} < \alpha$$

To follow this algorithm, iterate over all nodes and keep a link if it is significant at either end.

Local importance. Take the weight-2 link between Aristotle and Moses of Narbonne, a 14th-century commentator on Averroes. For Aristotle it is 2 of 521, nothing. For Moses of Narbonne it is 2 of 11, spread over ten links: $(1 - 2/11)^{9} = 0.16$, below $\alpha = 0.2$, so the filter keeps the link, for his sake. Aristotle's own weight-2 ties, meanwhile, fail the test on his side (at $\alpha = 0.2$ a link needs more than 0.54% of his strength, a weight of 3 or more) and survive only when the other end needs them. The backbone contains important ties relative to each node, whether the node is big or small. Pretty great.

Disparity filter vs. thresholds. Compare $\alpha = 0.2$ with the $w \ge 3$ threshold: similar link counts (1,540 vs 1,572), but the disparity filter keeps 950 philosophers attached against 863. 112 philosophers (Moses of Narbonne among them) are attached by the filter and dropped by the threshold, and for every one of them the strongest tie is a 2: everything to them, nothing to the hub at the other end. Below $\alpha = 0.2$ the backbone comes apart: at $0.1$ the giant component is down to 419 philosophers, at $0.05$ to 116. There is no right $\alpha$; there is an $\alpha$ that you need to choose and the setting should depend on what you're trying to achieve. Be prepared to defend (or at least discuss) your choice.

Start at $\alpha = 0.20$: 1,540 links survive, 950 philosophers keep at least one, and the giant component holds 816 of them. Drag $\alpha$ down to $0.10$ and watch the giant component fall to 419 while the traditions pull apart. Then switch to Threshold at $w \ge 3$: a similar 1,572 links, but only 863 philosophers stay attached, and the tiles show what each filter threw away (at $\alpha = 0.2$ the strongest dropped tie has weight 6; at $w \ge 3$ a weight-2 tie between Aristotle and Isaac Newton is gone). Hover a faded philosopher to see which of their ties the filter took.

Some thoughts on network visualization. When you draw a network for your project (and for the rest of your life) I recommend you do it in this order ... and also make sure you document the steps in your report:

1. Find the backbone first. If your network needs filtering (not all networks do), always use a method you've thought about and a parameter you can defend. And say how many links and nodes were removed.
2. Then the layout. Create a layout of the backbone, not of the full network; the backbone is what makes e.g. a force layout work.
3. Color by community. If the network has meaningful community structure (you know how to test if it does), based on a method that is appropriate (notes on how to do that above), it can enhance the visualization to show communities. But I generally advise against running community detection on the network backbone (unless you have a good reason to do so). The backbone isn't data (it's intended for visualization), instead pick a method that works for the data you have. Consider grouping the positions, and/or labeling the groups, because one reader in twelve cannot tell your green from your orange.
4. Size by degree (or strength, or centrality), so what is important is visible without labels.
5. Consider labeling important nodes so the reader can get oriented in the network.

Goodies

Everything above is the course. Everything below is for the student who finished the page and wants more. Nothing here is on the test; all of it is worth your time.

← Back to the course overview