1 of 20

Community Detection in R at SNH 2023�Peter J. Mucha, Dartmouth College

Partitions

CHAMP

Fixed Points

Map Parameters

2 of 20

Facebook�Traud et al., “Comparing community structure to characteristics in �online collegiate social networks” (2011)�Traud et al., “Social structure of Facebook networks” (2012)

Caltech 2005:�Colors indicate residential “House” affiliations�Purple = Not provided

3 of 20

Facebook�Traud et al., “Comparing community structure to characteristics in �online collegiate social networks” (2011)�Traud et al., “Social structure of Facebook networks” (2012)

Caltech 2005:�Colors indicate residential “House” affiliations

Community detection gives us unsupervised clustering tools to identify patterns directly from the network connectivity.

This visualization is the same data, pre-processed using only the Facebook Friend connections—not the House information—to place each node into a community, that is, a group of nodes that are more connected to each other than to the rest of the network. We visualize each community here by a pie chart, scaling the areas of the wedges proportional to the number of users with that House label.

The clear takeaway is that, indeed, the House structure is exceptionally well aligned with the identified communities.

The vast majority of the yellow users are in this community in the center. Most of the darker orange is in the community to the right.

The cyan and red colors splitting this community represent two Houses next door to each other on an end of campus with strong social overlap.

The only color broadly distributed color with seemingly little pattern here is purple…

4 of 20

Facebook�Traud et al., “Comparing community structure to characteristics in �online collegiate social networks” (2011)�Traud et al., “Social structure of Facebook networks” (2012)

Caltech 2005:�Colors indicate residential “House” affiliations�Purple = Not provided

5 of 20

Takeaway Messages

CommunitiesSNH2023.Rmd file designed to�highlight upcoming IDEANet capabilities
Community detection is “just” unsupervised �clustering of nodes in the network:

NFL: No single “right” way to cluster�(different tools, knobs)
“Meaning” of identified groups�depends on your application

CHAMP and Iterative Parameter Maps in R:

Multilayer modularity capabilities�“coming soon”�github.com/wweir827/CHAMP�github.com/ragibson/ModularityPruning

Partitions

CHAMP

Fixed Points

Map Parameters

6 of 20

This is the typical user:

To be clear, there’s no single one right answer here — Indeed, Leto Peel et al. 2017 have a No Free Lunch Theorem for community detection.

And while a single call at default resolution might work fine most of the time for the karate club, this was the Kolaczyk “If your method doesn’t work on this, go home” case.

And yet it's what most users in an application domain are going to do, and I don't blame them for that, they're smart people with their own disciplinary expertise and problems to solve and they're trying to use a tool to study their data.

So surely we can provide simple tools that promote better behavior in practice for most of these users.

--

To that end, both tools we’re going to talk about in the time remaining today are available in python both on GitHub and via pip install.

--

There might not be one single right way to do community detection, but we can almost always do better than just this.

7 of 20

Network Scientists with Karate Trophies �http://networkkarate.tumblr.com/

8 of 20

Zachary Karate Club

This partition optimizes modularity (at default resolution) which measures �the number of intra-community ties (relative to a random model)

“If your method doesn’t work on this network, then go home.”

Any story introducing community detection is seemingly obligated to at least mention the Zachary Karate Club.

Zachary was a social scientist surveying the friendship network in a university karate club when the best possible thing happened to him: the club got in a fight.

This wasn’t just regular sparring but a disagreement between the club’s president and lead instructor and they broke up into two rival clubs.

If you put yourself in this situation, unless you have a strong opinion about the content of the disagreement, which new club would you join?

Most people tend to go with the club where their friends go.

Sure enough, if you cluster this network through almost any community detection network, it breaks nicely along a cut down the middle here that is well aligned light-to-dark with the two new clubs.

Indeed, the split here is so strong that at one conference where this example came up in talk after talk, Eric Kolaczyk from BU who co-organized the workshop finally exclaimed “If your method doesn’t work on this network, then go home.”

9 of 20

Modularity is problematic

Modularity maximization remains most used method of community detection

Frequently misused

Heuristics 🡪 Stochastic
Pick resolution γ & coupling ω

If you’re going to use modularity, �we want to help you use it right

As much as modularity at default settings worked well on the previous examples, we need to acknowledge that modularity is problematic.

It’s a descriptive measure but it wasn’t developed to be statistically principled in a generative sense, it only finds assortative structures, and it’s biased towards balanced communities,

That said, it remains the most used method of community detection in practical applications because there are many fast heuristics that are easily accessible across different computational environments.

It is also frequently MISUSED, because these fast heuristics introduce pseudo-randomness in quickly finding good solutions to an NP-Hard problem

and because these packages typically do not make clear or provide much guidance about picking the resolution and coupling parameters.

Indeed, in some common computational environments it is relatively difficult or outright impossible for users to modify the resolution parameter, and they don't even know they're misusing it.

Our philosophy is that if modularity is going to continue to be widely used, we want to help people use it right.

10 of 20

Modularity with resolution parameter γ�(Newman & Girvan, 2004; Reichardt & Bornholdt, 2006)

Indicator on nodes i & j in

same community

