Code
-0.3333333333333304
Structure property relationship: In network science, the structure of a network often relates to its properties.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.
Birds of a feather flock together
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.
*“Birds of a feather flock together.”
Examples: People with similar beliefs, professions, or cultural backgrounds often become friends.
Consequences:
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:
The dynamic interplay between homophily and influence shapes the structure and evolution of social networks.
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:
Interpretation:
Importance:
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.
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.
Given two vectors of equal length, you can compute the extent to which their values covary with each other
For each edge, define two vectors:
Compute Pearson correlation between these vectors
Reflects the structural tendency of a network to connect similar or dissimilar nodes.
`
-0.3333333333333304
Clustering Coefficient:
Transitivity:
\[ C(i) = \frac{2 \tau(i)}{k_i(k_i - 1)} \]
\(C(i)\) is only defined for \(k_i > 1\)
\[ C(i) = \frac{2 \tau(i)}{k_i(k_i - 1)} \]
\[ C = \frac{\sum_{i: k_i > 1} C(i)}{N_{k > 1}} \]
Example: Co-authorship networks often have \(C > 0.5\)
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.
In NetworkX we can use the is_connected function to check if a network is connected.

Giant Connected Component (GCC):
In the directed case, we have to pay attention to linkdirections when determining whether a node can be reached from another.

NetworkX provides functions to identify the connected components of a network.
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:
Useful when analyzing real-world networks that are not fully connected.
A tree is an undirected, connected graph with no cycles
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:
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.

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”


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)
Co-Authorship Networks
Ego Sub-Networks
The Erdős Number
Collaboration networks typically show small-world properties: short average path lengths between any two nodes
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.
Hub: A center around which other things revolve or from which they radiate; a focus$ of activity, authority, commerce, transportation, etc.

Example:

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
Applications:
Helps identify sub-networks or node classes
Centrality distributions reveal structure and inequality in node importance
A centrality distribution is the distribution of centrality values across all nodes in a network.
Many real-world networks (e.g., social, biological, internet) exhibit power law degree distributions
Implications:
Power laws reveal the presence of inequality, hierarchy, and resilience in complex networks
\[ P(k) \sim k^{-\gamma} \]
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.
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: