Nov 4, 2013

Making Sense of Emergent Patterns in Networks

One of the most used functions of social network analysis software is to discover and display clusters and communities in networks -- the dense sub-networks, where there are more links internally, than externally.

It is easy for the common person to spot dense clusters of connection in a network visualization.  Yet, this is a difficult problem for algorithms.  Early cluster discovery and community detection algorithms took the easy way -- they forced every node into one, and only one cluster, because the math was easier.  It was like the college physics course I took where all of the problems we did were in a vacuum and there was no friction to be accounted for.  This taught the basic principles, but did not carry over into real life.

Sociologists where not happy with the early community detection algorithms because they did not reflect how humans naturally cluster, connect and group themselves.  We are members of many clusters, and through that multiple/partial membership in many groups, we cause those clusters to overlap -- groups are not distinct with just unique members in each.  Group boundaries and porous and fuzzy.

Today there are dozens of community detection algorithms, many allow for overlap, and multiple cluster membership.  Community detection is still a hard problem.  Smart network scientists don't always agree on what is in each community, as we shall see.

Figure 1 is a diagram of simple network of 16 people modeled in InFlow software.  Symmetric (non-directional) connections are shown by the green links in the diagram.  This first network layout is just a circle with nodes in numerical order clockwise.

Figure 1

We first apply the simple community algorithm which puts everyone in a single group only -- often resulting in some funny groupings.  The algorithm finds us 4 unique groups/clusters, and at first glance produces a nice picture.

Figure 2

Upon further inspection we see nodes 1 and 4 have more connections outside of their assigned cluster than inside -- why were they forced into that group?  They look like good candidates for membership in multiple groups.

Next we allow for cluster/group overlap -- multiple memberships -- and we are surprised.  There is more than one answer!  In complex systems, such as human groups, communities and organizations, there is usually no one right answer, or one best way of doing things -- there are often several good answers. It might be impossible to choose the best answer ahead of time! The next set of diagrams (Figure 3-5) all show reasonable clusterings found in the data above. They all show 4 clusters, each cluster enclosed in a gold frame.  If a node shows up inside more than one frame, it is a member of more than one cluster.

Figure 3

Figure 4

Figure 5

Next we run another algorithm and find not 4 clusters, but 3 emergent communities. 

Figure 6

Yet another algorithm gives us just two overlapping emergent groups.

Figure 7

Which of those above do you like?  Which do you think best represents the natural groupings in this toy network?

My favorite patterns are next.  There is no rule that says all nodes have to be assigned to at least one cluster!  Some play a role of connector, or between many nodes in the shortest paths that connect them -- they have high betweenness -- maybe they are liaison between many groups without belonging to any one of them?  One of the settings on the cluster analysis algorithm in InFlow, assigned all nodes to a group except for node 4 -- s/he is a connector of groups, but not a member of groups.

Figure 8

Adjusting the cluster algorithm a little more now get two nodes -- 4 and 5 -- that are not members of any cluster.  They are the connectors in this emergent network.  My favorite rendering of this emergent network is in Figure 9 below. 
Figure 9

One of the properties of human relationships is that they are messy, inexact, and complex.  We should not expect to find one perfect way to group or cluster a network of human relationships.  If we do find such a perfect solution, maybe we have over-simplified the problem, like in Figure 1?

One thing we see in the various clusters above is that nodes 1, 4, and 5 are often the linch-pins that hold two or more clusters together (the clusters overlap around these nodes).  If we run various network centrality metrics on this network, we consistently find nodes 1, 4, and 5 at the top of the list, no matter which metric we choose -- 4 being at the very top, most of the time.

Finding logical and plausible clusters in complex systems is not a simple task -- there is no one simple answer.  This is not like accounting, where everything should add up correctly every time, and you do get one right answer. Finding clusters in networks is often about sense-making, what are the logical patterns we see and what might they tell us?  In our human relationships, we always want "neat and clean", but we always get "messy and fuzzy."  The right software will help you through the messy, and help you make sense of it -- it will not provide simple answers.

What patterns do you see?


Joitske Hulsebosch said...

Thank, very useful! What do you consider the best algorithm for finding overlapping communities? (in SNA software terms)

dustproduction said...

If we substitute neuronal networks in the brain would the communities represent characteristics of personality, which might also be fluid?

dustproduction said...

There is no "best" since defining community is contextual and can vary.

dustproduction said...

If we substitute neural networks in the brain do the communities become representative of characteristics of personality?

Valdis Krebs said...

Obviously many usable cluster algorithms... no all-purpose one!

Communities in brain neural networks? There are people studying this... under the general heading of "Connectome". Should be exciting!

Rense Corten said...

I guess this nice exercise highlights the need for a more 'deductive' approach to community analysis: derive hypotheses from a substantive theory on what type of community structure we'd expect, and only then do the analysis. If you don't know what you're looking for it is indeed hard to find anything.