Print

Print


***** To join INSNA, visit http://www.insna.org *****
Dear Steve,

1. Community Discovery

In my knowledge, Newman-Girvan algorithm is a little outdated:
there are more recent algorithms which directly optimizes the modularity function,
instead of indirectly relying on link betweenness measures.

It has been known that the maximization of modularity function is NP-hard:
so every realistic algorithm relies on heuristic ideas.
Among many algorithms, CNM - Clauset, Newman, Moore - algorithm is the most famous one that people frequently use,
mainly because it is relatively scalable among community algorithms.  ( http://arxiv.org/abs/cond-mat/0408187 )
Due to the popularity of CNM algorithm, there are many variants.
In my experience, they're all heuristic, so the result highly depends on the characteristic of your data.
However, I suppose that your data is not very big (because you could apply Newman-Girvan algorithm),
and in that case, algorithms with simulated annealing work better than Newman-Girvan or CNM-type algorithms
because the latter algorithms are so greedy that they don't look back after they make a decision.

Newman's 2007 paper is a good summary and provides insightful messages, with some suggestions of new algorithms,
which are not yet realistic for application to larger networks, but in the case of small networks, they work.
( http://arxiv.org/abs/physics/0605087 )
For simulated-annealing approach, look at the references on the paper above,
and look at the papers published by Jorg Reichardt (sorry for having no link provided).

NetMiner  ( htp://www.netminer.com )  has a pretty good functionality on community identification.
If your network is not very big, try the evaluation version.


2. Cohesivness of each community

How about calculating clustering coefficient for each community?
This measure may not be introduced in Wasserman-Faust book, but it is pretty popular and frequently used - 
certainly more comparable than density measures. Or you may use mean average path length,
but sorry, I'm not an expert in this area. I just wanted to give you some suggestion.


Thanks,
Hyokun Yun
Ph.D Candidate,
Purdue Statistics


On Thu, Dec 31, 2009 at 6:48 PM, Steve Eichert <[log in to unmask]> wrote:
***** To join INSNA, visit http://www.insna.org ***** Hello,

I've been using the Newman Girvan algorithm [1] to identify communities within networks of individuals, however, I've been told by someone who I respect greatly that Newman Girvan isn't the best algorithm to use for identifying communities when dealing with human networks.  So, the question I have for the group is: what algorithm would you recommend for identifying communities when working with networks of people.  

[1] http://en.wikipedia.org/wiki/Girvan–Newman_algorithm

All the best,
Steve
_____________________________________________________________________ SOCNET is a service of INSNA, the professional association for social network researchers (http://www.insna.org). To unsubscribe, send an email message to [log in to unmask] containing the line UNSUBSCRIBE SOCNET in the body of the message.

_____________________________________________________________________ SOCNET is a service of INSNA, the professional association for social network researchers (http://www.insna.org). To unsubscribe, send an email message to [log in to unmask] containing the line UNSUBSCRIBE SOCNET in the body of the message.