L3-Network Structure and Measures

CHAPTER 3

22-08-2024 SOCIAL NETWORK ANALYSIS

 Introduction
This chapter cover methods,
- for understanding and comparing networks,
- the role of nodes within networks,
- measuring importance,
- and related properties.
The network measures allow an analyst to identify important or influential
individuals, characterize the network structure, understand how individuals fit
within the landscape of the network, and carry these properties forward to
understand how and why things happen in a network.

22-08-2024 SOCIAL NETWORK ANALYSIS

 Degree of a node
Simplest network property of a node is Degree.
The degree of a node is the number of edges connected to that node.
In undirected graphs, the degree of a node is the total number of edges connected to it.
In directed graphs, there are two measures of degree: in-degree and out-degree.
 The in-degree is given by the number of edges coming into the node. In network
diagrams in-degrees are shown as edges with arrows pointing at the node.
The out-degree is the number of edges originating from the node going outward to
other nodes. These are shown with arrows pointing away from the node.
The sum of the in-degree and out-degree gives you the total degree for the node.

22-08-2024 SOCIAL NETWORK ANALYSIS

22-08-2024 SOCIAL NETWORK ANALYSIS
 Centrality

Centrality is one of the core principles of network analysis.

It measures how “central” a node is in the network. This is used as an estimate of its importance in network.
what counts as “central” may vary depending on the context. Correspondingly, there are a number of ways
to measure centrality of a node.
Four types of centrality are considered:
1) Degree Centrality
2) Closeness Centrality
3) Betweenness Centrality
4) Eigen Vector Centrality

22-08-2024 SOCIAL NETWORK ANALYSIS

 Degree centrality

Degree centrality is one of the easiest to calculate.

The degree centrality of a node is simply its degree—the number of edges it
has. The higher the degree, the more central the node is.
This can be an effective measure, since many nodes with high degrees also have
high centrality by other measures.
Degree centrality is a good measure of the total connections a node has, but will
not necessarily indicate the importance of a node in connecting others or how
central it is to the main group.

22-08-2024 SOCIAL NETWORK ANALYSIS

22-08-2024 SOCIAL NETWORK ANALYSIS
 Closeness centrality
Closeness centrality indicates how close a node is to all other nodes in the network.
It is calculated as the average of the shortest path length from the node to every other node in network.

22-08-2024 SOCIAL NETWORK ANALYSIS

22-08-2024 SOCIAL NETWORK ANALYSIS
 In the case of closeness centrality, or average shortest
path length, lower values indicate more central nodes.
 Thus, since node D’s closeness centrality is 1.71 and
node A’s is 3.43, node D is more central by this
measure.
 The benefits of closeness centrality are that it indicates
nodes as more central if they are closer to most of the
nodes in the graph.
This strongly corresponds to visual centrality—a node
that would appear toward the center of a graph when
we draw it usually has a high closeness centrality.

22-08-2024 SOCIAL NETWORK ANALYSIS

Exercise-1
Exercise 2

1. Identify highest, lowest degree centrality nodes in graph.

2. Identify highest closeness centrality node in graph.

SOCIAL NETWORK ANALYSIS

 Betweenness Centrality
The betweenness centrality for each vertex is the number of these shortest paths
that pass through the vertex.
How important a node is to the shortest paths through the network.
 Steps to compute Betweenness Centrality

1. select a pair of nodes and find all the shortest paths between those nodes
2. we compute the fraction of those shortest paths that include node N.
3. We repeat this process for every pair of nodes in the network
4. Add up the fractions we computed to obtain centrality.
22-08-2024 SOCIAL NETWORK ANALYSIS
22-08-2024 SOCIAL NETWORK ANALYSIS
22-08-2024 SOCIAL NETWORK ANALYSIS
22-08-2024 SOCIAL NETWORK ANALYSIS
Compute Betweeness Centrality for the given graph with
respect to node B
 AC, AD, AE, AF, AG, AH,
CD, CE, CF, CG, CH,
DE, DF, DG, DH,
EF, EG, EH, FG, FH, and GH.

Without counting, we know that 100% of the shortest paths

from A to every other node in the network go through B,
since A can’t reach the rest of the network without B. Thus,
the fractions for AC, AD, AE, and AF, AG, and AH are all 1.

B = 6×1 (A to all others) + 0.5 (CD) +4×0 (all remaining

pairs) = 6 + 0.5 + 0 = 6.5

The betweenness centrality of A is zero, since no shortest paths between D, C, E, F, G, and H go through A.
 Betweenness Centrality

Betweenness centrality is one of the most frequently used centrality measures.

 It captures how important a node is in the flow of information from one part of the network to
another.
In directed networks, betweenness can have several meanings. A user with high betweenness may
be followed by many others who don’t follow the same people as the user. This would indicate that
the user is well-followed.
Alternatively, the user may have fewer followers, but connect them to many accounts that are
otherwise distant.
Understanding the direction of the edges for a node is important to understand the meaning of
centrality.

