Graph Databases & Network Analysis

COS457 Database Systems

Intro
Why do we need Graph
Databases?
Why graphs?

● Relational databases use tables and

joins

● Real-world data is often highly

connected
Limitations of Relational Databases for Connected Data
● Built for tabular data, not connected
relationships

● JOIN heavy queries are slow and

memory-intensive

● Performance drops exponentially with

multi-hop (3 + hops) queries

● Lengthy SQL needed for simple relationship

questions

● Cannot effectively model network-like or

hierarchical data
What Are Graph
Databases?
What Are Graph Databases? Node/vertex = Entity
G = (V,E)
Edge = Relationship
● Built on a graph data structure
(nodes + edges).
● Specialized databases for
connected data.
● Represent data as nodes
(entities) and edges
(relationships).
SQL vs Graph

SELECT [Link], [Link] MATCH

(a:Person)-[:FRIENDS_WITH]->(b:Pers
FROM People p1
on)
JOIN Friends f ON [Link] = f.person1_id
RETURN [Link], [Link];
JOIN People p2 ON f.person2_id =
[Link];
Property Graph vs. RDF models
Sample data

(Alice) ─FRIENDS_WITH→ (Bob),

(Bob) ─FRIENDS_WITH→ (Carol)

(Bob) ─FRIENDS_WITH→ (Dave)

(Carol) ─FRIENDS_WITH→ (Eve)

(Dave) ─FRIENDS_WITH→ (Eve)

Property Graph
● Nodes and relationships both store properties

● Nodes have labels (:Person, :City)

● Schema-optional — flexible for dynamic data

● Ideal for social networks, recommendations, fraud detection

Example:

(Alice:Person {name:'Alice'})-[:FRIENDS_WITH]->(Bob:Person {name:'Bob'})

RDF models
● RDF = Resource Description Framework

● Stores data as triples: Subject – Predicate – Object

● Example: Alice → knows → Bob

● Uses URIs for unique identification

● Queried via SPARQL

● Great for semantic meaning and data integration

Graph Data Models
Property Graph RDF Graph

Structure Nodes + Edges w/ properties Triples: Subject–Predicate–Object

Focus Performance & analytics Semantics & interoperability

Query Lang. Cypher / GQL SPARQL

Example (:Person)-[:KNOWS]->(:Person) <Alice> <knows> <Bob>

 Property Graph vs. RDF models

● Property graphs have vertices and edges that carry key-value properties

● RDF graphs stores data as triples with open-world semantics

● Interoperability is improving
○ RDF to property graph transformations
○ Emerging property graph schema
Technical Foundation &
Theory
Vivek
 Practical graph theory

● Applications of graph theory ● Common algorithms

○ Entities are represented as ○ Breadth-first search, depth-first search
nodes ○ Dijkstra’s
○ Relationships are represented by ○ PageRank
edges
○ Both have associated properties
G = (V,E)
● Core analytics of a graph database
○ Centrality
○ Community detection
○ Similarity
○ Shortest paths
Graph traversal algorithms (BFS, DFS, Dijkstra)

Breadth-First Search (BFS)

● Explores level by level.

● Finds shortest unweighted paths.
● Used for friend-of-friend, recommendation
distance.

Depth-First Search (DFS)

● Explores deep paths first, then backtracks.

● Useful for cycle detection, network
exploration.

Dijkstra’s Algorithm

● Finds shortest weighted path.

● Used in routing, logistics, latency
optimization.
Neo4j
● Native Graph Storage → index-free adjacency

● Query Engine executes Cypher patterns

● Transaction Engine ensures ACID compliance

● Graph Data Science Library runs BFS, Dijkstra, PageRank

 Cypher
“SQL for connected data”
 written_by Publication
Professor id title
professor_id publication_id
id name
1351 8583 8583 “Tangent-CFT:
An embed…”
1351 “Behrooz
Mansouri”
1351 1123 9931 “Explorations
in Numeric…”
4648 “Yuqi
Song” 7122 9931
1123 “Mathematical
Information…”
7122 “James
4648 7306
Quinlan”
7306 “Graph
convolution…”

SELECT [Link], [Link]

FROM Professor pr
JOIN written_by w ON [Link] = w.professor_id
JOIN Publication p ON w.publication_id = [Link]
 Behrooz James
writte
“Graph Mansouri n_by Quinlan
convolution…”
“Tangent-CFT:

wr
An embed…”

wr
itt

itte
en
_by

n_
_b

by
y
ten
writ

“Mathematical “Explorations in
Information…” Numeric…”
Yuqi
Song

MATCH (p:Publication)-[:written_by]->(pr:Professor)
RETURN [Link], [Link]
 Key Value

label Person

Alex name “Alex”

wo
rk
s_ age 27
at
friends_with

Nvidia
Key Value

_ at
rks
wo label works_at
Sam
since “10-05-24”

salary 170,000
 Find a person named Alex.

MATCH (p:Person)
Alex wo
rk WHERE [Link] = “Alex”
s_
at
RETURN p
friends_with

Nvidia

_ at Shorthand
rks
wo
Sam MATCH (p:Person {name: “Alex”})
RETURN p
 Find someone who is
friends with Alex.

Alex wo
MATCH (p:Person)-[:friends_with]->(a:Person)
rk
s_ WHERE [Link] = “Alex”
at
friends_with

RETURN p
Nvidia

_ at {
rks label: Person
wo
Sam name: “Sam”
age: 26
}
 Find how many jobs
Alex has.

Alex wo
MATCH (p:Person)-[w:works_at]->(:Company)
rk
s_ WHERE [Link] = “Alex”
at
friends_with

RETURN p, COUNT(w) AS job_count

Nvidia

_ at
rks
wo
Sam
 Return all people who have
deposited more than $500

Casco MATCH (p:Person)-[d:deposits]->(:Bank)

osits
dep
WITH p, SUM([Link]) AS total_deposited
Sam WHERE total_deposited > 500
dep
osi RETURN p AS person
ts

TD
Graph indexing and storage strategies

• Adjacency lists store direct neighbor pointers:

Alice → [Bob]
Bob → [Carol, Dave]
• Indexes find starting nodes quickly (e.g., {name:'Alice'})
• Traversal = following pointers, not joining tables
• Data locality → related nodes stored close in memory
• Partitioning → huge graphs split across machines for parallel traversal
Graph analytics and centrality measures

Degree Centrality: Who has the most friends

Betweenness Centrality: Who connects groups (e.g., Bob bridges Alice & Carol)

Closeness Centrality: Who can reach everyone fastest

PageRank: Who is most influential overall