In this section we focus on how to quantify the structure of a network.
Structure property relationship: In network science, the structure of a network often relates to its properties.
We will focus on the following properties:
Assortativity
Connectedness
Paths
Trees
Small-world property
Visualization of network structure
Here we show examples of common elements that emerge in network structures, we will be looking at each of these more closely as we go along.
Recall centrality: Method to quantify the importance of a node or a link
Homophily and Assortativity
Birds of a feather flock together
Getting started: recall social networks
It is important to note that the following discussion primarily focuses on social networks.
While aspects of the discussion may be applied more generally, other types of networks, such as information networks, biological networks, and communication networks, may or maynot exhib similar properties.
Homophily: A network formation mechanism
Definition: The tendency for similar individuals (nodes) to form connections more frequently than dissimilar ones.
*“Birds of a feather flock together.”
Examples: People with similar beliefs, professions, or cultural backgrounds often become friends.
Consequences:
Can strengthen communities and foster support.
But also contributes to echo chambers and filter bubbles, where exposure to diverse viewpoints is limited.
Increases a network’s vulnerability to misinformation and coordinated influence.
Social Influence
Definition: The process by which connected individuals become more similar over time due to interaction and mutual influence.
In some sense, social influence is the opposite of homophily, i.e. dissimilar nodes with existing connections becoming similar over time, rather than similar nodes forming connections (homophily).
Examples:
Friends adopting each other’s slang, habits, or political opinions.
Collective behavior shifts during trends or viral movements.
Chicken or the Egg?
Do we form links because we are similar (homophily), or do we become similar because we are linked (social influence)?
In most real-world networks, these forces:
Operate simultaneously,
Reinforce each other, and
Make it challenging to untangle cause from effect.
The dynamic interplay between homophily and influence shapes the structure and evolution of social networks.
Assortativity: Quantifying network similarity
Definition: Assortativity is a network property that measures the tendency of nodes in a network to connect to other nodes that are similar in some way.
Types of Assortativity:
Degree Assortativity: Do high-degree nodes connect to other high-degree nodes?
Attribute Assortativity: Do nodes with similar attributes (e.g., age, gender, profession) tend to connect?
Interpretation:
Positive Assortativity: Similar nodes are more likely to connect (e.g., friends with similar ages).
Negative Assortativity (Disassortativity): Dissimilar nodes are more likely to connect (e.g., mentors and mentees).
Importance:
Influences the robustness and dynamics of networks.
Helps understand patterns of segregation or integration.
Example: Attribute Assortativity
Assortativity increases predictive power:
If assortativity is present we can make predictions about attributes of unknown nodes by inspecting their neighbors
Conceptually this is a similar idea to the KNN algorithm in machine learning
Important: It is however still differnt, in KNN the “similarity” is entirely based on the features (attributes) of a data-point, since there are no edges, in network science we can use the network structure itself to make predictions.
Example: Assortative networks
high-degree nodes tend to be connected to other high-degree nodes, while low-degree nodes tend to have other low-degree nodes as neighbors.
Example: Dis-assortative networks
This is the opposite of an assortative network, in this case, low-degree nodes tend to be connected to high-degree nodes.
Example: The Web, food webs, and other biological networks tend to be disassortative.
For example, online it is common for a low degree website to point into a high degree website via a URL.
Visualization: Comparison of assortative and disassortative networks
Recall: Pearson correlation
Given two vectors of equal length, you can compute the extent to which their values covary with each other
Assortativity Coefficient
Measures correlation between node degrees across edges
Specifically, the degree assortativity coefficient is a special case of the Pearson correlation coefficient
Interpretation:
r > 0 → Assortative: nodes tend to connect to others with similar degree
r = 0 → Neutral: no correlation
r < 0 → Disassortative: high-degree nodes connect to low-degree nodes
How it’s computed:
For each edge, define two vectors:
Source degrees
Target degrees
Compute Pearson correlation between these vectors
Reflects the structural tendency of a network to connect similar or dissimilar nodes.
Example: Manual Assortativity calculation
`
Example: Code Assortativity calculation
import networkx as nximport matplotlib.pyplot as pltG = nx.Graph()G.add_edges_from([(1,2),(1,4),(1,5),(2,4),(3,4),(3,5)])nx.draw(G, with_labels=True,# labels=labels, node_color='blue', width=3, node_size=500, font_color='white', font_size=18, )print(nx.degree_assortativity_coefficient(G))
-0.3333333333333304
Triangles
Triangles: Friend of a Friend
In a social network, if Alice and Bob are both friends of Charlie’s, then they are also likely to be friends of each other. (i.e. they form a triangle)
This is a three-body effect, and is a common phenomenon in social networks.
A triangle is a triad (set of three nodes) where each pair of nodes is connected.
Closer look at triangles
A triangle forms when three nodes are mutually connected (i.e., A is connected to B, B to C, and C to A)
Why Triangles Matter:
Represent strong local clustering
Capture friend-of-a-friend relationships
Indicate community cohesion and trust
Related Concepts:
Clustering Coefficient:
Measures how often a node’s neighbors are also connected
High clustering implies many local triangles
Transitivity:
Global measure of triangle density across the entire network
Reflects overall tendency for triadic closure
Real-World Relevance:
Social networks tend to form many triangles due to shared interests, mutual acquaintances, or trust reinforcement
Nodal Clustering Coefficient
Measures how tightly connected a node’s neighbors are
Defined as the fraction of neighbor pairs that are connected (i.e., form triangles)
Formula:
\[
C(i) = \frac{2 \tau(i)}{k_i(k_i - 1)}
\]
\(\tau(i)\): number of triangles involving node \(i\)
\(k_i\): degree of node \(i\)
\(\binom{k_i}{2}\): total possible neighbor pairs
\(C(i)\) is only defined for \(k_i > 1\)
Example clustering coefficient calculation
\[
C(i) = \frac{2 \tau(i)}{k_i(k_i - 1)}
\]
\(\tau(i)\): number of triangles involving node \(i\)
\(k_i\): degree of node \(i\)
\(\binom{k_i}{2}\): total possible neighbor pairs
Network-Level Clustering Coefficient
Measures the overall tendency of a network to form triangles
High clustering (close to 1): many closed triangles (common in social networks)
Example: Co-authorship networks often have \(C > 0.5\)
Network Connectivity
Connected Networks
A connected network is a network where there is a path between any two nodes.
The connectedness defines many properties of a network’s physical structure.
Examples:
In NetworkX we can use the is_connected function to check if a network is connected.
Recall Density
Connectedness & Components (island)
A disconnected network has more than one connected component (or “island”)
A component is a subset of nodes where every node is reachable from every other (in some sense)
Giant Connected Component (GCC):
The largest connected component in a network
In many real-world graphs, it includes a majority of nodes
In a fully connected network, the GCC is the entire graph
Connectedness in Directed Graphs:
In the directed case, we have to pay attention to linkdirections when determining whether a node can be reached from another.
Weakly Connected:
Connectivity exists when ignoring direction of edges
Strongly Connected:
There is a directed path in both directions between every pair of nodes
NetworkX: Identifying connected components
NetworkX provides functions to identify the connected components of a network.
Distances in Disconnected Networks
Option 1: Focus only on nodes in the Giant Connected Component (GCC)
Option 2: Compute distances within each component, then average over all connected pairs
Diameter:
Calculate the diameter of each component
Final network diameter = maximum of all component diameters
Useful when analyzing real-world networks that are not fully connected.
Trees in Network Science
A tree is an undirected, connected graph with no cycles
No Cycles: No closed loops or circular paths
For \(n\) nodes, a tree has exactly \(n - 1\) edges
There is a unique path between any pair of nodes
Hierarchical: any node can be chosen as a root
Edge Critical:
Adding an edge creates a cycle
Removing an edge disconnects the tree
Trees are hierarchical, meaning you can pick any node in a tree to act as a root.
NetworkX has algorithms to determine whether a network is a tree.
Hubs and small worlds
Six Degrees of Separation
The six degrees expression arose from an experiment conducted by psychologist Stanley Milgram in the 1960s, which provided the empirical evidence of “small worlds”
Mailed letters to randomly selected individuals, asking them to forward the letter to a target person using only personal contacts
Result: Most letters reached the target in about 6 steps, giving rise to the idea of “six degrees of separation”
Small worlds phenomenon
A small world network is a network where the average distance between any two nodes is small.
Most social networks have very short paths among nodes, i.e. you are likely to know someone who knows someone who knows someone…
A small world is the popular notion that social distances are short (on average)
Examples of small world networks
Co-Authorship Networks
A well-studied type of social collaboration network
Nodes: Scholars
Edges: Co-authored papers (data mined from digital libraries)
Ego Sub-Networks
A node (the ego) and its immediate neighbors
Useful for analyzing local collaboration patterns
The Erdős Number
Paul Erdős: prolific mathematician and central figure in co-authorship networks
A scholar’s Erdős number = shortest path to Erdős
Many scholars have low Erdős numbers, reflecting short paths in the network
Collaboration networks typically show small-world properties: short average path lengths between any two nodes
Definition of “short” depends on network size
We say that the average path length is “short” when it grows very slowly with the size of the network
We can express slow growth mathematically by saying that the average path length scales logarithmically with the size of the network:
\[
\langle\ell\rangle \sim \log N
\]
The logarithm of \(a\) in base \(b, \log _b a\), is the exponent \(c\) such that \(b^c=a\). Base \(b=10\) is commonly used; \(\log _{10} 10=1\) because \(10^1=10, \log _{10} 100=2\) because \(10^2=100\), \(\log _{10} 1000=3\), etc. The logarithm is therefore a function that grows very slowly.
Hubs
Hub: A center around which other things revolve or from which they radiate; a focus$ of activity, authority, commerce, transportation, etc.
Example:
Centrality Distributions and Heterogeneity
Recall: Centrality measures
Statistical approach
Centrality Distributions in Networks: To understand how centrality is distributed in large networks, we use statistical approaches
Why It Matters:
The range of the distribution reveals heterogeneity
Example: Node degrees spanning from 1 to millions indicate a highly heterogeneous network
Applications:
Helps identify sub-networks or node classes
Example: Group nodes by similar degree centrality
Focus shifts from individual nodes to patterns across the network
Centrality distributions reveal structure and inequality in node importance
Centrality distributions
A centrality distribution is the distribution of centrality values across all nodes in a network.
Degree distribution
Average degree
Power-law distributions
Many real-world networks (e.g., social, biological, internet) exhibit power law degree distributions
Implications:
Most nodes have few links, but a few have very high degree (hubs)
Networks are robust to random failure, but vulnerable to targeted attacks
Reflects self-organizing and scale-free structure
Power laws reveal the presence of inequality, hierarchy, and resilience in complex networks
Scale free (heterogenious) networks
A scale-free network is a network whose degree distribution follows a power law, at least asymptotically.
That is, the fraction \(P(k)\) of nodes in the network having \(k\) connections to other nodes goes for large values of \(k\) as
\[
P(k) \sim k^{-\gamma}
\]
where \(\gamma\) is a parameter whose value is typically in the range \(2<\gamma<3\)
Degree distribution for a network with 150000 vertices and mean degree created using the Barabási-Albert graph generator
Scale free networks: Video
Heterogeneity parameter
Heterogeneous networks present a wide variability in the properties and roles of their elements nodes and/or links. (Non-uniform distribution of network properties)
One way to measure the breadth of the degree distribution is to compute the heterogeneity parameter, which compares the variability of the degree across nodes to the average degree.
Examples
Summary
Assortativity measures how likely nodes are to connect to others with similar properties, such as degree or attributes, often reflecting homophily or social influence.
Paths are sequences of links between nodes; the shortest path defines the distance between nodes, and can be found using algorithms like breadth-first search.
A tree is a connected, cycle-free network with the minimum number of links.
Connected components are subnetworks where any two nodes are connected; in directed networks, components can be strongly or weakly connected.
Average path length is the mean shortest distance between all node pairs in a connected network, or within components if disconnected.
Small-world property describes networks where most nodes are separated by only a few steps, as in “six degrees of separation.”
Clustering refers to the tendency of nodes to form tightly-knit groups (triangles); the clustering coefficient quantifies this, and is typically high in social networks.
Social Influence
In some sense, social influence is the opposite of homophily, i.e. dissimilar nodes with existing connections becoming similar over time, rather than similar nodes forming connections (homophily).
Examples: