Communities can be found in many types of networks. They show up in social networks (cliques, common interests, "old boy" networks), biological networks (functional groupings in metabolic networks1), and even academic structures like research citations.
Communities are simply groups of elements in a network where members are more likely to interact with each other than with elements outside the group. In some networks, communities are easy to spot visually. For others, you need complex calculations to help tease out the community lines.
Today we're announcing a powerful community detection framework we've built into Kumu, based on the SLPA algorithm. Communities are identified based on communication flows and, unlike older algorithms (such as the Louvain method used by Gephi), the algorithm can detect overlapping communities. (Which is awesome since community membership is rarely black and white!)
If you're interested in the specifics of the algorithm, see the "SLPA details" section at the bottom of the post. For everyone else, let's dive into the basic steps of community detection within Kumu:
1. Detect communities
You'll see a new icon in the bottom toolbar that looks like a building. Click this to open the community detection window.
If you haven't run community detection before, clicking this will automatically detect communities. If you're already run community detection, clicking the icon will bring you to a window showing you the previous results.
2. Review members
After running the algorithm, we present the results to you in a table that allows you to browse each of the communities, ordered by popularity (defined as the size of the community).
Within each community, elements are listed in order of their strength of association to that community. Think of this value as the probability of that element belonging to the given community. Elements in grey are ones that had ties to the community but ultimately had stronger ties somewhere else.
When analyzing the communities, you may notice that a common theme runs across all members of that community. Maybe they all went to the same graduate school, or worked at the same law firm (maybe they even went to the same high school). If you notice a theme like this, we provide an easy way to override the community name and replace it with a descriptive one.
Don't forget to click save once you're done!
Note: Some community detection algorithms treat communities as black and white. You're either in or you're out. While this helps simplify the analysis (and admittedly makes it much easier to color by community), it throws away a lot of useful information about the overlapping community structures within the network. The SLPA algorithm preserves this data, and we believe the breakdown is even more valuable than simply knowing the primary community an element belongs to.
3. Color by communities
First, make sure to save the community results. This will save the best match for each element to the "Community" attribute so you can use the community values to decorate your maps.
Eventually we'll build a UI to make the process of coloring by communities even easier, but for now you just need to add these lines to your advanced perspective:
@settings {
element-color: categorize("community", spectral);
}
Wondering what "spectral" means? With the release of community detection, Kumu now also has built in support for a number of color scales (including all the colorbrewer scales -- mouse over for the name). Here's a few custom ones for you to try:
- olympic
- neon
- heat
- stoplight
Bonus Tip: Try replacing "community" with "element type" for a quick and easy way to color by each element type!
4. Rerun from scratch (optional)
When you rerun community detection, we'll use the existing communities to seed the algorithm by default. This keeps the communities more stable, but occasionally you may want to throw away the previous communities and start fresh. For instance, if you've made a number of changes to the map the previous communities will unfairly dominate the new network. Just click "throw away the current communities" and we'll dump the existing communities and rerun the algorithm from scratch.
Remember, not all networks have meaningful community structure. Use the default settings and try to avoid fiddling too much just to get a pretty picture.
The science of community detection is still evolving. Use the results from the algorithm to ask better questions about your maps but don't take them as fact.
SLPA details
For those who just can't help themselves, here's the gist of how the algorithm works:
By default each element starts off as its own community. For each element (the "listener"), the neighbor elements (the "speakers") suggest a community for the listener to join based on the communities they've heard so far. The listener then selects the community spoken the most times by its neighbors.
This process is repeated multiple times (100 rounds by default). Once complete, each element's association to a community is simply the number of rounds it selected that community divided by the total number of rounds. This gives us values between 100% (only community it selected) and 0% (never selected it).
For even more details and an overview of other community detection algorithms, take a look at this paper: http://arxiv.org/pdf/1110.5813.pdf