LISTSERV mailing list manager LISTSERV 16.0

Help for SOCNET Archives


SOCNET Archives

SOCNET Archives


SOCNET@LISTS.UFL.EDU


View:

Message:

[

First

|

Previous

|

Next

|

Last

]

By Topic:

[

First

|

Previous

|

Next

|

Last

]

By Author:

[

First

|

Previous

|

Next

|

Last

]

Font:

Monospaced Font

LISTSERV Archives

LISTSERV Archives

SOCNET Home

SOCNET Home

SOCNET  February 2012

SOCNET February 2012

Subject:

Re: Girvan-Newman's Q value in Netdraw

From:

"Bruggeman, J.P." <[log in to unmask]>

Reply-To:

Bruggeman, J.P.

Date:

Thu, 9 Feb 2012 12:11:57 +0000

Content-Type:

text/plain

Parts/Attachments:

Parts/Attachments

text/plain (136 lines)

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

The basic idea of modularity, Q, is that one compares an actual network to a network with the same degree distribution but otherwise random (Newman and Girvan 2004). Groups (or communities) should have higher densities than could be expected on the basis of random chance, and be separated by cleavages that are sparser than in the randomized network. When tie strength is taken into account, strongly connected nodes are more likely to be in the same group than weakly connected nodes, in line with Granovetter's (1973) well-known argument. Out of multiple possible assignments of nodes to groups that fulfill these requirements, the one with the maximal difference between actual and expected densities-maximal modularity-is arguably the best.

In larger networks where the number of groups is not known at the start (which includes most empirical networks) there are in fact so many different assignments that comparing all of them is not feasible. There exist numerous algorithms that search heuristically for a good solution in ways that are efficient and effective (for an overview, Fortunato 2010). As most of these algorithms randomly re-assign nodes to other groups in their search for modularity improvement, after each run of community detection a slightly different assignment might be found. Salient communities are robust, but the less salient communities are, and the more the network resembles a random network, the less stable the assignment will be. This is not (only) a limitation of the software, because for non-salient communities with overlaps, different assignments can have (almost) the same maximal modularity value. To detect group overlaps and smaller (sub)groups initially overlooked, a parameter can be fine-tuned, and thereby overcome to some extent the resolution limit inherent to this method, although several challenges remain (Kumpala et al 2007, Fortunato 2010; Traag et al. 2011).

Random graphs can sometimes exhibit surprisingly high modularity scores due to random fluctuations (Reichardt and Bornholdt 2007), contrary to claims one sometimes encounters that in a random network modularity would equal zero. This makes it difficult to compare modularity scores across different networks. It also implies that to establish significance, one would have to generate large numbers of simulated random networks with the same degree distribution, and compare them with a large number of community detection runs on the empirical network. This does not imply that the modularity approach is flawed, and in fact it has been validated in many test cases (Fortunato 2010), but when interpreting modularity results, one should take these considerations into account.

To study groups changing over time, an effective method was crafted by Mucha cum suis (2010), termed multi-slice modularity, where each slice represents a network for a single wave of observation. An advantage over earlier approaches is that its longitudinal modularity depends not only on the individual slices, like standard modularity discussed above, but also on the temporal stability of the communities.

To detect communities in signed graphs, Vincent Traag and I (2009, in Ph. Rev. E) started out from the assumption that negative ties are to be found in between contending groups rather than within them. To optimize modularity, densities of negative within-group ties are then to be minimized, while densities of positive ties are to be maximized, just as above. This conception generalizes social balance theory, by loosening up the latter's rigid community assignment wherein no negative ties were allowed to exist within communities. The underling theory we flesh out in our paper.

Several algorithms for community detection in graphs with positive ties are in the igraph package of R, like simulated annealing that works well for relatively small graphs. Another option is Louvain (Blondel et. al 2008), which is fast and accurate and can handle larger graphs, http://launchpad.net/Louvain/

I hope this helps,

Jeroen Bruggeman
University of Amsterdam


From: Social Networks Discussion Forum [mailto:[log in to unmask]] On Behalf Of Jesse Michael Fagan
Sent: donderdag 9 februari 2012 1:06
To: [log in to unmask]
Subject: Re: [SOCNET] Girvan-Newman's Q value in Netdraw

