Topological properties of graphs

Sep 29^th 2026

BMI/CS 775 Computational Network Biology�Fall 2026

Sushmita Roy

https://bmi775.sites.wisc.edu

These slides, excluding third-party material, are licensed under CC BY-NC 4.0 by Sushmita Roy and Anthony Gitter

Plan for the semester

2

*Includes Deep Learning in Network Biology

Plan for this section

• Topological properties of networks (Sep 29^th )

​

• Graph clustering (Sep 29^th, Oct ^1st)

Goals for today

• Commonly measured network properties
• Degree distribution
• Average shortest path length
• Network motifs
• Clustering coefficient
• Modularity of biological networks

​

• Algorithms to find modules on graphs
• Clustering
• Girvan Newman algorithm

Why should we care about network properties?

• Are there specific properties that characterize real world networks?
• How can we generate networks with such properties?

​

“Probably the most important discovery of network theory was the realization that despite the remarkable diversity of networks in nature, their architecture is governed by a few simple principles that are common to most networks of major scientific and technological interest” Barabasi and Oltvai, Nature Genetics Review 2004

Commonly measured network properties

• Degree distribution
• Average shortest path length
• Network motifs
• Clustering coefficient
• Modularity of biological networks

​

Recall node degree

• Undirected network
• Degree, k: Number of neighbors of a node
• Directed network
• In degree, k_in: Number of incoming edges
• Out degree, k_out: Number of outgoing edges

​

​

​

​

​

Average degree

• Consider an undirected network with N nodes
• Let k_i denote the degree of node i
• Average degree is

​

​

​

​

​

​

​

​

​

​

Degree distribution

• P(k) the probability that a node has k edges
• Different networks can have different degree distributions
• A fundamental property that can be used to characterize a network

Different degree distributions

• Poisson distribution
• The mean is a good representation of k_i of all nodes
• Networks generated using the “Erdös Renyi” random model have a Poisson degree distribution
• Power law distribution
• Also called scale free
• There is no “typical” node that captures the degree of nodes.

Poisson distribution

• A discrete distribution

​

​

​

• The Poisson is parameterized by which can be easily estimated by maximum likelihood

​

​

​

​

​

k

P(X=k)

Power law distribution

• Used to capture the degree distribution of real networks

​

​

​

• A value of between 2 and 3 is observed in some real-world networks.

​

• MLE exists but is more complicated
• See Power-Law Distributions in Empirical Data. Clauset, Shalizi and Newman, 2009 for details

P(k)

k

Barabasi and Oltvai, Nature Genetics Review 2004

Erdös Renyi random graphs

• Dates back to 1960 due to two mathematicians Paul Erdös and Alfred Renyi.
• Provides a probabilistic model to generate a graph
• Starts with N nodes and connects two nodes with probability p
• Node degrees follow a Poisson distribution
• Tail falls off exponentially, suggesting that nodes with degrees different from the mean are very rare

Example Erdos-Renyi graphs

Courtesy: Spencer Halberg, Erika Da-Inn Lee

n: # of nodes, p: prob of an edge

p=0.05

p=0.1

p=0.25

p=0.4

Scale free networks

• Degree distribution is captured by a power law distribution
• There is no “typical” node that describes the degree of all other nodes
• Many real-world networks were originally thought to have a power law distribution and considered scale-free

Poisson versus Scale free

Barabasi & Oltvai 2004, Nature Genetics Review

Yeast protein interaction network is believed to be scale free

• “Whereas most proteins participate in only a few interactions, a few participate in dozens”

​

• Such high degree nodes are called hubs

Barabasi & Oltvai 2004, Nature Genetics Review

Degree of a node is correlated to functional importance of a node

• Hubs maybe associated with important biological function
• Red nodes on deletion cause the organism to die
• Red nodes also among the nodes with the highest degree

​

​

Yeast PPI network degree distribution

5,905 nodes

86,286 edges

Origin of scale free networks

