## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

Chapter 11
Social Networks
11.1 Introduction
Social networks consist of persons or groups of people which have some kind of
relationship. A social network can be modeled by a graph where a vertex represents a
person or a group and an edge between two vertices indicates an interaction between
these two entities. We have already discussed the small-world property observed in
many social networks in which the nodes of the network can access other nodes using
We will now take a closer look at the internal structures of social networks and
investigate their properties that are radically different from those of other complex
networks. As a ﬁrst attempt, we will try to label the relationship between people as
positive and negative and will search to assess global stability criteria for the so-
cial networks based on the stability of local relationships. The notion of equivalence
is another property which is not found in other types of complex networks and we
describe this in Section 11.3. Clustering, now called community detection in social
networks, provides us with useful information about the structure of the network and
is again a fundamental area of research in these networks. We describe four algo-
rithms in chronological order that may be used for community detection in social
networks. The ﬁrst algorithms uses edge betweenness of vertices to divide the net-
work into clusters. The second algorithm uses the resistor model of the network and
the third similar algorithm is based on random walks in the network. The last algo-
rithm uses a new measure called modularity to perform clustering and validates this
parameter while performing clustering.
227
228
Complex Networks: An Algorithmic Perspective
C
C
t1
t
2
A
B
A
B
11.2 Relationships
In our investigation of complex networks so far, we have concentrated on static prop-
erties which we assumed do not change signiﬁcantly over time. Social networks have
the tendency to have a dynamic topology as can be observed in friendship networks.
For example, let us assume a person A has two friends B and C at time t
1
who do not
know each other. However, it is highly probable that B and C will have a chance to
get acquainted in future and become friends as they have a common friend, and also
they will trust each other through A. This situation is depicted in Figure 11.1 where
the link between B and C is formed at time t
2
. This property of social networks is
known as triadic closure since the link between B and C closes.
11.2.1 Homophily
While social networks dynamically evolve, their formation usually follows a simple
principle, the entities of the network are more likely to form relationship with enti-
ties of similar structure to themselves. For example, students at a high school will
prefer to form friendship with students close to their age. This principle is known
as homophily and is a widely investigated topic in social networks. Given a social
network with two distinct populations such as boys and girls in a high school, we
will search ways of evaluating if there is some homophily in such a network. In other
words, do girls tend to become friends among themselves or with the opposite gen-
der? We can evaluate the degree of homophily as in [7] where we will assume the
percentage of the ﬁrst population (male) is p
1
and the second one (female) is p
2
.
When each node of the graph modeling the social network is independently assigned
the gender male with probability p
1
and female with probability p
2
, the probability
of having two males at the end of an edge is p
2
1
and female is p
2
2
. The probabil-
ity of having a male and a female at the end of an edge is 2p
1
p
2
considering both
directions. We can now count the number of edges in the cutset between the two
communities to ﬁnd its ratio to the number of all edges and check whether this value

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required