22-08-2024 SOCIAL NETWORK ANALYSIS

 Case Study- finding hijackers of 9/11 attacks by Valdis Krebs
Degree Centrality: How many links each hijacker had to the rest of the network.
Betweenness Centrality: Their location in the network relative to other members.
Closeness Centrality: The average social distance between a particular member and all of
the other members of the network.
 Exercise

1. Identify betweeness centrality of nodes P and G in graph.

2. Identify highest betweeness centrality node in graph.

08-08-2020 SOCIAL NETWORK ANALYSIS

 Eigenvector centrality

1. Eigenvector centrality measures a node’s importance while giving consideration to the importance of its
neighbors. For example, a node with 300 relatively unpopular friends on Facebook would have lower
eigenvector centrality than someone with 300 very popular friends.
2. It is determined by performing a matrix calculation to determine what is called the principal eigen
vector using the adjacency matrix.
3. variant of Eigen- vector centrality is at the core of Google’s PageRank algorithm -use to rank web
pages.
4. The main principle is that links from important nodes are worth more than links from unimportant
nodes.
5. All nodes start off equal, but as the computation progresses, nodes with more edges start gaining
importance. Their importance propagates out to the nodes to which they are connected. After re-
computing many times, the values stabilize, resulting in the final values for eigenvector centrality.

22-08-2024 SOCIAL NETWORK ANALYSIS

Describing networks – Degree Distribution
•A number of measures can be used to describe the structure of a network as a whole.
•Degree distribution: Degree is used to describe individual nodes. To get an idea of the degree for
all the nodes in the network, we can build the degree distribution, which shows how many nodes
have each possible degree.
•To create a degree distribution, calculate the degree for each node in the network. The next step is
to count how many nodes have each degree. This is totaled for each degree, including those for
which there are no nodes with that count.
•The most common way to show a degree distribution is in a bar graph. The x-axis has the degrees
in ascending order, and the Y-axis indicates how many nodes have a given-degree.

22-08-2024 SOCIAL NETWORK ANALYSIS

22-08-2024 SOCIAL NETWORK ANALYSIS
22-08-2024 SOCIAL NETWORK ANALYSIS
 Describing networks – Density
•Density—the number of edges in the graph divided by the number of possible edges—is one of the
most common ways of describing a network.
•Another way to understand both individual nodes and the network as a whole is by studying density.
•Consider the following two networks, which both have the same number of nodes. Network (a) has very few
edges while network (b) has numerous edges among the same number of nodes. Therefore, network (b) has
higher density.
•There is a formula to calculate density:
•This scenario is sometimes known as the handshake problem—if a person comes into a room, how many
people can he or she shakehands with?

22-08-2024 SOCIAL NETWORK ANALYSIS

22-08-2024 SOCIAL NETWORK ANALYSIS
22-08-2024 SOCIAL NETWORK ANALYSIS
 Density…
•Consider the networks in Figure3.6. Both have eight nodes.
•Network(a) has five edges. Since it is an undirected network,the density is 5/(8*8-1)/2 = 5/28=
0.179.
•Network (b) has 16edges, so the density is 16/28= 0.571.Note that the density is higher for
network(b).
•A network with no edges would have a density of 0.
•On the other hand, the densest possible network would be a network where all possible edges
exist—a clique. In a clique, the numerator and denominator will be the same, so the density will
be 1.
•This illustrates that density is always between 0 and 1,where 0 is the lowest possible density
and 1 is the highest.

22-08-2024 SOCIAL NETWORK ANALYSIS

 Density in egocentric networks
•Computing the density of each node’s egocentric network gives us a way to compare nodes.
•Some will have dense egocentric networks, which means a lot of their friends know one another. Others
will have sparse egocentric networks, and thus we know their connections often do not know one
another.
•The density of an egocentric network is sometimes referred to as the local clustering coefficient.

22-08-2024 SOCIAL NETWORK ANALYSIS

 Density in egocentric network
While calculating density consider a 1.5 diameter network, Exclude the ego node.

Draw the egocentric network w.r.to node A and node B

Fig 3.6
 Calculate density for the below graphs
B

Wrt Node B
H
C

Wrt Node A

E
F

0.833

0.6 (a)

Fig 3.7 : 1.5 Diameter egocentric network for Fig 3.6

 Connectivity
Density measures the percentage of possible edges in a graph.
Connectivity, also known as cohesion, measures how those edges are distributed.
Connectivity is a count of the minimum number of nodes that would have to be
removed before the graph becomes disconnected; that is, there is no longer a path from
each node to every other node.

22-08-2024 SOCIAL NETWORK ANALYSIS

What is the connectivity here?
 the connectivity is 1 because removing node B, C, or
D would disconnect the graph. Since removing any
one of those nodes disconnects the graph, the
connectivity is 1

22-08-2024 SOCIAL NETWORK ANALYSIS

What is the connectivity here?
 connectivity is 2. Removing any one node would not
break the graph into two parts, but there are several
options for removing two nodes that would. For
example, removing nodes E and F would separate G
from the rest of the graph. If we removed B and D
instead, node A would become separated.

