Unit-I

Graphs

Objective:
• To familiarize with the technological concepts of Social networks.

Syllabus:

Graphs as models of Networks, Paths and Connectivity, Distance and Breadth-First

Search, The Strength of Weak Ties, Structural Holes, Betweenness measure, Homophily, Affiliation,
Structural Balance.

Learning Outcomes:

At the end of the unit student will be able to:

1. understand the concepts of graph theory.
2. apply the graph models to create a social network.
3. analyze various kinds of relationship for the network.
4. measure the homophily for the network.
5. hypothesize the structural balance of the network.

Learning Material
Introduction:
Definition:
• Social Network is a network of social interactions and personal relationships.
• Social Network is a social structure made up of a set of social actors (such as individuals or
organizations) sets of dyadic ties and other social interactions between actors.
Difference between social media and social networking:
• Social media is a platform for broadcasting information, whereas social networking is a
platform for communicating with one another.
Social Networking
• It is the practice of expanding the number of social contacts by making connections
through individuals, often through social media.
• Social Networking Sites
• It is a website or other application which enables users to communicate with each other by
posting information, comments, messages etc.
Examples:
Page 1 of 25
 • Face book
• Twitter
• LinkedIn
Social Network Analysis (SNA)
• Social Network Analysis (SNA) is the process of investigating social structures using
networks and graph theory.
• It characterizes networked structures in terms of nodes (individual actors, people, or things
within the network) and the ties, edges, or links (relationships or interactions) that connect
them.
• Social networks have been at the core of human society since we were hunters and
gatherers.
• Kinship and family relations are social networks.
• Neighborhoods, villages, and cities are crisscrossed with networks of obligations and
relationships.
Network is different from Networking
• A Network is simply a set of relations between objects which could be people,
organizations, nations, items found in a google search, brain cells or electrical
transformers.
• Networking is actively using a network to make connections to further one’s personal
goals.
• Internet itself is an example of a huge network and changed the rules of social networks
because the more that people see each other in person and talk on the phone, the more they
use the internet.
Network
• A network contains a set of objects (nodes) and a mapping or description of relations
between the objects or nodes.
• It is a set of relationships.
• A network with two nodes with mutual relationship is called a “Dyad".
• The simple network of three nodes with mutual relationship is called a "Triad".

Types of Relationships
1. Simple Relationship
The simplest network contains two objects, 1 and 2, and one relationship that links
them. Nodes 1 and 2, for example, might be people, and the relationship that' links them

Page 2 of 25
might be as simple as standing in the same room. If 1 is in the same room as 2, then 2 is in
the same room as 1. The relationship is in figure 1.1 is not directional.

Fig 1.1: Simple Relationship

2. Directed Relationship
There are also directional relationships (figure 1.2) such as 1 likes 2. In directed
relationship, the exchange of information flows in a certain direction.

Fig 1.2: Directed Relationship

3. Symmetric Relationship
In Symmetric relationship, the relationships are mutual. Nodes 1 and 2 like one
another, or their liking is mutual. The liking network below (figure 1.3) is similar to the
first one of standing in the same room together, but has a valence or a flow. Mutuality is
not easy to achieve, so mutual networks tend to be limited.

Fig 1.3: Symmetric Relationship

4. Multiplex Relationship
In multiplex relationship, nodes have more than one relationship. For example, 1
and 2 might be in the same room and might also like one another. When there is more than
one relationship, this is called a multiplex relationship. Relationships can be more than the
sharing of an attribute or being in the same place at the same time. There can be a flow
between the objects or the nodes.
Liking, for example, might lead to an exchange of gifts. Flows and exchanges are very
important in network theory.
5. Relationship through an Intermediatory
Consider a network (figure 1.4) between pairs that operates via an intermediatory
node.

Page 3 of 25
 Fig 1.4: Relationship through an Intermediatory
For example node 1 is connected to 3 via 2. The relationships shown above are directional
and not reciprocal. If the relationship is transitive, it means that if 1 loves 2, then 2 also loves
3. Transitive relationships are more common in an official hierarchy. Node 1 gives a message
to 2 who forwards it to 3. The network distance between pairs of nodes can be described in
terms of the number of steps or links between them.
Sociogram
The network depicted in figure 1.5 is a "Sociogram"—a term invented by Jacob
Moreno, who is regarded as a key founder of modern network studies.

