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

a few links.

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

Figure 11.1: Triadic closure example

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

Start Free Trial

No credit card required