22-08-2024 SOCIAL NETWORK ANALYSIS

 Centralization
• It is an important way to understand the role of node in the networks and
to compare the nodes
• Centrality measure is used to understand the network.

• What does high centrality mean?

• How do we compute it?
• For example, betweenness centrality can represent the control one node has in the ability of others to
communicate.
• If a few nodes have very high betweenness, we can say that the power is centralized in those nodes.

22-08-2024 SOCIAL NETWORK ANALYSIS

 Freeman’s Formula for Centralization
Centralization is computed by looking at the sum of the differences in centrality between the most
central node and every other node in the network, and dividing this by the maximum possible
difference in centrality that could exist in the graph (Freeman,1979).
Since there are different centrality measures(e.g., betweenness, closeness,etc.), there are different
centralization measures for a graph.
But the basic formula is the same, and different centrality measures can be substituted.

22-08-2024 SOCIAL NETWORK ANALYSIS

Freeman’s Formula for Centralization

n* is the most central node and ni is every other node

22-08-2024 SOCIAL NETWORK ANALYSIS
 Freeman’s Formula for Centralization

n* is the most central node and ni is every

other node

22-08-2024 SOCIAL NETWORK ANALYSIS

Sample Graph

22-08-2024 SOCIAL NETWORK ANALYSIS

 Small worlds
six degrees of separation:
 one phrase from social network analysis has made its way into common vocabulary.
It is the title of both a play and a movie, and the origin for pop culture phenomena like the
Kevin Bacon Game.
The core idea behind the phrase, is that any two people in the world are separated by short
paths, on average about six steps.
Term small worlds, indicates that people who may be very far apart physically and socially
are still connected with relatively small paths.

22-08-2024 SOCIAL NETWORK ANALYSIS

 Small Worlds..
fundamental research on this topic was done in the 1960s by Stanley Milgram (Milgram, 1967).
Milgram wanted to explore the interconnection of social networks, so he devised an experiment.
He sent information packets to people who lived in Omaha, Nebraska and Wichita, Kansas. The
recipients were asked to get the packet to a specific person in Boston, Massachusetts. If they
knew the Boston contact personally, they were supposed to send the packet directly to them. If
not, they were supposed to think of someone they did know who was likely to be closer to the
person in Boston, sign their name to a roster, and send the packet on to their friend. The friend
was then instructed to repeat the process.
Average number of links from the original recipient to the contact person was between five and
six.

22-08-2024 SOCIAL NETWORK ANALYSIS

 Small Worlds…
Small world networks have two primary characteristics:
a short average shortest path length and high clustering (measured by the local clustering
coefficient).
The idea of six degrees of separation reflects this short average path length.
Consider an example: We have a network with 36 nodes and 72 edges. These edges can be
distributed in a variety of ways. Figure 3.9 shows what is known as a regular network.
Each node is connected to a fixed number of neighbors on either side.

22-08-2024 SOCIAL NETWORK ANALYSIS

Regular Graph

 FIGURE 3.9 A regular graph. Each node is connected to

the neighbour directly next to it and two steps away in
the layout.

• There are many steps necessary to find a path from A to

B in this network. The shortest path moving clockwise is
eight steps.
• In Figure 3.9, B is almost half way around the ring of
nodes. nearly 1/4 of the nodes are touched before
reaching B.
• A quarter of the nodes would still be touched if the graph
expanded to1,000 nodes, so the path length would be
around 250. For a node with a million nodes, the path
length would be around 250,000.
Random Graph
• Graph with the same number of nodes and edges can be
created where the edges randomly connect the nodes instead
linking them in a regular pattern. This is called a Figure 3.10
random graph.
• the shortest path from A to B is much shorter (A to C to B):
just two steps. And, the shortest path between most nodes
is shorter.
• If we increased the number of nodes to one million, the
average shortest path length would increase, but not at the
rate of the regular graph.
 Small Worlds…
Small world networks, including social networks, have this property of a short path length,
even when the networks become huge.
Small world networks have one other main characteristic: high clustering.
In social terms, this means that a person’s friends tend to know one another. Clustering is
computed as the average of the node’s local clustering coefficients.
In 2011, Facebook had 720 million users and the average shortest path length was 4.74.
How is this possible?

22-08-2024 SOCIAL NETWORK ANALYSIS

In Figure 3.9, node A has four neighbors. That means there are six possible edges between them.
Three of those edges exist, so the density of A’s egocentric network is 0.5.
In Figure 3.10, however, A has three neighbors with three possible edges, but only one edge
connects them, for a density of 0.33.
Node B has the same density as Node A in Figure 3.9—every node has the same pattern of
neighbors and connections.
 In Figure 3.10, however, none of node B’s neighbors are connected, so the density of B’s
egocentric network is 0. In regular graphs, the clustering is high, but in random graphs the
clustering is low.

22-08-2024 SOCIAL NETWORK ANALYSIS

22-08-2024 SOCIAL NETWORK ANALYSIS