Subgraph Operations

Subgraph operations extract portions of a larger graph based on structural proximity, node membership, some other criteria. They are normally useful for analyzing local neighborhoods or focusing on specific regions.

Setup

create table edges as
select *
from (values (1::bigint, 2::bigint),
             (1, 3),
             (2, 3),
             (2, 4),
             (3, 4),
             (4, 5),
             (4, 6),
             (5, 6),
             (5, 7),
             (6, 7),
             (7, 8),
             (8, 9)) t(src, dst);

---

Ego Graph

Extracts the subgraph within a given radius of a center node. The ego graph includes the center node, all nodes within the specified number of hops, and all edges between them.

select src, dst
from onager_sub_ego_graph((select src, dst from edges), center := 4::bigint, radius := 2);

Column	Type	Description
src	bigint	Source node of edge
dst	bigint	Destination node

Parameters:

• center: The central node of the ego graph
• radius: Maximum distance from center (number of hops)

-- Compare ego graphs at different radii
select 'radius=1' as scope, count(*) as edges
from onager_sub_ego_graph((select src, dst from edges), center := 4::bigint, radius := 1)
union all
select 'radius=2', count(*)
from onager_sub_ego_graph((select src, dst from edges), center := 4::bigint, radius := 2)
union all
select 'radius=3', count(*)
from onager_sub_ego_graph((select src, dst from edges), center := 4::bigint, radius := 3);

---

K-Hop Neighbors

Returns all nodes within k hops of a starting node. Unlike ego graph, this returns only node IDs, not edges.

select node_id
from onager_sub_k_hop((select src, dst from edges), start := 1::bigint, k := 2)
order by node_id;

Column	Type	Description
node_id	bigint	Node within k hops of start node

Parameters:

• start: Starting node
• k: Maximum number of hops (0 returns just the start node)

-- Find nodes at exactly distance 2 (in 2-hop but not in 1-hop)
with hop1 as (select node_id from onager_sub_k_hop((select src, dst from edges), start := 1::bigint, k := 1)),
     hop2 as (select node_id from onager_sub_k_hop((select src, dst from edges), start := 1::bigint, k := 2))
select h2.node_id
from hop2 h2
         left join hop1 h1 on h2.node_id = h1.node_id
where h1.node_id is null;

---

Induced Subgraph

Given a set of nodes, returns the subgraph containing only those nodes and the edges between them. The induced subgraph preserves the original graph structure within the specified node set.

-- Extract subgraph for specific nodes
select src, dst
from onager_sub_induced((
  select e.src, e.dst, n.node as filter_node
  from edges e
  cross join (values (2::bigint), (3), (4), (5)) n(node)
));

Column	Type	Description
src	bigint	Source node of edge
dst	bigint	Destination node

[!NOTE] The induced subgraph function requires a table with (src, dst, filter_node) columns.

---

Complete Example: Neighborhood Analysis

Analyze the local structure around a node of interest:

create table social as
select *
from (values (1::bigint, 2::bigint),
             (1, 3),
             (2, 3),
             (2, 4),
             (3, 4),
             (3, 5),
             (4, 5),
             (4, 6),
             (5, 6),
             (5, 7),
             (6, 7),
             (6, 8),
             (7, 8),
             (7, 9),
             (8, 9),
             (8, 10)) t(src, dst);

-- Find nodes near user 5
select node_id as nearby_user
from onager_sub_k_hop((select src, dst from social), start := 5::bigint, k := 2)
order by node_id;

-- Get the ego network and analyze it
with ego as (select src, dst
             from onager_sub_ego_graph((select src, dst from social), center := 5::bigint, radius := 2))
select (select count(*) from (select src from ego union select dst from ego)) as nodes,
       (select count(*) from ego)                                                                              as edges,
       (select round(avg_clustering, 3)
        from onager_mtr_avg_clustering((select * from ego)))                                                   as clustering;

-- Compute centrality within the neighborhood
with ego as (select src, dst
             from onager_sub_ego_graph((select src, dst from social), center := 5::bigint, radius := 2))
select node_id, round(rank, 4) as local_importance
from onager_ctr_pagerank((select * from ego))
order by rank desc limit 5;