Understanding Node Similarity and its Uses

What is Node Similarity?

In network analysis, node similarity measures how alike two nodes are with respect to their position and role within a network. Similarity can be based on several criteria, including shared neighbours, network connectivity, or local structural patterns. In graphlet analysis, node similarity is typically assessed by comparing the Graphlet Degree Vectors (GDVs) of nodes.

A Graphlet Degree Vector records how many times a node participates in each graphlet orbit. Nodes with similar orbit counts are considered structurally similar because they occupy comparable positions within their local neighbourhoods.

For example:

Nodes A and B have similar orbit profiles and are therefore more structurally similar than either is to Node C.

Measuring Node Similarity

Node similarity is often calculated by computing a distance or similarity measure between the graphlet vectors of two nodes. Common measures include:

• Euclidean Distance
• Manhattan Distance
• Cosine Similarity
• Graphlet Degree Vector Distance (GDVD)

A small distance indicates high similarity, while a large distance indicates that the nodes participate in very different local structures.

Why is Node Similarity Important?

Identifying Functional Equivalence

Nodes located in different parts of a network may perform similar structural functions. For example, two individuals from different departments may both act as coordinators within their respective groups.

Detecting Hidden Relationships

Traditional network analysis often focuses on direct connections. Node similarity can reveal relationships between nodes that have no direct link but possess highly similar structural characteristics.

Discovering Roles in a Network

Structural similarity helps identify nodes serving as:

• Hubs
• Brokers
• Gatekeepers
• Peripheral members
• Community leaders

Nodes with comparable graphlet signatures often fulfil similar network roles.

Community and Group Analysis

Similarity measures can be used to cluster nodes into groups with shared structural characteristics, helping analysts identify meaningful subpopulations within a network.

Anomaly Detection

Nodes with orbit profiles that differ substantially from others may represent:

• Outliers
• Exceptional performers
• Vulnerable points
• Unusual actors

Such nodes can be investigated further to understand their significance within the network.

Applications Across Domains

Social Networks

Identify individuals with similar influence patterns, leadership roles, or brokerage positions, even if they belong to different social groups.

Biological Networks

In protein-protein interaction networks, proteins with similar graphlet signatures often exhibit similar biological functions.

Citation Networks

Researchers occupying comparable positions within scientific collaboration or citation structures can be identified through node similarity analysis.

Organizational Networks

Employees with similar communication and collaboration patterns can be discovered, revealing informal organizational structures

From Transactions to Structural Similarity

Traditional transaction analysis focuses on examining direct relationships between accounts. For example, a transaction network (graph) can be constructed from the transaction dataset as shown below based on the the IBM AML dataset that we used and detailed in one of the previous articles. Click here for the article…

library(igraph)
edges <- read.csv("motif_analysis/transactions_edges_full_small.csv")
g <- graph_from_data_frame(
  edges[, c("sender_account_id", "receiver_account_id")],
  directed = TRUE
)

The graph object constructed from a transaction dataset allows us to investigate metrics such as degree, betweenness centrality, and shortest path lengths.

However, the measures mentioned above looks at direct connectivity between nodes and does not reveal whether two nodes (accounts in the above graph) play similar roles within the network. Figure 1 explains the point: “Degree, betweenness and shortest paths measure connectivity, but not whether nodes occupy similar structural roles.”

Although A and X belong to different regions of the network and may never interact directly, they occupy nearly identical structural positions. Both serve as the centre of a similarly organized local neighbourhood. Traditional measures focus on connectivity and distance, whereas graphlet analysis focuses on structural role. As a result, A and X may have a very small orbit distance despite being far apart in the network.

This helps readers understand that graphlets answer a different question:

• Traditional network metrics: How close are these nodes?
• Graphlet analysis: How similar are these nodes?

Graphlet analysis addresses this limitation by describing each node using its participation across graphlet orbits. But before graphlet analysis, we will look into a few other similarity measures.

Jaccard Similarity

Jaccard similarity measures the overlap of neighbours. Two nodes are similar if they connect to many of the same nodes. From the previous graph, we can extract similar nodes:

Example

Suppose:

A → {X, Y, Z} and B → {Y, Z, W}

Then : Shared neighbours = {Y, Z} = 2 . And all neighbours = {X,Y,Z,W} = 4. So, Jaccard Similarity J is:

sim <- similarity(g, method = "jaccard")

g_top50 <- induced_subgraph(g,names(sort(degree(g), decreasing = TRUE))[1:50])
sim <- similarity(g_top50, method = "jaccard")
# Convert matrix to edge list
sim_df <- as.data.frame(as.table(sim))
names(sim_df) <- c("from", "to", "weight")
# Remove self-links
sim_df <- sim_df[sim_df$from != sim_df$to, ]
# Keep only strong similarities
sim_df <- subset(sim_df, weight > 0.3)
g_sim <- graph_from_data_frame(sim_df, directed = FALSE)
plot(
g_sim, 
vertex.size = 10, 
vertex.label.cex = 0.7,
  edge.width = E(g_sim)$weight * 2
)

The plot connects similar nodes. The width of the edges is proportional to the similarity observed between the codes.

There are other similarity metrics such as “Euclidean” and “Cosine” as well.

Node Similarity Using Orbit Counts

Node similarity derived from graphlet orbit counts provides a powerful way to compare nodes based on structural role rather than direct connectivity. This allows researchers to identify functionally equivalent nodes, uncover hidden patterns, detect anomalies, and better understand the organization of complex networks. Graphlet-based node similarity is particularly valuable because it captures rich local structural information that simpler metrics such as degree or shortest path distance often miss.

In the first section of this article, we already discussed the orbit count and how the node-orbit matrix contains a structural footprint for every node. Extending this further, we can calculate similarity between orbit vectors using distance metrics.

Calculating Orbit Distance

A simple approach is to calculate Euclidean distance between orbit vectors.

orbit_dist <- dist(
  orbit_counts,
  method = "euclidean"
)
orbit_dist[1:5]

The distance between nodes $i$i and $j$j is:$$d(i,j)= \sqrt{ \sum_{k=0}^{72}(O_k^i-O_k^j)^2 }$$

where $O_k$​ represents the count for orbit k. Here, smaller values indicate greater structural similarity

Finding the Most Similar Accounts

Convert the distance matrix:

dmat <- as.matrix(orbit_dist)
dmat[1:5,1:5]

Find accounts most similar to account 7:

similarities <- sort(dmat[7, ])
head(similarities, 10)
       7      125      180      333      525      457
 0.00000  0.00000  0.00000  0.00000  0.00000 12.24745

7 -> distance = 0 is expected because it is the distance from node 7 to itself. The other more interestingly:

125 -> distance = 0
180 -> distance = 0
333 -> distance = 0
525 -> distance = 0

means these nodes have identical orbit vectors. Node 7 was found to have an orbit distance of zero from nodes 125, 180, 333, and 525. Although these accounts may be located in entirely different parts of the transaction network, they participate in exactly the same graphlet orbit patterns. From a graphlet perspective, these nodes are structurally equivalent.

Identifying clusters (communities)

Orbit vectors can be used to cluster nodes with similar behaviour.

orbit_subset <- orbit_counts[1:50, ] # take only a subset
orbit_dist <- dist(orbit_subset, method = "euclidean" )
hc <- hclust(orbit_dist, method = "ward.D2")
plot(hc)

This produces groups of accounts exhibiting similar local topological patterns as in Figure

Unlike community detection, which groups nodes that are densely connected, orbit-based clustering groups nodes that perform similar functions.

Why Graphlet Similarity Matters in Financial Networks

In transaction networks, fraudulent accounts frequently attempt to hide or disguise themselves by avoiding direct relationships with known fraudulent actors. Traditional graph metrics may fail to identify these accounts.

Graphlet analysis approaches the problem differently. Rather than examining who an account transacts with, it examines how the account is embedded within the surrounding topology. Two accounts may never transact with each other, yet show nearly identical graphlet signatures. Such accounts may be participating in the same operational pattern, acting as hubs, collectors, brokers, or members of a money-laundering structure.

This makes graphlet-based node similarity particularly useful for fraud detection, typology discovery, anomaly detection, and behavioural segmentation.