0
$\begingroup$

I want to filter out networks/graphs which are just a single community rather than interconnected communities. Each community can either be a random graph or a star graph, but there should no community structure. The definition is loose considering that these data sets can have multiple communities with a varying number of edges connecting them together or nodes acting as bridging islands. (these networks are connected)

I thought of looking for networks where the average path length for at least 10% of the nodes is greater than 2.

I am using `MATLAB' and any reference to useful libraries would be appreciated.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ A side note: the igraph package in R has a lot of graph measures for community analysis... $\endgroup$ – Deer Hunter Mar 21 '13 at 19:38
2
$\begingroup$

There are lots of ways to approach this. Since you didn't provide many details, I would recommend looking at lots of different notions of what a "community" is and then finding the one that you think suits your needs best. Here are some ideas and references that might help:

Here's an overview of several methods: http://en.wikipedia.org/wiki/Community_structure.

Do a spectral clustering on the graph laplacian.

Use the adjacency matrix as a similarity matrix (a counterpart to a distance matrix) and then do a standard clustering method on that similarity matrix.

If you decide to use R, then I'd recommend the package statnet. I don't use Matlab for network analysis, so I don't have package recommendations for that.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have tried spectral clustering and it breaks down on large matrices, and the worst part is that in star graphs the nodes of the center come out on the ends of the spectrum. $\endgroup$ – Vass Mar 22 '13 at 14:16
  • $\begingroup$ I tried the methods of Ding et al published at KDD and they need a computer with superior memory capabilities to that of a normal laptop for networks with thousands of nodes. $\endgroup$ – Vass Mar 26 '13 at 12:00
0
$\begingroup$

The best and easiest to understand statistical measure for when there are communities present in a network is the Q statistic in the method of "Modularity and community structure in networks" Newman 2006. It looks at a community structure's connectivity and compares the probability for such a connection structure to have arisen randomly. Low values indicate a deviation from this random case.

In my datasets this Q value distinguishes quite well between the networks with and without community structure.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.