Adjacency data:

Edge/weight from i to j

“Null model” expected edge weight,�typically product of node degrees (undirected): k_ik_j/(2m)

Optimization: Find partition σ of nodes in communities to maximize Q�Resolution parameter γ indirectly controls number/sizes of communities

“Modularity matrix”

Modularity is a descriptive objective function that measures the within-community edge weight of a partition of nodes into communities relative to what you would expect in an appropriate random graph model.

Here the modularity or “quality” Q depends on your data in the form of adjacency matrix,

and a null model of expected edge weights, typically obtained through a product of node degrees in the undirected case

where k_i and k_j here indicate the degrees or in a weighted network the strengths of nodes i and j, and m is the total edge weight in the network.

Together this combination is referred to as the modularity matrix and the sum over a subset of its elements is controlled by an indicator for whether nodes i and j are together in the same community c in the partition sigma.

That is, this becomes the sum over all node pairs in the same community

The optimization problem is then to pick the partition sigma to maximize Q. While this is NP-Hard, it turns out there are many reasonable computational heuristics.

The resolution parameter gamma was added to modularity to control the number and sizes of communities.

Larger gamma increases the penalty paid for putting two nodes in the same community, thus tending to move the maximum Q to partitions of larger numbers of smaller communities.

--

If you are familiar with different machine learning methods of unsupervised clustering, modularity is perhaps qualitatively similar to something like k-means in terms of being an optimization-driven method,

But of course just like with other unsupervised clustering settings, there are many other methods, some of which fit a model to the data, that we are ignoring for now.

11 of 20

Convex Hull of Admissible Modularity Partitions

github.com/wweir827/champ

12 of 20

How to pick γ? (1) CHAMP

50,000 Louvain calls

384 unique partitions

13 of 20

Q_σ(γ) isn’t a point. Each partition σ defines a line.

50,000 Louvain calls

384 unique partitions

19 admissible partitions

That is, each of these 384 partitions defines a different line, so maximizing Q at each gamma is the half-space intersection problem of finding the line segments that comprise the upper envelope of Q versus gamma.

We then find that only 19 of these partitions are admissible in the sense that their lines are anywhere on the upper envelope,

And by showing the intersections of lines on the upper envelope by triangles we see that two of these lines have longer segments on the upper envelope.

With our attention then focused on those two partitions, we find the one has 12 communities and the other has 13, and if query the community labels

closely under the hood, it turns out that this 13-community partition is simply splitting one of the 12 communities into two parts (corresponding to splitting a conference into its divisions).

14 of 20

Q_σ(γ) isn’t a point. Each partition σ defines a line.

50,000 Louvain calls

384 unique partitions

19 admissible partitions

That is, each of these 384 partitions defines a different line, so maximizing Q at each gamma is the half-space intersection problem of finding the line segments that comprise the upper envelope of Q versus gamma.

We then find that only 19 of these partitions are admissible in the sense that their lines are anywhere on the upper envelope,

And by showing the intersections of lines on the upper envelope by triangles we see that two of these lines have longer segments on the upper envelope.

With our attention then focused on those two partitions, we find the one has 12 communities and the other has 13, and if query the community labels

closely under the hood, it turns out that this 13-community partition is simply splitting one of the 12 communities into two parts (corresponding to splitting a conference into its divisions).

15 of 20

Modularity-SBM Equivalence (Newman, 2016)

K

Degree-corrected “planted partition” SBM with K blocks, ,

Newman showed that if you took the log-likelihood of a degree-corrected planted partition of K blocks with a pair of propensity parameters for in-block and out-of-block edges and rewrote it in the right way,

it looks like modularity with a gamma defined by this combination of the theta propensities.

Newman then proposed an iterative procedure to find a partition that maximizes modularity at the gamma that self-consistently matches the theta values empirically estimated from the same partition.

An important wrinkle we will see is that Newman proposed to hold the number of communities K to be fixed, consistent with the norms of stochastic block modeling and assume that K was provided a priori or might be obtained in some other way.

In Newman’s table of example results, of most interest for our remaining narrative here will be the K=2 result for the Karate club yielding a gamma = 0.78.

16 of 20

Fixing v. Varying K for �Zachary’s Karate Club

Fixing K=2

Varying K

The Newman and Pamfil et al papers are both AWESOME and I highly recommend them, but I think there's still an interesting wrinkle in here, we can see even on Zachary’s Karate Club.

In Newman’s version of the procedure, fixing K=2, it is in most cases a single iterative step from a 2-community partition at an initial gamma giving empirical estimates that yield gamma=0.78 and the 2-community partition found there.

But under Pamfil et al.’s proposed iterations allowing K to vary, we see much less consistency in the outcomes.

If you start at small gamma giving two communities, it jumps to gamma=0.78 and sometimes it stops there finding a 2-community partition.

But there is actually a 3-community partition with higher Q there, and if the heuristic finds it then the empirical estimates on that partition point to a gamma near 0.9.

Again, sometimes it stops there, but there’s a 4-community partition that goes to higher gamma.

The blue markers here indicate the varied final values of gamma that result from this iterative procedure allowing K to vary.

17 of 20