Fig 1.5: Sociogram of Three Nodes, All Mutually Related

Graph Theory, a branch of mathematics, allows sociograms to be manipulated
mathematically. The depiction of relationships gives insight as to what was going on in
small, not overly complicated networks. Network Analysts use Adjacency Matrix to
represent networks algebraically.
1 2 3
1 - 1 1
2 1 - 1
3 1 1 -

Table 1.1 Adjacency Matrix that represents figure 1.5

The numbers, 1, 2, and 3 on the top line and the first column identify the same nodes as in
figure 1.2.e. The number 1 on the second line indicates a connection between the nodes.
Node 1 "chooses" nodes 2 and 3. Node 2 "chooses" nodes 1 and 3. Node 3 "chooses"

Page 4 of 25
 nodes 1 and 2. The dashes indicate that in this graph or matrix, self-choice is not at play,
though in some networks self-choice can be an option. For example, candidates in an
election can vote for themselves.

Types of Networks

Social scientists have investigated three kinds of networks: ego-centric, socio-centric,

and open-system networks.

1. Ego-Centric Networks

• Ego-centric networks are those networks that are connected with a single node or
individual. For example, good friends or all the companies that do business with
Widgets, Inc. (the favorite name of organizations studied in business schools).
• It is a network in which each individual is at least all connected with the person
being supported.
• The support may include help with a job search, comfort during an illness, or a loan
of money
• A person with a large number of good friends whom he or she can count on is
commonly said to have a large "network."
• This network cannot be discussed in social network terms, however, unless we
know whether and how these people are connected with one another.

2. Socio-Centric Networks

• Socio-centric networks are networks in a "box."

• Connections between children in a classroom or between executives or workers in
an organization are closed system networks.
• These networks are most often studied in terms of the fine points of network
structure.

3. Open System Networks

• Open system networks are networks in which the boundaries are not necessarily
clear, for they are not in a box.
• For example, the elite of the United States, connections between corporations, the
chain of influencers of a particular decision, or the adopters of new practices.
• These are the most interesting networks.
•
Page 5 of 25
1 Graphs:
1.1 Nodes and Edges
• Graph is a collection of nodes and edges.
• A graph consists of a set of objects, called nodes, with certain pairs of these
objects connected by links called edges.
• Two nodes are said to be neighbours if they are connected by an edge.
• The following figure on the left shows undirected graph and right show directed
figure.

Figure 1.6 Undirected and directed graph

1.2 Graphs as models of Networks
• Graphs are useful because they serve as mathematical models of network
structures.
• Graphs play a role whenever it is useful to represent how things are either
physically or logically linked to one another in a network structure.
• The thirteen-node (ARPANET) Advanced Research Projects Agency Network
is an example of a communication network, in which nodes are computers or
other devices that can relay messages and the edges represent direct links along
which messages can be transmitted.
• Social networks, in which nodes are people or groups of people, and edges
represent social interaction.
• Information networks, in which the nodes are information resources such as
Web pages or documents, and edges represent logical connections such as
hyperlinks, citations, or cross references.

Page 6 of 25
 Figure 1.7 ARPANET Map

• The above network figure 1.7 can be represented in nodes and edges shown in
the following figure 1.8.

Figure 1.8 Graph model of ARPANET

2. Paths and Connectivity

2.1 paths
A path is simply a sequence of nodes with the property that each consecutive pair
in the sequence is connected by an edge.
2.2 cycles
A cycle is a path with at least three edges, in which the first and last nodes are the
same, but otherwise all nodes are distinct.
2.3 connectivity
A graph is connected if, for every pair of nodes, there is a path between them and
every node can reach every other node by a path.
2.4 components
A connected component of a graph (often shortened to the term component) is a
subset of the nodes such that
(i) Every node in the subset has a path to every other. and
(ii) The subset is not part of some larger set with the property that every node
can reach every other.

