Last set of comps readings, I talked about sense of community:

belonging, having influence, fulfillment of needs, and emotional

support. Now, let’s talk about the physics version of

“community” – cohesive subgroups. In a graph, these are

groups of nodes in a graph that are more connected to each other than

to other parts of the graph. Clumpy spots. If you read old Wasserman and

Faust, you’ll probably think of cliques, cores, and lambda

sets… some how these didn’t do it for me – literally, when I was

trying to locate

communities in science blog networks, it didn’t work..

If you have a computer science or maybe even sociology

background you’ll probably

just look at some sort of clustering (agglomerative or divisive).

The hot thing for the

past few years comes from physicists and that’s what’s covered here.

I did other posts on SNA

articles, so those are mostly

elsewhere. (BTW – if you ever take stats for the social sciences and

can substitute R for stata, do so and take the time to learn it. The

igraph package for R has all of the coolest community detection

thingies in it) (note, too, that these readings are not necessarily for

the dabbler in bibliometrics or social network analysis!)

Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating

community structure in networks. Physical Review E (Statistical,

Nonlinear, and Soft Matter Physics), 69(2), 26113-21.

(just go here)

This article, like the ones from Barabasi, sort of kicked off this

flurry of research. They use a divisive clustering technique

– so they start with the whole network, and break the connections with

the highest betweeness. See figure.

See how if you remove

that one line, how you completely break up the thing? That line has

high betweenness. So they calculate that for all of the lines using

whatever method, then take the line with the highest out, then

re-calculate and remove, and again. They then go on to talk about the

actual algorithm to use to efficiently do all of this betweenness

calculating and give some examples. There’s a lot in this

article, though, because they next talk about how to figure out when

you’re done and if you’ve got decent communities. This measure is

modularity (see the article for the definition), but basically it’s 0

if random and 1 is the maximum. If you calculate Q at each step, then

you can stop when it’s highest. Note that any given node can only be in

one community, unfortunately. (in real life, people are nearly always

in multiple communities)

Reichardt, J., & Bornholdt, S. (2006). When are networks truly

modular? Physica D, 224(1-2), 20-26. doi: 10.1016/j.physd.2006.09.009

(or look here)

They review Newman and Girvan and suggest a new way that groups

connected nodes and separates non-connected

nodes. They go through a process and end up

with an equation that’s apparently like a Hamiltonian

for a q-state Potts spin glass (dunno, ask a physicist if you need more

info on that!). This method allows for overlapping

communities because there could be times when you could move a node

from one community to the next without increasing the energy.

They compared it for some standard graphs and it did better

than N-G. Instead of just stopping by minimizing modularity, they

compare the modularity to a random graph with the same degree

distribution.

Reichardt, J., & Bornholdt, S. (2007). Clustering of sparse

data via network communities-a prototype study of a large online

market. Journal of Statistical Mechanics: Theory and

Experiment, P06016. doi:10.1088/1742-5468/2007/06/P06016

In this one they test the spin glass community detection method against

the German version of ebay to look for market segmentation. The network

has bidders as nodes, and if they bid on the same item there is an

edge. The spin glass method was successful at pulling out

clusters and using odds ratios, the authors showed that these clusters

corresponded to groupings of subject categories. The Q was much higher

than it would be for a random graph.