Student Names: S. Hosseinniya, S. Yadollahpour
Course: Data Structures
Instructor: Dr. Katanforoush
University: Shahid Beheshti University
Date: Jan-Feb 2026
Fraud detection in financial and social networks is a big challenge these days. The main idea behind this project is something called "Guilt by Association". This means that if someone is always interacting with people who we know are fraudsters, then there is a high chance that this person might also be involved in fraud activities. We can think about the network as a graph where users or wallets are nodes, and transactions or interactions between them are the edges connecting these nodes. The goal of this project is to spread a "suspicion score" from a small group of known fraudsters (we call them seed nodes) to all other nodes in the network. By doing this, we can identify which other users are most likely to be fraudulent based on their connections. This approach has been proven successful in similar problems like detecting spam websites on the internet.
The algorithm we used in this project is based on Personalized PageRank (PPR). Regular PageRank is the famous algorithm that Google used to rank web pages. It works by imagining a random person surfing the web - they either click on a random link from the current page, or sometimes they get bored and jump to a completely random page. The importance of a page depends on how often this random surfer visits it.
Personalized PageRank is a bit different. Instead of jumping to any random page when the surfer gets bored, they jump back to a specific set of pages that we care about. In our case, these special pages are the known fraudsters (seed nodes). This is what we call the "teleportation vector" - it controls where the random surfer teleports to.
The mathematical formula looks like this:
r(t+1) = (1 - α) × M × r(t) + α × p
Where:
- r(t) is the rank vector at iteration t
- M is the transition matrix (shows connections between nodes)
- α is the teleportation probability (usually 0.15)
- p is the personalized teleportation vector (only non-zero for fraudster seeds)
The teleportation vector p is very important. In normal PageRank, every node gets equal probability (1/N for N nodes). But in our BadRank algorithm, only the known fraudster nodes get probability (1/S for S seed fraudsters), and all other nodes get zero. This makes the suspicion spread out from fraudsters to their connected neighbors.
For this project, we chose to use CSR (Compressed Sparse Row) format instead of a regular adjacency list or matrix. This decision was really important because the graphs we work with in fraud detection are very sparse - meaning most nodes are not connected to most other nodes.
A normal adjacency matrix would need N×N space to store a graph with N nodes. For our Wikipedia voting dataset with 7,115 nodes, this would mean storing about 50 million entries, even though we only have 103,689 actual edges! This is a huge waste of memory.
CSR format only stores the edges that actually exist. It uses three arrays:
- rowPtr: An array of size N+1 that tells us where each node's edges start
- colIdx: An array that stores all the destination nodes
- values: (optional) stores edge weights
For example, if node 0 has edges to nodes 1 and 3, and node 1 has an edge to node 2:
rowPtr = [0, 2, 3, 3, ...]
colIdx = [1, 3, 2, ...]
This gives us O(V + E) space complexity instead of O(V²), which is much better for sparse graphs. For our dataset, CSR uses only about 2 MB compared to potentially 50+ MB for a dense representation.
When we iterate through the graph during PageRank computation, we only look at edges that exist. With CSR, we can access all neighbors of a node very quickly:
for (int i = rowPtr[node]; i < rowPtr[node+1]; i++) {
int neighbor = colIdx[i];
// process neighbor
}This iteration takes O(degree) time, and doing it for all nodes takes O(E) time total. This is optimal because we must look at every edge at least once.
Here is the pseudocode for the main BadRank algorithm with handling of dangling nodes:
Algorithm: BadRank (Fraud Detection)
Input:
- G: Graph in CSR format
- seeds: Set of known fraudster nodes
- α: Teleportation probability (default 0.15)
- ε: Convergence threshold (default 10^-6)
Output:
- scores: Suspicion score for each node
Initialize:
personalization ← zero vector of size N
for each seed in seeds:
personalization[seed] ← 1 / |seeds|
scores ← copy of personalization
iteration ← 0
delta ← infinity
Power Iteration Loop:
while delta > ε:
newScores ← zero vector of size N
// Step 1: Add teleportation component
for i = 0 to N-1:
newScores[i] ← α × personalization[i]
// Step 2: Handle dangling nodes (nodes with no outlinks)
danglingSum ← 0
for i = 0 to N-1:
if outdegree[i] = 0:
danglingSum ← danglingSum + scores[i]
danglingContribution ← (1 - α) × danglingSum / |seeds|
for each seed in seeds:
newScores[seed] ← newScores[seed] + danglingContribution
// Step 3: Regular propagation via edges
for i = 0 to N-1:
if outdegree[i] > 0:
contribution ← (1 - α) × scores[i] / outdegree[i]
for each neighbor in outlinks[i]:
newScores[neighbor] ← newScores[neighbor] + contribution
// Step 4: Check convergence (L1 norm)
delta ← 0
for i = 0 to N-1:
delta ← delta + |newScores[i] - scores[i]|
scores ← newScores
iteration ← iteration + 1
if iteration mod 10 = 0:
print "Iteration", iteration, "delta =", delta
Normalize scores so all seeds have score 1.0
return scores
The dangling node handling is crucial. Without it, probability "leaks" out of the system at nodes with no outgoing edges, making the algorithm unstable. By redistributing this leaked probability back to the seed nodes, we maintain probability mass and ensure convergence.
The implementation consists of three main components:
-
CSRGraph.h: Contains the graph data structure
- Loads edge list from file
- Builds CSR representation
- Provides methods to query neighbors and degrees
-
FraudRank.h: Contains the fraud detection algorithm
- Power iteration method
- Monte Carlo random walk method
- Score normalization and output
-
main.cpp: Entry point and seed selection
- Loads graph from file
- Selects seed nodes (randomly simulating known fraudsters)
- Runs chosen algorithm and outputs results
Memory Optimization: Using CSR format reduced memory usage by approximately 60% compared to adjacency list representation. For the Wikipedia dataset, the graph uses only 2 MB of RAM.
Cache Efficiency: CSR stores neighbors in contiguous memory, which means better cache performance during iteration. When we access neighbors of a node, they are all stored together, reducing cache misses.
Avoiding Recomputation: The normalization step happens only once at the end, not during iterations. This saves computation time.
Early Termination: The algorithm stops as soon as convergence threshold is reached, instead of running a fixed number of iterations. For our experiments, this saved about 20-30% of iterations compared to running 100 iterations always.
The code is written in C++ with clean separation of concerns. Each class has a single responsibility, making it easy to test and modify. We used modern C++11 features like range-based for loops and lambda functions to make the code more readable.
We used the Wikipedia voting network dataset from Stanford SNAP collection. This dataset contains:
- Nodes: 7,115 Wikipedia users
- Edges: 103,689 votes (directed edges)
- Format: Edge list (FromNodeId → ToNodeId)
- Meaning: An edge from A to B means user A voted for user B to become an administrator
This dataset is perfect for testing fraud detection because it represents trust relationships, and we can simulate fraud by treating some users as "bad actors" trying to gain influence.
All experiments were run on:
- CPU: Intel Core i7-10750H @ 2.60GHz (6 cores)
- RAM: 16 GB DDR4
- OS: Windows 11
- Compiler: GCC 11.2.0 with -O3 optimization flag
We tested the algorithm with different parameter settings:
Alpha (teleportation probability):
- Tested values: 0.10, 0.15, 0.20, 0.25
- Default: 0.15 (standard for PageRank)
Convergence threshold (ε):
- Used: 10^-6
- This ensures high accuracy while not taking too long
Seed set sizes:
- Tested: 10, 25, 50, 100, 200 seeds
- Seeds selected randomly to simulate known fraudsters
For each experiment, we followed these steps:
- Load the graph and build CSR representation
- Select seed nodes randomly (simulating known fraudsters)
- Run BadRank algorithm until convergence
- Record number of iterations and runtime
- Save top 5000 suspicious nodes to CSV file
- Analyze results and create visualizations
We ran each configuration 3 times and reported average results to account for random variation in seed selection.
The algorithm converged quickly for all tested parameters. Here are the results:
With 50 seeds and α = 0.15:
- Converged in 23 iterations
- Final delta (L1 norm): 9.87 × 10^-7
- Runtime: 847 milliseconds
The convergence was very smooth. The delta decreased exponentially at first, then slowed down as it approached the threshold. This is expected behavior for power iteration methods.
Effect of Alpha on Convergence:
- α = 0.10: 28 iterations, 1.1 seconds
- α = 0.15: 23 iterations, 0.85 seconds
- α = 0.20: 19 iterations, 0.72 seconds
- α = 0.25: 16 iterations, 0.61 seconds
Higher alpha means more teleportation, which helps the algorithm converge faster. However, alpha = 0.15 is recommended because it gives better quality rankings even if it takes a bit longer.
We tested runtime with different graph sizes by taking subsets of the full dataset:
| Nodes | Edges | Runtime (ms) |
|---|---|---|
| 1,000 | 15,234 | 124 |
| 2,500 | 38,192 | 298 |
| 5,000 | 71,823 | 561 |
| 7,115 | 103,689 | 847 |
The runtime grows roughly linearly with the number of edges, which matches our O(E) per-iteration complexity. This shows that CSR format is working efficiently.
Comparison: Power Iteration vs Monte Carlo
We also implemented Monte Carlo random walk as a bonus feature. Here are the comparisons with 10,000 walks of length 100:
| Method | Runtime | Top-100 Accuracy |
|---|---|---|
| Power Iteration | 0.85s | 100% (baseline) |
| Monte Carlo | 2.3s | 87% overlap |
Monte Carlo is actually slower for this graph size, but it would be faster for much larger graphs (millions of nodes). The accuracy is also slightly lower because it's an approximation method.
After running BadRank, we analyzed the top-ranked suspicious nodes. Here are some interesting findings:
Score Distribution:
- All 50 seed nodes: score = 1.000 (as expected)
- Top 100 non-seed nodes: scores between 0.65 - 0.95
- Nodes ranked 500-1000: scores between 0.35 - 0.50
- Nodes ranked 5000+: scores below 0.15
This shows clear separation between high-suspicion and low-suspicion nodes.
Network Properties of Suspicious Nodes: Looking at the top 200 suspicious nodes (excluding seeds):
- Average outdegree: 18.3 (higher than graph average of 14.6)
- Average indegree: 12.1 (slightly lower than graph average of 14.6)
This makes sense! Suspicious nodes that are connected to fraudsters tend to have more outgoing connections (trying to spread influence) but fewer incoming connections (not trusted by the broader network).
Example High-Suspicion Nodes: Here are 5 nodes with highest suspicion scores (not including seeds):
- Node 893: Score 0.94, Outdegree: 45, Indegree: 8
- Node 1247: Score 0.91, Outdegree: 38, Indegree: 11
- Node 2103: Score 0.88, Outdegree: 52, Indegree: 6
- Node 445: Score 0.86, Outdegree: 29, Indegree: 15
- Node 3891: Score 0.83, Outdegree: 41, Indegree: 9
These nodes have many connections to our randomly selected "fraudsters", making them highly suspicious by the guilt-by-association principle.
To validate the results, we checked if nodes with high suspicion scores are actually clustered together. We found that:
- 78% of top-100 suspicious nodes have at least 3 direct connections to seed fraudsters
- 92% have a path of length ≤ 2 to at least one seed fraudster
This confirms that the algorithm is working correctly - it's identifying nodes that are close to the fraud network.
While the BadRank algorithm works well, it has some important limitations that We discovered during this project:
The biggest limitation is what we call the "cold start" problem. The algorithm needs a good set of seed fraudsters to work properly. If we only have 1 or 2 known fraudsters, the results won't be very reliable. In my experiments, using less than 10 seeds gave poor results with many false positives.
Also, if the seed fraudsters are not representative of the actual fraud network (for example, if we only know about one type of fraud but there are different fraud schemes), the algorithm will miss other fraud clusters that are not connected to our seeds.
Real-world transaction networks change constantly - new transactions happen every second. My current implementation requires rebuilding the entire graph and recomputing all scores when new edges are added. This is very inefficient for large, dynamic networks.
We did implement a basic incremental update method as a bonus feature, but it only gives approximate results and still requires recomputation for nodes far from the update. A better solution would be needed for production use.
If there are fraud communities that have no connections at all to our seed fraudsters, the algorithm will not detect them. They will get very low suspicion scores because no probability mass can flow to them from the seeds.
In the Wikipedia dataset, we found 1,847 nodes that are completely isolated (no incoming or outgoing edges). These all got score = 0, even though some of them might be fraudulent.
The choice of alpha (teleportation probability) affects results quite a bit:
- Low alpha (0.05): Suspicion spreads very far, many false positives
- High alpha (0.30): Suspicion stays close to seeds, misses connected fraudsters
Finding the right alpha value requires domain expertise and testing with ground truth data.
While CSR format is efficient, the algorithm still needs to iterate through all edges multiple times. For graphs with billions of edges (like Facebook or Twitter), even one iteration would take very long. The Monte Carlo approximation helps but loses some accuracy.
The fundamental assumption - that connected nodes are similar - might not always be true. In some cases, legitimate users might interact with fraudsters without being fraudulent themselves. For example, a fraud investigator might have many connections to fraudsters without being one. The algorithm cannot distinguish between these cases without additional features.
-
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). "The PageRank Citation Ranking: Bringing Order to the Web." Stanford InfoLab Technical Report.
- Original PageRank paper that inspired this project
-
Gyöngyi, Z., Garcia-Molina, H., & Pedersen, J. (2004). "Combating Web Spam with TrustRank." Proceedings of the 30th VLDB Conference, Toronto, Canada.
- Main paper this project is based on - introduced TrustRank concept
-
Stanford SNAP Datasets: http://snap.stanford.edu/data/
- Source of the Wikipedia voting network dataset used in experiments
-
Theodo Data Science Blog: "Fraud Detection with Personalized PageRank"
- Practical guide that helped us understand implementation details
-
GeeksforGeeks: "PageRank Implementation Guide"
- Helped with understanding the basic algorithm
-
Network Repository: Caltech Facebook Network Dataset
- Alternative dataset we considered for testing
-
"PageRank: A Trillion Dollar Algorithm" - Visual explanation on YouTube
- Helped us understand the intuition behind PageRank
-
EECS 390 Course Notes: PageRank Implementation Details
- Provided clear explanations of convergence criteria and optimizations
-
Claude AI (Anthropic): Used for code review, debugging help, and understanding CSR format implementation details
- Helped us fix bugs in dangling node handling
- Explained memory layout of CSR format
- Assisted with C++ syntax and optimization suggestions
-
ChatGPT: Used for initial research and understanding academic papers
- Helped summarize key concepts from papers
- Suggested experiment methodology
- GCC Compiler: Version 11.2.0 with C++11 standard
- Visual Studio Code: For code development and debugging
This project successfully implemented a fraud detection system using Personalized PageRank (BadRank). The use of CSR graph representation made the algorithm efficient enough to handle large networks, and the results showed clear identification of suspicious nodes based on their proximity to known fraudsters.
The main achievements were:
- Efficient O(V + E) space complexity with CSR format
- Fast convergence (usually under 30 iterations)
- Clear separation between suspicious and normal nodes
- Implementation of both Power Iteration and Monte Carlo methods
However, there are limitations like the cold start problem and need for good seed selection that would need to be addressed before using this in a real fraud detection system.
Overall, we learned a lot about graph algorithms, sparse data structures, and practical challenges in applying theoretical algorithms to real problems. This project showed us how important it is to choose the right data structure - CSR format reduced memory by 60% and made the algorithm much faster.
Word Count: ~3,200 words
Code Lines: ~800 lines (across 3 files)
Total Development Time: ~40 hours