• Scale free property often observed for networks in the real-world
• How do such networks arise?
• Such networks are the result of two processes
• a growth process where new nodes join the network over an extended period of time
• Think about how the internet has grown
• preferential attachment: new nodes tend to connect to nodes with many neighbors
• Rich get richer.

​

​

Barabasi & Oltvai 2004, Nature Genetics Review

Growth and preferential attachment in scale free networks

A new node (red) is more likely to connect to node 1

than 2

Barabasi & Oltvai 2004, Nature Genetics Review

Example scale free graph creation

Courtesy: Spencer, Erika. Original gif from Harvath Arpad available in Networkx in python

Commonly measured network properties

• Degree distribution
• Average shortest path length
• Network motifs
• Clustering coefficient
• Modularity of biological networks

​

Paths on a graph

C

B

A

D

G

H

E

Path: a set of connected edges from one node to another

Paths from B to D

F

There are two paths from B-D: B->A->D and B->G->H->A->D

Path lengths

• The shortest path length between two nodes A and B:
• The smallest number of edges that need to be traversed to get from A to B
• Mean path length is the average of all shortest path lengths
• Diameter of a graph is the longest of all shortest paths in the network

Scale-free networks tend to be ultra-small

• Two nodes on the network are connected by a small number of edges
• Note: estimated on the “giant connected component” if a graph is disconnected
• Average path length is proportional to log(log(N)), where N is the number of nodes in the network
• In a random network (Erdös Renyi network) the average path length is proportional to log(N)

Yeast protein interaction network

Avg. path length: 2.6

​

Diameter: 6

​

Nodes: 5,905

​

Edges: 86,286

​

Are scale free networks ubiquitous?

• Large diverse corpus of 928 networks
• Examined other distributions such as Log-normal and Exponential

Broido, A. D. & Clauset, A. Scale-free networks are rare. Nat Commun 10, 1017 (2019).

Are scale free networks ubiquitous?

• Examined other distributions such as Log-normal and Exponential
• Classified networks into more categories of scale-freeness
• Found many networks exhibit a log-normal distribution

​

Broido, A. D. & Clauset, A. Scale-free networks are rare. Nat Commun 10, 1017 (2019).

Top Hat Question

Commonly measured network properties

• Degree distribution
• Average shortest path length
• Network motifs
• Clustering coefficient
• Modularity of biological networks

​

Network motifs

• Network motifs:
• small recurring subgraphs that occur much more than a randomized network
• Often called “building blocks” of complex networks
• Biological networks tend to exhibit certain types of network motifs
• Some motifs are associated with specific network dynamics

​

Milo Science 2002

Network motifs of size 3 in a directed network

Additional possibilities if we consider the sign of an edge

Milo Science 2002

Different types of feed-forward motifs

Coherent: sign of the direct path is the same as the indirect path

Incoherent: sign of the direct path and indirect path are not the same

Alon 2007, Nature Review Genetics

Network motifs are associated with dynamics

A feed-forward motif with an AND gate can encode a sign sensitive delay

Alon 2007, Nature Review Genetics

Network motifs found in many complex networks

The occurrence of the feed-forward loop in both networks suggests a fundamental similarity in the design on these networks

Milo et al., Science 2002

How to find network motifs?

• Given an input network G we need to address two problems
• Subgraph enumeration: Find which subgraphs occur in G and how many times
• Significance of the number of occurrences: Compare to the number of occurrences of subgraphs in randomized networks
• Requires checking for subgraph isomorphism
• Software to find network motifs
• FANMOD: a tool for fast network motif detection http://bioinformatics.oxfordjournals.org/content/22/9/1152.full

​

Wernicke 2005: Pages 165-177 https://link.springer.com/content/pdf/10.1007/11557067.pdf

Generating a randomized network

• While an Erdös Renyi network is random, it does not have the same degree distribution as a given network
• How to generate a randomized network with the same degree distribution?

Strategy to generate randomized networks (Switching method)

1

2

3

4

5

1

2

3

4

5

Select two edges connecting four vertices and swap the end points.

Repeat.

