Clustering and
Community Formation/
Structure
Diego Pinheiro Silva
A. Vespignani. GLEAM: Global Epidemic and Mobility Model. [Link]
Network properties
What properties of networked system can we measure or model and
how are those properties related to the practical issues we care about?
Common properties in many
networks
small-world
properties
network transitivity
Is there anything
else?
power-law degree
distributions
community structure
What if this network represent:
students at university;
friendship at gym;
blogosphere;
coauthorships in a university
department.
tool for analysis and
understand of network
data
Newman, M. Networks. (Oxford University Press, 2010)
Community structure
!
Clusters, communities,
cohesive groups or
modules
pattern of edges
relatively weakly
interconnected modules
Newman, M. E. J. Detecting community structure in networks. Eur.
Phys. J. B - Condens. Matter 38, 321330 (2004).
Community structure
social network
real social grouping by interest
or background
citation network
related papers on a single topic
metabolic network
cycles or other functional
grouping
metabolic network
pages on related topics
Problem
variable
current value
spread of
diseases
variables on
the vertices
neighboring
vertices
parallel computer
minimize interprocessor communication
Cluster finding
specified
graph
partitioning
not specified
community
detection
number
and size
of the
groups
Cluster finding
find the best division of a network
graph
partitioning
regardless of whether
any good division
exists
community
detection
no need to divide if no
good exists
Graph partitioning
two nonoverlapping
groups
graph
bisection
given sizes
cut size is minimized
Newman, M. Networks. (Oxford University Press, 2010)
graph partitioning
exhaustive search
Number of ways
!
Roughly exponential
!
intractable computation when
n go much beyond 30
Newman, M. Networks. (Oxford University Press, 2010)
Kernighan-Lin Algorithm
Dividing into 2 groups of
required size
(i,j) interchange influence
find (i,j) with the largest cut
size reduction
swap (i,j)
choose the state with the
smallest cut size value
among all swapping
procedure
Newman, M. Networks. (Oxford University Press, 2010)
Community detection
natural divisions
Community
detection
many edges within
groups
few edges
between groups
Community Detection
minimum cut size
ratio cut partitioning
without group size
constraint
natural
divisions?
eliminates the
problem of all
vertices in the
same group
biases the
solution towards
roughly equally
sized groups
How to measure the quality
of a division?
is the cut size a good
measure?
edges between communities
few edges
fewer than
expected
number of edges
within groups
How to measure the quality
of a division?
number of edges
within groups
what about
assortative mixing?
Related to
number os such edges
expected in a basis of
chance
Assortative Mixing
Modularity
many more edges in a
network
fall between vertices of the
same type
than one would expect by
chance
high value
Simple Modularity
Maximization
Dividing into 2 equally
sized groups
vertex i interchange
influence according to
modularity
find i with the largest
modularity
move i
choose the state with the
highest modularity value
among all movements
Newman, M. Networks. (Oxford University Press, 2010)
Community Detection
addition
agglomerative
removal
divisive
Technique
Agglomerative
Calculate similarities
between vertex pairs
dendogram
Assign each vertex to a
group of its own
Join together the pairs of
groups with the highest
similarities
recalculate similarities
Newman, M. & Girvan, M. Finding and evaluating community
structure in networks. Phys. Rev. E 69, 026113 (2004).
Agglomerative
good at discovering the
strongly linked cores of
communities
tend to leave out
peripheral vertices
Newman, M. & Girvan, M. Finding and evaluating community structure in networks.
Phys. Rev. E 69, 026113 (2004).
Divisive
Start with network of interest
dendogram
Compute similarity between
all edges
remove the edge with the
lowest similarity
Recalculate similarities
Newman, M. & Girvan, M. Finding and evaluating community
structure in networks. Phys. Rev. E 69, 026113 (2004).
highest betweenness
Similarities
Pearson coefficients
Euclidean distance
Cosine similarity
flexibility
answers depending on
the measures
Cosine similarity
Common neighbors
!
Cosine of the angle
!
!
Dot product of two
rows
!
unweighted simple
graph
Cosine similarity
Varol, O., Ferrara, E., Ogan, C. L., Menczer, F., & Flammini, A. (2014). Evolution of online user behavior during a social upheaval. In
Proceedings of the 2014 ACM conference on Web science - WebSci 14 (pp. 8190). New York, New York, USA: ACM Press. doi:
10.1145/2615569.2615699
clusters matched geopolitical profiles
Gezi Park movement in Turkey
Borge-Holthoefer, J., Rivero, A., Garca, I., Cauh, E., Ferrer, A.,
Ferrer, D., Moreno, Y. (2011). Structural and dynamical patterns
on online social networks: the Spanish May 15th movement as a
case study. PloS One, 6(8), e23883. doi:10.1371/[Link].
0023883
social aspects
May 15th movement (15M) in Spain
Conclusions
References
I appreciate the opportunity. Thank you for
your time..
Diego Pinheiro