***** To join INSNA, visit http://www.insna.org ***** Hi Peyina,

The 'goodness of fit' is not a bad way to interpret Q.

You can fit any grouping of nodes to any network. You can arbitrarily assign nodes to an arbitrary number of groups. For any arbitrary grouping you can calculate a value of Q. Of course, as the size of a network increases attempting all possible combinations of groupings becomes intractable. So you have the Girvan-Newman method (and a great, huge host of other methods) which operate on good assumptions about network structure. The Girvan-Newman method assumes that edges in the network with high betweenness are edges tying communities together.

The Q (modularity) value is based on a null model of network connectivity.  In a random network you would expect the likelihood of two nodes   to be linked to be based on the degree of each of the nodes.

Pab = (degree(a) * degree(b)) / (2 * total edges in network)

Community detection algorithms, generally, attempt to find a way of grouping nodes together such that they are more likely to connect to other members of the group than would be expected based on this null model. Most community detection values attempt to find the highest value of Q possible (although a value greater than 0.7 would probably not be considered 'significant', but most algorithms won't approach that value). You would get a value of Q=0 if there was one community and all nodes belonged to it and a value of Q=1 if there were as many groups as there are nodes and there was a single node in each group. Both Q=0 and Q=1 are not significant. The best values for Q are between Q=0.3 and Q=0.8, but there could be considerable discussion concerning the 'best' values.

Check out Chris's recommendation. It will provide a good survey of methods and uses of modularity in networks. I hope this helps.

-Jesse Fagan


On Wed, Feb 8, 2012 at 4:26 PM, P. Lin <[log in to unmask]> wrote:
***** To join INSNA, visit http://www.insna.org *****
Hi,
 
I'm a PhD student at the University of Washington Information School studying high school social groups and the multiplexity of technology interactions.
 
I'm intrigued by the Q-value in Netdraw's Girvan-Newman subgroup function. According to Hanneman's online book on social network methods, this Q-value is a goodness of fit.
Does anyone know how to interpret the Q value (or goodness of fit) in Netdraw's Girvan-Newman subgroup function?
What is considered a good fit?
 
I got no responses on the UCINET group (posted 2 days ago), and emailed Dr. Hanneman, who kindly suggested I email this listserv.
 
To elaborate, Netdraw has an Analysis>Subgroup function that :
 
a) visualizes the subgroups partitioned by coloring the subgroups in different colors.
b) produces partition information, including a Q value.
 
I looked through the Girvan and Newman (2002) article cited for this algorithm, and couldn't see an explanation of the goodness of fit either.
 
UCINET does not produce this goodness of fit measurement either, which leads me to think that the goodness of fit is specific to Netdraw?
 
The Netdraw output makes sense to me (in the way I'm interpreting my data), and I'm just looking for a way to validate the clusters produced. So, perhaps the Q goodness of fit measure produced could help, though I need some help in knowing how that Q value is produced and what it means.
 
Thank you!
 
 
Peyina
-
Peyina Lin
PhD Candidate
The Information School
University of Washington
http://students.washington.edu/pl3
@peyinalin
 
_____________________________________________________________________ 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.

On Wed, Feb 8, 2012 at 4:44 PM, Weare, Christopher <[log in to unmask]> wrote:
***** To join INSNA, visit http://www.insna.org *****
This may have more information than you want, but this paper covers the modularity index very well.
 
Porter, M. A., J.-P. Onnela, et al. (2009). "Communities in Networks." Notices of the American Mathematical Society, Vol. 56, No. 9, 2009.
 
Chris
 
From: Social Networks Discussion Forum [mailto:[log in to unmask]] On Behalf Of P. Lin
Sent: Wednesday, February 08, 2012 3:26 PM
To: [log in to unmask]
Subject: [SOCNET] Girvan-Newman's Q value in Netdraw
 
***** To join INSNA, visit http://www.insna.org *****
Hi,
 
I'm a PhD student at the University of Washington Information School studying high school social groups and the multiplexity of technology interactions.
 
I'm intrigued by the Q-value in Netdraw's Girvan-Newman subgroup function. According to Hanneman's online book on social network methods, this Q-value is a goodness of fit.
Does anyone know how to interpret the Q value (or goodness of fit) in Netdraw's Girvan-Newman subgroup function?
What is considered a good fit?
 
I got no responses on the UCINET group (posted 2 days ago), and emailed Dr. Hanneman, who kindly suggested I email this listserv.
 
To elaborate, Netdraw has an Analysis>Subgroup function that :
 
a) visualizes the subgroups partitioned by coloring the subgroups in different colors.
b) produces partition information, including a Q value.
 
