Page 335 - Becoming Metric Wise

327
Networks

not a good indicator of the quality of the division since placing all vertices
in a single community would give the value one while giving no informa-
tion about community structure at all. For this reason, Newman and
X
Girvan proceed as follows. Let a i 5 e ij ; this number represents the frac-
j
tion of edges that connect to vertices in community i. In a network in
which edges connect vertices without taking community structure into
account one would have the independence relation: e ij 5 a i a j . This leads to
the notion of modularity Q, as defined by Newman and Girvan (2004),
Q 5 X e ii 2 a 2 (10.11)
i
i
Modularity Q measures the fraction of the edges in the network that
connect vertices of the same type i.e., within-community edges, minus
the expected value of the same quantity in a network with the same com-
munity divisions but random connections between the vertices. If the
number of within-community edges is no better than random, we have
Q 5 0. Modularity values lie in the range [21/2,1). They are positive if
the number of edges within groups exceeds the number expected on the
basis of chance. The higher the modularity value the stronger the com-
munity structure.
Algorithms to find the best division in communities try to maximize
the modularity value. Although Newman and Girvan (2004) propose
such an algorithm the most widely used method today for detecting com-
munities in large networks is the Louvain method (Blondel et al., 2008).
This is a simple, efficient and easy-to-implement method for identifying
communities in large networks. It has been used with success for net-
works of many different types and for sizes up to 100 million nodes and
billions of links. The Louvain method unveils hierarchies of communities
and allows zooming in within communities to discover subcommunities.
Once communities have been determined it makes sense to apply the
gefura measure and determine the bridging roles of nodes in the
network.
We finally mention the term homophilous networks (McPherson et al.,
2001). Networks are homophilous if people, or generally actors, sharing
similar characteristics establish more edges between them than with
others. This means that they tend to lead to well-defined communities. In
this context one uses the saying, “Birds of a feather flock together.” (see
e.g., Kretschmer, 2002).