Finding largest cliques (completely connected sub-graph components) is hard. The best algorithms have run times proportional to 3^(#nodes/3). Triple the nodes = nine times the run length. So what’s a guy without a supercomputer to do but start looking for shortcuts?

Shortcut 1: Maximize for your goals

My interest is in characterizing a network, in part, through largest clique size. Since the interest is in size, not quantity, I can start looking for cliques of size N+1 as soon as I find one of size N.

Shortcut 2: Estimate

I’m interested in specific types of networks, social networks. And we can tune for that through size estimation.

The networks I’ve run through my clique analysis are public (mailing lists, twitter feeds, etc) and generally demonstrate maximum clique size relative to number of active participants and independent of the time observed. I’ve looked at networks sampled for a week to complete observations of 10+ years of conversations.

I have only found once case where the maximum clique size was smaller than ln(# nodes)/2 for these directed networks. When artificially forcing them to undirected networks, the maximum clique size is around double.

Shortcut 3: Cleanse the Data

Now that I have estimated size, every node with fewer edges can be ignored. With that amounting to around (1-1/n)%, for n less than the estimated size, we can cut down the search space.

Shortcut 4: Order your Data

With looking for the largest clique, the more links a node has, the more likely it’s a member of that clique.  So, when you are selecting which nodes to start with, start with the ones with most links.  The sooner you locate larger cliques, the sooner you can stop looking for smaller ones.

Results

Here’s where the “laptop test” comes in: using just a subset of the above, I was able to locate 9-member cliques in an undirected 2,000-node 5,500-edge network in under 5 seconds.  By comparison, on the same machine, it took 5 minutes to locate them using the igraph library in R.

R’s igraph, sadly, ignores edge direction in locating cliques.  But, a run of the above using my code with edge direction completed in about 0.5 seconds.

As an example for larger graphs, I located 15-member cliques in an undirected 75,000-node 220,000-edge network in 20 hours.  R topped out in memory before reaching this size network, and was unable to complete.

Update: It’s been pointed out to me that this has scaled pretty close to n^3.

How I Stopped Worrying About Network Visualization (PDF)

About a year ago, we comparatively visualized conversations between two competitive brands of major sport apparel companies.  The network of communications of Brand A showed better potential characteristics for healthy and robust interaction.

One year later, and more than 1,000,000 people talking about each brand, what do we see?

Brand A (one year later)

Brand A

Several million conversations later, we still see a deeply interconnected pattern of communication in Brand A.  The large number of clusters are still visible, but the interconnections are less clearly visible.  Let’s compare with Brand B:

Brand B

Brand B (one year later)

Brand B began with fewer, more centralized, clusters of conversation, and less “cross talk” between them.

Again, several million conversations later, it has evolved to a larger version of what we saw before.  While there are more distinct clusters one year later in Brand B than Brand A, each of those clusters receives less input from others.  Visually, we see this distinction by the are of fewer “clear” clusters toward center of the later graph of Brand A. In other words, should something great happen, the network of communications in Brand A would foster faster and more reinforcing communication.  If you’re a marketer, that’s what you want.

So, what’s the difference in stock performance over the past year?  Brand A outperformed B by about 30%.

Cleaned up the data a little, and created a new visualization to better demonstrate the split between the two connected clusters.  The center of the smaller one is a Gov Palin email address that has the “Gov Sponsored” qualifier.

It looks like this email address was used for her constituents to get in touch with her.

[huge semi-readable image, by request for @kev97. Regular big here.]

Gov Palin's Email Network (click for larger version)

Lots of cleanup left to do in the code parsing/cleaning up the emails, but here’s a first pass.  Seems like at least two connected networks, and surprisingly both the yahoo and the Gov’t email addresses are both in the larger one.  I wonder what the smaller one comprises of?

A very big thanks to the folks over at Sunlight Foundation for the data.

2.5 million tweeters having 11 million conversations.  Pay attention to the clustering.

Song: Dance on Vaseline (Thievery Corporation Remix) by David Byrne

(YouTube link here)

Over a long enough period of time, maps of who is talking with whom mostly look the same.  Many conversations start to overlap with each other, and eventually you see a large central core and any number of outliers.

However if you look over short enough periods, you can see patterns of how those conversations start to merge.  And, you can tell a lot.  Easily.

Brand A

Brand B

Here we have a mapping of conversation partners mentioning two of the top sports apparel manufacturers, measured over the same period. Compare the shapes of Brand A (on left) to Brand B.

Brand B (on right) has a few larger clusters of conversation, lightly linked together by a few individuals participating in a number of the conversations.

Brand A has a lot of smaller conversations, interspersed with a handful of larger dense clusters; all webbed together in wide mesh.

So which is better?

Well, better for what?  That’s the $64,000 question in social analytics.  You need a goal, but hopefully that’s why you started looking for metrics in the first place.  Right?

That’s not necessarily true.  There’s a lot already baked into the question.  These two brands and their products are in direct competition.

Brand A has a much stronger network of communication, in both breadth and quantity of conversation clusters.  There are also a large number of small, non-connected conversations in the blue fringes that may be pulled into the core over time.  That means there’s more to keep track of, but likely a stable set of opinions.  Opinions will not likely change without introducing something substantively new, as information flows between the clusters fairly freely. This network displays characteristics of healthy and robust interaction.

Brand B, even excepting a significantly smaller quantity of conversation clusters, is heavily based on a few conversation clusters connected through a small number of individuals.  This indicates a fragility and possibly wider variance in opinion within the overall set of conversations.  In this structure, information will flow between clusters more slowly.  The second element Brand B is missing is depth of field in potential new recruits.  Brand A has quite a few blue conversations in the periphery with potential to join the core.  Brand B has very few.  I’d rather not be representing Brand B.

The two clusters in the core are roughly split into Democrats (l) and Republicans (r).

Chicago Olympics Bid

Built from data by LittleSis.org.  As always, click for larger image.

3.6-times as many former congressional staffers turned health care lobbyists and their immediate connections have network ties closer to former President Bush, than to current President Obama.

The connections in the network map shown below, and used for the analysis above, include people and organizations (e.g. corporate, not-for-profit, public, etc.) the people have been identified with.

Other trivia:

• 53% have equidistant path lengths between both Obama and Bush
• All are 0.45 links closer to Bush, on average
• Minimum distance of 6 in distance to Obama + to Bush
• Maximum difference of 4 in path lengths to Obama compared with to Bush

Expanding on the earlier network visualization of these new health care lobbyists, I have updated the network graph to the 500 identified by LittleSis.org.

The two easily identified clusters are close to Obama (lower left) and Bush (upper right).  Red dots are former staffers from the LittleSis.org list, and hollow dots are their other relationships.

And, not surprisingly the relationship distribution follows a power-law.  Or, as indicated in this log-scale histogram, a Poisson distribution.

]]> http://www.howweknowus.com/2009/09/22/health-care-leans-republican/feed/ 2 http://www.howweknowus.com/2009/09/22/health-care-leans-republican/ http://feedproxy.google.com/~r/hwku/~3/XbzVZLkQZtQ/ http://www.howweknowus.com/2009/09/08/mathematicians-do-it-randomly/#comments Tue, 08 Sep 2009 18:52:03 +0000 erich http://www.howweknowus.com/?p=660

What it look like if you took all of the Mathematics articles from JSTOR, the digital journal archive, and mapped co-authorship of the papers? It would look something like this.  Interesting to note, that while the distribution does hold to the small world network distribution exponent, there’s some “peakiness” about it that may suggest it’s not really one network, but the merging of several.  Given the role of mathematics on so many other subjects, that would not be a surprise.

Largest cluster of co-authorship

Zoomable image with names, after the jump.

[typo in JSTOR name fixed 2010-09-30]