I looked through the Girvan and Newman (2002) article cited for this algorithm, and couldn't see an explanation of the goodness of fit either.
 
UCINET does not produce this goodness of fit measurement either, which leads me to think that the goodness of fit is specific to Netdraw?
 
The Netdraw output makes sense to me (in the way I'm interpreting my data), and I'm just looking for a way to validate the clusters produced. So, perhaps the Q goodness of fit measure produced could help, though I need some help in knowing how that Q value is produced and what it means.
 
Thank you!
 
 
Peyina
-
Peyina Lin
PhD Candidate
The Information School
University of Washington
http://students.washington.edu/pl3
@peyinalin
 
_____________________________________________________________________ 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.

_____________________________________________________________________ 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.

Top of Message | Previous Page | Permalink

Advanced Options


Options

Log In

Log In

Get Password

Get Password


Search Archives

Search Archives


Subscribe or Unsubscribe

Subscribe or Unsubscribe


Archives

November 2019
October 2019
September 2019
August 2019
July 2019
June 2019
May 2019
April 2019
March 2019
February 2019
January 2019
December 2018
November 2018
October 2018
September 2018
August 2018
July 2018
June 2018
May 2018
April 2018
March 2018
February 2018
January 2018
December 2017
November 2017
October 2017
September 2017
August 2017
July 2017
June 2017
May 2017
April 2017
March 2017
February 2017
January 2017
December 2016
November 2016
October 2016
September 2016
August 2016
July 2016
June 2016
May 2016
April 2016
March 2016
February 2016
January 2016
December 2015
November 2015
October 2015
September 2015
August 2015
July 2015
June 2015
May 2015
April 2015
March 2015
February 2015
January 2015
December 2014
November 2014
October 2014
September 2014
August 2014
July 2014
June 2014
May 2014
April 2014
March 2014
February 2014
January 2014
December 2013
November 2013
October 2013
September 2013
August 2013
July 2013
June 2013
May 2013
April 2013
March 2013
February 2013
January 2013
December 2012
November 2012
October 2012
September 2012
August 2012
July 2012
June 2012
May 2012
April 2012
March 2012
February 2012
January 2012
December 2011
November 2011
October 2011
September 2011
August 2011
July 2011
June 2011
May 2011
April 2011
March 2011
February 2011
January 2011
December 2010
November 2010
October 2010
September 2010
August 2010
July 2010
June 2010
May 2010
April 2010
March 2010
February 2010
January 2010
December 2009
November 2009
October 2009
September 2009
August 2009
July 2009
June 2009
May 2009
April 2009
March 2009
February 2009
January 2009
December 2008
November 2008
October 2008
September 2008
August 2008
July 2008, Week 62
July 2008
June 2008
May 2008
April 2008
March 2008
February 2008
January 2008
December 2007
November 2007
October 2007
September 2007
August 2007
July 2007
June 2007
May 2007
April 2007
March 2007
February 2007
January 2007
December 2006
November 2006
October 2006
September 2006
August 2006
July 2006
June 2006
May 2006
April 2006
March 2006
February 2006
January 2006
December 2005
November 2005
October 2005
September 2005
August 2005
July 2005
June 2005
May 2005
April 2005
March 2005
February 2005
January 2005
December 2004
November 2004
October 2004
September 2004
August 2004
July 2004
June 2004
May 2004
April 2004
March 2004
February 2004
January 2004
December 2003
November 2003
October 2003
September 2003
August 2003
July 2003
June 2003
May 2003
April 2003
March 2003
February 2003
January 2003
December 2002
November 2002
October 2002
September 2002
August 2002
July 2002
June 2002
May 2002
April 2002
March 2002
February 2002
January 2002
December 2001
November 2001
October 2001
September 2001
August 2001
July 2001
June 2001
May 2001

ATOM RSS1 RSS2



LISTS.UFL.EDU

CataList Email List Search Powered by the LISTSERV Email List Manager