Page 7 of 25
3. Distance and Breadth-First Search
3.1 Distance
• Distance is the length of a path to be the number of steps it contains from
beginning to end i.e the no. of edges in the sequence that comprises it.
• Distance between two nodes in a graph should be the length of the shortest path
between them.
3.2 Breadth-First Search
• Breadth First Search searches the graph outward from a starting node, reaching
the closest nodes first.

• First declare all of your actual friends to be at a distance of 1.

• Then find all of their friends (not counting people who are already friends of
yours), and declare these to be at a distance of 2.
• Then find all of their friends (again, not counting people whom you’ve already
found at distances of 1 and 2) and declare these to be at a distance of 3. (. . . )
• Continuing in this way, search in successive layers, each of which represents
the next distance out.
• Each new layer is built from all those nodes that
i. have not already been discovered in earlier layers and
ii. have an edge to some node in the previous layer.

Page 8 of 25
 • This technique is called breadth-first search, since it searches the graph outward
from a starting node, reaching the closest nodes first.
• In addition to providing a method of determining distances, it can also serve as
a useful conceptual framework to organize the structure of a graph, arranging
the nodes based on their distances from a fixed starting point.
• The following diagram depicts BFS for ARPANET figure 1.8.

4. The Strength of Weak Ties

4.1 Triadic Closure
If two people in a social network have a friend in common, then there is an
increased likelihood that they will become friends themselves at some point in the
future. This principle is called as triadic closure.
If nodes B and C have a friend A in common, then the formation of an edge
between B and C produces a situation in which all three nodes A, B, and C have
edges connecting each other – a structure we refer to as a triangle in the network.
The term “triadic closure” comes from the fact that the B-C edge has the effect of
“closing” the third side of this triangle.

Page 9 of 25
 Reasons for Triadic Closure:
1. Opportunity
B and C are more likely to become friends, when they have a
common friend A, is simply based on the opportunity for B and C to meet.
2. Trusting
In the process of forming a friendship between B and C ,it gives
them a basis for trusting each other.
3. Incentive
A third reason is based on the incentive that A may have to bring B
and C together: if A is friends with B and C, then it becomes a source of
latent stress in these relationships if B and C are not friends with each other.
4.2 Strength of Weak Ties
In Social Networks there are two kinds of relationships or ties:
StrongTie:
Strong relationship exists between close members with frequent interactions or
meetings. Example – family members and close friends cause strong ties.
WeakTie:
Weak relationship is caused by distant social relationships and very infrequent
meetings or interactions. Example – Acquaintances and strangers cause weak ties.
in 1973 a Stanford professor published a paper called the Strength of
Weak Ties. According to Granovetter’s paper, the strength of weak ties is said that
each tie has its different perspective and advantages as well and everyone talks
about the advantages of strong ties but there are also some advantages of weak ties
as well which is absent in strong ties.

Figure – Strong and Weak Ties

Page 10 of 25
  Assume I have 5 friends A, B, C, D, and E. Out of these 5 friends 4 (A, B, C, D)
work in the same place where I work and E works in a different company shown in
the following figure 3.5. Now almost all the information that A, B, C, and D have
is already known to me as we live in the same world. But E is from a different
world and that is why every information that E has is new to me although E has a
weak tie with me. So E is the one who helps me in getting new information about
the different world which increases my knowledge.

So strong ties are weak when it comes to information related to new jobs or
job switch and weak ties are strong in the same scenario.
4.3 Neighbourhood overlap
Neighborhood overlap of an edge connecting A and B to be the ratio

Page 11 of 25
 Example: As an example of how this definition works, consider the edge A-F in
Figure3.4

The denominator of the neighborhood overlap for A-F is determined by the

nodes B, C, D, E, G, and J, because each of these nodes is a neighbor of at least one
of A or F. Of these, only C is a neighbor of both A and F, so the neighborhood
overlap is 1/6.
4.4 Embeddedness
The embeddedness of an edge in a network to be the number of common
neighbors shared by the two endpoints.

Page 12 of 25
 Thus, for example, the A-B edge has an embeddedness of 2, because A and
B have the two common neighbors E and F. The local bridges are precisely the
edges that have an embeddedness of zero.
5. Structural Holes
Ronald Burt, one of the world’s top network scientists believes the number one
best predictor of career success is an open network. Individuals who build open networks
recognize the value of structural holes. A structural hole is a gap between two individuals
who exhibit complementary skill sets or knowledge. In contrast to a weak tie, which deals
with the strength of the relationship between two connections, a structural hole is,
according to Burt, a “chasm” or absence of a tie between two connections.

