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.