L3-Network Structure and Measures
CHAPTER 3
9/2/2025 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.
9/2/2025 SOCIAL NETWORK ANALYSIS
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 of a degree and out-degree.
The in-degree is given by the number of edges coming
node 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.
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 SOCIAL NETWORK ANALYSIS
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.
Centrality
Four types of centrality are considered:
1) Degree Centrality
2) Closeness Centrality
3) Betweenness Centrality
4) Eigen Vector Centrality
9/2/2025 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.
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 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.
9/2/2025 SOCIAL NETWORK ANALYSIS
Closeness centrality
9/2/2025 SOCIAL NETWORK ANALYSIS
Closeness centrality
9/2/2025 SOCIAL NETWORK ANALYSIS
Exercise-1
Find the node with greatest closeness
centrality in the graph.
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.
[Link]
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.
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 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.
9/2/2025 SOCIAL NETWORK ANALYSIS
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
Exercise-1
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.
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 totalled 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.
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 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 shake hands with?
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 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= [Link] 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.
9/2/2025 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.
9/2/2025 SOCIAL NETWORK ANALYSIS
Density in egocentric network
While calculating density consider a 1.5 diameter network, Exclude the ego node.
Draw the egocentric network [Link] 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
(a)
Fig 3.7 : 1.5 Diameter egocentric network for 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.
9/2/2025 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
9/2/2025 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.
9/2/2025 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.
9/2/2025 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.
9/2/2025 SOCIAL NETWORK ANALYSIS
Freeman’s Formula for Centralization
n* is the most central node and ni is every other node
9/2/2025 SOCIAL NETWORK ANALYSIS
Freeman’s Formula for Centralization
n* is the most central node and ni is every
other node
9/2/2025 SOCIAL NETWORK ANALYSIS
Sample Graph
9/2/2025 SOCIAL NETWORK ANALYSIS
Sample Graph
9/2/2025 SOCIAL NETWORK ANALYSIS
Small worlds
In social network analysis, the concept of "small worlds" refers to a type of network structure
where most nodes are not directly connected to each other but can be reached from every other
by a small number of steps. This idea is closely related to the "six degrees of separation" theory,
which suggests that any two people in the world are connected by, at most, six social
connections.
9/2/2025 SOCIAL NETWORK ANALYSIS
Small worlds
The key features of a small-world network are:
[Link] Clustering: In a small-world network, nodes tend to form tightly knit clusters, with a high
probability that two neighbors of a node are also neighbors of each other.
[Link] Path Lengths: Despite the high clustering, the average shortest path between any two
nodes in the network is relatively short. This means that even though the network is highly
clustered, it doesn’t take many steps to connect one part of the network to another.
9/2/2025 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.
9/2/2025 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.
9/2/2025 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.
9/2/2025 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?
9/2/2025 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.
9/2/2025 SOCIAL NETWORK ANALYSIS
9/2/2025 SOCIAL NETWORK ANALYSIS
Network Visualization
CHAPTER 4
9/2/2025 SOCIAL NETWORK ANALYSIS
Why Visualization?
Humans are wired to find patterns visually.
We have natural abilities to see anomalies, patterns, clusters, and changes.
we can recognize many of these things without consciously looking for them.
Why Visualization?
1. Information visualization deals with the presentation of data in visual format. The data
may be numeric, categorical, network data (like social networks), text, and other types.
2. Good information visualization supports users in better understanding the data they are
seeing .
3. The goal of information visualization is to take advantage of humans’ natural abilities to
see patterns, anomalies, relationships, and features in visual data.
4. Visualizations are a qualitative way to begin understanding data. From there,
quantitative experiments or analysis can follow to explain any insights.
5. Graph visualizations apply all these lessons to looking at the structure of networks.
Types of network
visualizations
Graph layout : Every network is made up of nodes and edges.
Researchers have presented some general guidelines that make network visualizations easier to work
with:
1) Every node is visible.
2) For every node you can count its degree.
3) For every link you can follow it from source to destination.
4) Clusters and outliers are identifiable.
network layout algorithms
This section presents a few of the most common network layout algorithms.
Note that many of these algorithms have some random features in them.
They start with the nodes randomly placed and iteratively move them around into better positions.
As a result, running the algorithm multiple times will produce graphs that look different. They will
often be similar but may be positioned differently.
Also, each iteration helps to improve the layout.
Eventually, the iterations make small or no changes. Some applications automatically run the
algorithms for a fixed number of rounds, but other times the user can specify a number.
We are not concerned about the absolute position in x and y axis.
Types of Network
Layout
Random layout
Often, when loading data into a visualization tool, the nodes are placed randomly.
This is called a random layout, and it often does not provide much insight into the structure of
the network.
Figure 4.4 shows the same network from Figure 4.3 presented in a random layout.
We may be able to tell that node a has a high degree in this network, but the clusters and other
patterns are not at all clear from the random layout.
Circular Layout…
Circular layouts place all the nodes in a circle and then add edges between them.
Some circular layouts place nodes closer to one another when they are more closely connected.
In Figure 4.5, the cluster of nodes labeled a1 through a10 is clearer because of the density of
edges in that section of the graph.
The chain of nodes from b through b4 is also present, though the edges around the circle are a bit
harder to pick up visually than in the Figure 4.3 layout.
A circular layout places nodes in structured positions and then adds edges between connected
pairs.
Circular layout
Grid layout
Note that the degree of node a is
clearly high, the cluster of nodes
a1 through a10 is obvious, and the
chain of nodes b through b4 is
clear across the top.
Force-directed layout
1. Most graphs are not laid out randomly or in one of these formats with a predetermined structure.
2. Instead, the layout is dynamic and determined by the connections between the nodes.
3. Those nodes that are more closely connected are laid out close to one another, and those that are distant
are shown further apart.
4. This type of layout is generally called force directed. Nodes and edges are treated as a physical system,
and a Simulation of that system is applied to determine a final layout.
5. For example, nodes may be treated as objects, and edges may be treated as springs that apply equal force.
The nodes are randomly laid out, connected by springs for edges, and then a simulation of how the springs
would physically behave determines the final Position of nodes and edges.
6. A cluster of nodes with many connections will be close together, because pulling any node away pulls on
many springs that want to keep it close.
7. Figure 4.3 uses an algorithm that does this simulation.
Force-directed layout
The algorithm is based on a physical model. Nodes are
represented as points in a plane that are electrically
charged and apply repulsive forces against each other.
Edges connect these points simulating a spring-force,
attracting adjacent nodes.
The model iteratively determines the resulting forces
that act on the nodes and try to move the nodes closer to
an equilibrium where all forces add up to zero, and the
position of the nodes stays stable.
Yifan Hu layout
It is a very fast algorithm with a good quality on
large graphs. It combines a force-directed model
with a graph coarsening technique (multilevel
algorithm) to reduce the complexity. The repulsive
forces on one node from a cluster of distant nodes
are approximated by a Barnes-Hut calculation,
which treats them as one super-node. It stops
automatically.
Yifan Hu layout
Many algorithms lay out graphs in this matter.
Figure 4.3 uses one called Yifan Hu. Figure 4.7 uses a variant called Force Atlas. While there are differences
between Figures 4.3 and 4.7, the similarities in clustering and separate nodes are clear.
Harel-Koren fast multiscale layout
a. The Harel-Koren fast multiscale algorithm (Harel and Koren, 2000), available in NodeXL, is
designed to quickly lay out large, complex graphs.
b. It is based on force-directed layout algorithms but uses optimizations in the underlying code to
make the algorithm computationally efficient.
c. For large graphs with thousands of nodes, generating a layout with many force-directed algorithms
can take a very long time.
d. With Harel-Koren, it often can be achieved in a few seconds, making it an ideal choice for large
networks .
Other layouts
Most graphs will be presented using a force-directed layout algorithm.
However, there are some more sophisticated layouts designed to convey additional information
through layout.
Figure 4.9 shows a layout available in the graphing program NodeXL. Here, nodes are clustered,
grouped into boxes, and then links are added within and between boxes.
Visualizing network features
The layout algorithms dictate the placement of nodes and edges.
Other network features, like edge weights, node properties, labels, and clusters, can
also be visualized.
Labels
Labels are some of the more difficult attributes to show in a network, both on nodes and on edges.
Figure 4.10 shows a network with only 92 nodes, which is still relatively small.
The nodes represent YouTube videos, and the edges indicate that they were tagged with at least one
similar term.
The node labels are the YouTube identifiers for each video. Even in this small graph, the image becomes
very cluttered with all the labels shown.
Labels..
1. Similar problems happen with edge labels.
2. Whether shown on top of the edge with straight alignment or angled along the edge, the
graph tends to become cluttered and difficult to read.
3. Some techniques can improve on this a bit, either by putting boxes around the text, by
only showing a few labels of interest, or by relying on interactive interfaces that only show
labels on demand. The latter allow the user to move the mouse over a node or edge and see
the label or other data on demand.
4. That facilitates exploration of the graph without the clutter. Still, there are no solutions to
totally eliminate this problem when producing fixed visualization images, so often labels are
left off.
Size, shape, and color
Categorical or quantitative attributes are particularly easy to show by adjustments in size, shape,or
color.
Figure 4.11 shows color encoding of node degree.
Darker colors indicate nodes with higher degrees, and node a is the darkest. For clarity, the node labels
have been left off this graph.
Node color could also be used to indicate other attributes of a node. For example, node color could indicate
if each person is a friend, family member, classmate, co-worker.
Keeping color as an indicator of degree, node size can be used to indicate other attributes.
Edges can also be treated with color or thickness to indicate their attributes.
For example, different types of relationships could each be coded in a different color. Edge weights are also
commonly visualized.
Larger graph properties
Larger graph properties can also be encoded in visualizations.
Figure 4.13 shows a new graph that has two main clusters.
This graph is a network of YouTube videos, where nodes represent videos and edges connected videos
that share a common tag. All of these videos were tagged with the word “cubs”; Even without the color
coding, the two groups would be relatively easy to see. But using a community detection algorithm that
groups nodes into clusters, and then color coding by those clusters, makes it even more apparent.
Scale issues
Visualization is very useful for analysing networks of this size or smaller. When networks become much
larger, the quality of the visualization diminishes.
Figure 4.15 shows a network from a peer-to-peer file sharing network.
Nodes represent hosts (computers participating in the network), and edges represent connections
between them.
There are close to 11,000 nodes in this network with roughly 40,000 edges. Even with a very low
density(,0.001), there are still too many nodes and edges to see much of anything.
Depending on the structure of the network, it is sometime possible to get useful visualizations with up to
around 10,000 nodes; however, networks under1,000 nodes are typically safest.
Density
Density can also be a problem for visualization, even if the number of nodes is small.
Figure 4.16 shows a network of members of the U.S. Senate.
There are only 100 nodes but over 4,100 edges.
The edges indicate that the senators have voted the same way in at least one bill.
As this network shows, there are no interesting patterns visible with the threshold of
40%; the network is simply too dense.
Filtering for visual patterns
1. It is often difficult to see any patterns in very dense networks.
2. One way to compensate for this is to filter the networks when possible.
3. For example, if we take the same network from Figure 4.13 and filter the edges so that
they only connect senators who have voted the same way on at least two-thirds of the
bills, the pattern changes dramatically, which is shown in Figure 4.17.
4. In this figure, two clear clusters emerge, representing the two major political parties.
5. Furthermore, five senators are pulled out from the major party clusters along the center,
indicating that they frequently vote with members of both parties.