Research has found that structural holes in entrepreneurs’ social networks are
associated with entrepreneurial success. When we exploit structural holes in our network,
we can broker opportunities and combine knowledge in new and exciting ways.

6. Betweenness measure
A way of thinking about networks in terms of tightly-knit regions and the weaker
ties that link them together.

Page 13 of 25
6.1 Methods for Graph partitioning
General Approaches to Graph Partitioning. One class of methods focuses on
identifying and removing the “spanning links” between densely connected regions.
Once these links are removed, the network begins to fall apart into large pieces;
within these pieces, further spanning links can be identified, and the process
continues. We will refer to these as divisive methods of graph partitioning.
Two Partitioning Strategies
1. agglomerative.(Bottom-up)
2. divisive.(Top-Down)
Example: Consider the network given

For example, we can determine the betweenness of each edge in Figure

3.14(a) as follows:
• First consider the 7-8 edge. For each node A in the left half of the graph,
and for each node B in the right half of the graph, their full unit of flow
passes through the 7-8 edge. On the other hand, no flow passing between
pairs of nodes that both lie in the same half uses this edge. As a result, the
betweenness of the 7-8 edge is 7 × 7 = 49.
• The 3-7 edge carries the full unit of flow from each node among 1, 2, and 3
to each node among 4–14. Thus, the betweenness of this edge is 3 × 11 =
33. The same goes for the edges 6-7, 8-9, and 8-12.
• The 1-3 edge carries all the flow from node 1 to every other except node 2.
As a result, its betweenness is 12. By strictly symmetric reasoning, the other
edges linked from nodes 3, 6, 9, and 12 into their respective triangles have a
betweenness of 12 as well.

Page 14 of 25
 • Finally, the 1-2 edge only carries flow between its endpoints, so its
betweenness is 1. This also holds for edges 4-5, 10-11, and 13-14. Thus,
betweenness has picked out the 7-8 edge as the one that carries the most
traffic.

Example2: Consider the following graph.

The sequence of steps in Figure 3.17 in fact exposes some interesting points
about how the method works: When we calculate the betweenness in the first step,
the 5-7 edge carries all the flow from nodes 1–5 to nodes 7–11, for a betweenness

Page 15 of 25
 of 25. The 5-6 edge, on the other hand, only carries flow from node 6 to each of
nodes 1–5, for a betweenness of 5 (and similarly for the 6-7 edge).
Once the 5-7 edge is deleted, however, all the betweennesses for the second
step are recalculated. At this point, all 25 units of flow that used to be on this
deleted edge have shifted onto the path through nodes 5, 6, and 7, and so the
betweenness of the 5-6 edge (and also the 6-7 edge) has increased to 5 + 25 = 30.
This is why these two edges are deleted next.

7. Homophily
One of the most basic notions governing the structure of social networks is
homophily – the principle that we tend to be similar to our friends. Typically, your friends
don’t look like a random sample of the underlying population. Viewed collectively, your
friends are generally similar to you along racial and ethnic dimensions; they are similar in
1. Age.
2. Including the places they live.
3. Their occupations.
4. their levels of affluence.
5. their interests, beliefs, and opinions.e.t.c.,
Aristotle (people “love those who are like themselves”), as well as in proverbs such as
“birds of a feather flock together.” The role of homophily in modern sociological research
was catalyzed in large part by the influential work of Lazarsfeld and Merton in the 1950s.
Page 16 of 25
7.1 Measuring Homophily
The network shown in figure 4.2 depicts a network which contains 9 people
in which 6 are men and 3 are women Thus, suppose we have a network in which
 a fraction p of all individuals are male, and
 a fraction q of all individuals are female.