Milo, R., Kashtan, N., Itzkovitz, S., Newman, M. E. J. & Alon, U. On the uniform generation of random graphs with prescribed degree sequences. at http://arxiv.org/abs/cond-mat/0312028 (2004).

Strategy to generate randomized network (Matching method)

Adapted from Jure Leskovec slides on “Machine learning with graphs”

A

B

C

D

Nodes with spokes

Randomly pair up spokes

Resulting graph

Assessing the significance of a network motif

The motif (red dashed edges) occurs much more frequently in the real network than

in any randomized network

Commonly measured network properties

• Degree distribution
• Average shortest path length
• Network motifs
• Clustering coefficient
• Modularity of biological networks

​

Clustering coefficient

• Measure of transitivity in the network that asks
• If A is connected to B, and B is connected to C, how often is A connected to C?
• Clustering coefficient C_i for each node i is

​

​

​

• k_i Degree of node i
• n_i is the number of edges among neighbors of i
• Average clustering coefficient gives a measure of local neighborhood connectivity

A

B

C

?

Clustering coefficient example

A

C

B

G

D

Commonly measured network properties

• Degree distribution
• Average shortest path length
• Network motifs
• Clustering coefficient
• Modularity of biological networks

​

Resuming on Oct 21^st, 2025

Modularity in networks

• Modularity “refers to a group of physically or functionally linked nodes that work together to achieve a distinct function” -- Barabasi & Oltvai
• Modularity is an important principle of biological systems
• Genes tend to interact with a select set of other genes exhibiting a clustering of interactions
• Module detection can help to
• Understand the organizational properties of the network
• Can be used to predict function of genes based on their grouping behavior

A modular network

Module 1

Module 2

Module 3

M. E. J. Newman, Modularity and community structure in networks, PNAS 2006

Different types of network modules

• Topological modules
• Defined solely based on the graph connectivity of nodes
• Functional modules
• Based on graph connectivity & other node attributes
• Can be further grouped into
• Active modules
• Integrative modules
• Disease modules

​

​

Albert-László Barabási, Natali Gulbahce, and Joseph Loscalzo, Nature Review Genetics 2011, Mitra et al., Nature Review Genetics 2014

Studying modularity in biological systems

• Given a network is it modular?
• Q Modularity: measures the relative density of edges between and within the groups
• Given a network what are the modules in the network?

Q measure for modularity

• Suppose the nodes in the graph belong to K groups (communities)
• Modularity (Q) can be assessed as follows:
• difference between within group (community) connections and expected connections within a group
• This measure assess how good a particular grouping is

​

K: number of groups

e_ij: Fraction of total edges that link nodes in group i to group j

Detecting community structure in networks. M.E. J Newman

Fraction of edges within group i

Fraction of edges without regard to community structure

Summary of topological properties of networks

• Given a network, its topology can be characterized using different measures
• Degree distribution
• Average path length
• Clustering coefficient (also used to measure modularity of a network)
• Degree distribution can be
• Poisson
• Power law
• Network motifs
• Building blocks of complex networks
• Over-represented subgraphs of specific types
• Clustering coefficient
• Transitivity/local neighborhood density
• Network modularity
• Q modularity

​

Goals for today

• Commonly measured network properties
• Degree distribution
• Average shortest path length
• Network motifs
• Clustering coefficient
• Modularity of biological networks

​

• Algorithms to find modules on graphs
• Clustering
• Girvan Newman algorithm

Problem definition of (topological) module detection

• Given:
• A graph
• A measure of cluster quality
• Do
• Partition the vertices into groups such that they form densely connected subgraphs (e.g. as measured by the cluster quality)

Common graph clustering algorithms

• Hierarchical or flat clustering using a notion of similarity between nodes
• Girvan-Newman algorithm
• Hierarchical Agglomerative clustering
• Spectral clustering
• Stochastic block models
• Markov clustering algorithm
• Affinity propagation
• Louvain clustering

​

Please review Clustering slides at the end of this presentation if needed.

Community structure in a graph

• A graph that has a grouping (community) structure is going to have few intercommunity edges.
• Community structure can be revealed by removing such intercommunity edges