Consider a given edge in this network. If we independently assign each node the
gender male with probability p and the gender female with probability q, then both
ends of the edge will be male with probability p^2, and both ends will be female
with probability q^2. On the other hand, if the first end of the edge is male and the
second end is female, or vice versa, then we have a cross-gender edge, so this
happens with probability 2pq. Therefore, the test for homophily according to
gender can be summarized as follows:
Homophily Test: If the fraction of cross-gender edges is significantly less than 2pq,
then there is evidence for homophily.In Figure 4.2, for example, 5 of the 18 edges
in the graph are cross-gender edges. Since p = 2/3 and q = 1/3 in this example, we
should be comparing the fraction of crossgender edges to the quantity 2pq = 4/9 =
8/18. In other words, with no homophily, one should expect to see 8 cross-gender
edges rather than 5, and so this example shows some evidence of homophily.
Second, it is also easily possible for a network to have a fraction of cross-
gender edges that is significantly more than 2pq. In such a case, we say that the
network exhibits inverse homophily. The network of romantic relationships shown
in the following figure2.7 Romantic relationships in an American high school over
an 18-month period

Page 17 of 25
8. Affiliation
But in fact, it is possible to put these contexts into the network itself, by working
with a larger network that contains both people and contexts as nodes. Through such a
network formulation, we obtain additional insight into some broad aspects of homophily.
Adopting terminology introduced by Scott Feld, we’ll refer to such activities as
foci – “focal points” of social interaction – constituting “social, psychological, legal, or
physical entit[ies] around which joint activities are organized (e.g., workplaces, voluntary
organizations, hangouts, etc.)”
The following network Figure 4.3, showing two people (Anna and Daniel) and two
foci (working for a literacy tutoring organization, and belonging to a karate club). The
graph indicates that Anna participates in both of the foci, while Daniel participates in only
one. Such a graph is referred to as an affiliation network, since it represents the affiliation
of people (drawn on the left) with foci (drawn on the right). More generally, affiliation
networks are examples of a class of graphs called bipartite graphs. We say that a graph is
bipartite if its nodes can be divided into two sets in such a way that every edge connects a
node in one set to a node in the other set. (In other words, no edges join nodes that belong
to the same set; all edges go between the two sets.) Bipartite graphs are very useful for
representing data in which the items under study are divided into two categories, and we
want to understand how the items in one category are associated with the items in the
other. In the case of affiliation networks, the two.

Page 18 of 25
 There is a natural network perspective on these ideas, which begins from a network
representation that slightly extends the notion of an affiliation network. As before, we have
nodes for people and nodes for foci, but we now introduce two distinct kinds of edges as
well. The first kind of edge functions as an edge in a social network: it connects two
people and indicates friendship (or alternatively some other social relation, like
professional collaboration). The second kind of edge functions as an edge in an affiliation
network: it connects a person to a focus and indicates the participation of the person in the
focus. We will call such a network a social-affiliation network, reflecting the fact that it
simultaneously contains a social network on the people and an affiliation network on the
people and foci. Figure 4.5 depicts a simple social-affiliation network.

Once we have social-affiliation networks as our representation, we can appreciate

that a range of different mechanisms for link formation can all be viewed as types of
closure processes in that they involve “closing” the third edge of a triangle in the network.

Page 19 of 25
 Suppose we have two nodes, B and C, with a common neighbour in the network,
A, and suppose that an edge forms between B and C. As Figure 4.6 illustrates, there are
several possible interpretations of this situation, depending on whether A, B, and C are
people or foci:
i. If A, B, and C each represent a person, then the formation of the link between B
and C is triadic closure, just as in Chapter 3 [see Figure 4.6(a)].
ii. If B and C represent people, but A represents a focus, then the formation of the B-C
edge corresponds to something different: the tendency of two people to form a link
when they have a focus in common [see Figure 4.6(b)]. This is an aspect of the
more general principle of selection, when a person forms links to others who share
characteristics with him or her. To emphasize the analogy with triadic closure, this
process has been called focal closure [259].
iii. If A and B are people, and C is a focus, then we have the formation of a new
affiliation: B takes part in a focus in which her friend A is already involved [see
Figure 4.6(c)]. This is a kind of social influence, in which B’s behaviour comes
into closer alignment with that of her friend A. Continuing the analogy with triadic
closure, we will refer to this kind of link formation as membership closure.
Thus, three very different underlying mechanisms – reflecting triadic closure
and aspects of selection and social influence – can be unified in this type of network as
Page 20 of 25
 kinds of closure: the formation of a link in cases where the two endpoints already have
a neighbour in common. Figure 4.7 shows all three kinds of closure processes at work:
triadic closure leads to a new link between Anna and Claire; focal closure leads to a

new link between Anna and Daniel; and membership closure leads to Bob’s affiliation
with the karate club. Oversimplifying the mechanisms at work, we can summarize
them in the following succinct way:
(i) Bob introduces Anna to Claire.
(ii) Karate introduces Anna to Daniel.
(iii) Anna introduces Bob to Karate.
9. Structural Balance
Here we describe a rich part of social network theory that involves taking a
network and annotating its links (i.e., its edges) with positive and negative signs.
Positive links represent friendship.
Negative links represent antagonism.
Important problem in the study of social networks is to understand the tension
between these two forces. Such a network is called a clique, or a complete graph. We then
label each edge with either + or −; a + label indicates that its two endpoints are friends,
while a − label indicates that its two endpoints are enemies. The principles underlying
structural balance are based on theories in social psychology dating back to the work of
Heider in the 1940’s.

Page 21 of 25
 Based on this reasoning, we refer to triangles with one or three +’s as balanced,
since they are free of these sources of instability, and we refer to triangles with zero or two
+’s as unbalanced. The argument by structural balance theorists is that, because
unbalanced triangles are sources of stress or psychological dissonance, people strive to
minimize them in their personal relationships.

Structural Balance Property:

For every set of three nodes, if we consider the three edges connecting
them, either all three of these edges are labeled +, or exactly one of them is labeled
+.

Page 22 of 25
 Assignment-Cum-Tutorial Questions
A. Objective Questions
1. The term Sociogram is invented by ______________.
2. ___________ is used to represent the network mathematically.
3. The phrase “A Friend of my friend is a friend of mine” is example of______________.
4. As per the well-known history of Karate club, in the end, the club got divided into how
many communities [ ]
a) 1 b) 2 c)3 d) 4
5. A Person with higher degree than others have [ ]
a) high centrality. b) low Centrality. c) small distance. d) None of these.
6. Networks in which boundaries are not clear [ ]
a) Ego Centric Network. b) Socio Centric Network.
c)Open System Network. d)None of these.
7. Homophily refers to the friendship between people [ ]
a) Who are similar to each other.
b) Who are dissimilar to each other.
c) Who are introduced to each other because of a common friend.
d) Who have different ethnicity but live at the same place.
8. Weak ties are important because: [ ]
a) They might later become strong ties.
b) They provide connections across communities.
c) They connect nodes with difficult-to-reach parts of the network.
d) both b and c
9. Which of the following triangles follows the social belief that `Enemy of my enemy is my
friend'? [ ]

10. Find the clustering coefficient for the node 3 in the following network____

Page 23 of 25
B. Subjective Questions
1. Explain basic types of network and list various types of relationships observed in a
network.
2. Mention different kinds of networks investigated by social scientists.
3. Justify the sentence “Graphs as model of Networks”.
4. Summarize the concept of Structural Holes.
5. Explain the concept of Embeddedness.
6. What is triadic closure? List and explain the reasons for triadic closure.
7. Demonstrate various paths and connectivity in network with suitable example.
8. Compare strong tie and weak tie of a network with neat suitable sketch.
9. Illustrate the Tie strength on Facebook.
10. Explain the Breadth first search traversal of a graph with neat sketch.
11. Analyze the following graph. calculate the following

a) embeddedness value of 3-10 edge.

b) embeddedness value of 10-7.
c) neighbourhood overlap of an edge connecting 3 and 2.
d) clustering coefficient for node 3.
12. Discuss various methods for graph portioning with suitable example.
13. Explain Bridges and Local Bridges with neat sketch.
14. Calculate the Neighbourhood Overlap for all the edges in the given network and identify
the strong and weak ties. A strong tie is having neighbourhood overlap score >=0.5.

15. Define Homophily. Demonstrate the procedure to measure homophily.

Page 24 of 25
16. Compute the Clustering coefficient of shaded node in a given graph.

17. Use the following network find the clustering coefficient for node 1, 3 and node 7.

Page 25 of 25