Detecting community structure in networks, M. E. J. Newman

Communities

Intercommunity edges

Girvan-Newman algorithm

• General idea: “If two communities are joined by only a few inter-community edges, then all paths through the network from vertices in one community to vertices in the other must pass along one of those few edges.”
• Community structure can be revealed by removing edges that with high betweenness
• Algorithm is based on a divisive clustering idea

M. E. J. Newman and M. Girvan. Finding and evaluating community structure

​

Betweenness of an edge

• Betweenness of an edge e is defined as the number of shortest paths that include e
• Edges that lie between communities tend to have high betweenness

Girvan-Newman algorithm

• Initialize
• Compute betweenness for all edges
• Repeat until convergence criteria
1. Remove the edge with the highest betweenness
2. Recompute betweenness of remaining edges

​

• Convergence criteria can be
• No more edges
• Desired modularity

M. E. J. Newman and M. Girvan. Finding and evaluating community structure

​

Girvan-Newman algorithm as a hierarchical clustering algorithm

• One can view this algorithm as a top-down (divisive) hierarchical clustering algorithm
• The root of the dendrogram groups all nodes into one community
• Each branch of the tree represents the order of splitting the network as edges are removed

​

​

Graph vertices

where clustering is good enough

Zachary’s karate club study

• A well-known example of a social network with community structure
• Dataset collected by Wayne Zachary over 2 years who observed social interactions among members of a karate club
• Due to a dispute the club split into two factions
• Can a graph clustering/module detection algorithm predict the factions?

Each node is an individual and edges represent social interactions among individuals. The shape and colors represent different groups.

Girvan Newman on Zachary’s karate club dataset

Each node is an individual and edges represent social interactions among individuals. The shape and colors represent different groups.

Node grouping based on betweenness

Modularity

References

• A.-L. Barabasi and Z. N. Oltvai, "Network biology: understanding the cell's functional organization," Nature Reviews Genetics, vol. 5, no. 2, pp. 101-113, Feb. 2004. [Online]. Available: http://dx.doi.org/10.1038/nrg1272
• R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, "Network motifs: Simple building blocks of complex networks," Science, vol. 298, no. 5594, pp. 824-827, Oct. 2002. [Online]. Available: http://dx.doi.org/10.1126/science.298.5594.824
• U. Alon, "Network motifs: theory and experimental approaches," Nature Reviews Genetics, vol. 8, no. 6, pp. 450-461, Jun. 2007. [Online]. Available: http://dx.doi.org/10.1038/nrg2102
• S. Wernicke and F. Rasche, "FANMOD: a tool for fast network motif detection," Bioinformatics, vol. 22, no. 9, pp. 1152-1153, May 2006. [Online]. Available: http://dx.doi.org/10.1093/bioinformatics/btl038
• M. E. J. Newman and M. Girvan. “Finding and evaluating community structure in networks”, 2003, 10.1103/PhysRevE.69.026113
• M. E. J. Newman, "Modularity and community structure in networks," Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577-8582, Jun. 2006. [Online]. Available: http://dx.doi.org/10.1073/pnas.0601602103
• A. Clauset, C. R. Shalizi, and M. E. J. Newman, "Power-law distributions in empirical data," SIAM Review, vol. 51, no. 4, pp. 661-703, Feb. 2009. [Online]. Available: http://dx.doi.org/10.1137/070710111
• Broido, A.D., Clauset, A., 2019. Scale-free networks are rare. Nat Commun 10, 1017. https://doi.org/10.1038/s41467-019-08746-5

​

​

​

​

​

​

​

Neural Subgraph Matching

Rex et al. Neural Subgraph Matching. at http://arxiv.org/abs/2007.03092 (2020).

• GNN based framework for the subgraph isomorphism problem
• Based on embedding node neighborhoods as subgraphs
• Could be used for motif counting as an additional application

Subgraph isomorphism

https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

Algorithm for enumerating subgraphs: Edge sampling

N(V’): set of neighbors of all vertices in V’

Kashtan et al., Bioinformatics 2004