Methods for graph creation from point clouds

3 minute read

In my Graph-Creation-from-point-clouds repository I have included four function files which create graphs according to different rules. Each function takes a set of points (nodes) in a space of arbitrary dimensionality, and decides whether each pair of nodes is connected. The functions output the network in the form of an edgelist: each row is one edge [node i, node j, distance between]. See Compare_graph_creation_functions.m for a script to create the figures below.

K nearest-neighbors Graph


Connect each node to its k nearest neighbors. [node i, node j, distance] is included in edgelist if j is a nearest neighbor of i (the reverse may or may not be true). This type of graph creation rule produces directed edges due to the asymmetry of KNN.

im Using K=3

im Varying K

Epsilon ball Graph


Connect each node to all others within a distance \(\epsilon\). This graph will be undirected.

Fixed \(\epsilon\)


Dynamic \(\epsilon\)

You can also make the epsilon radius epsilon radius a function of the data itself. Above I’ve made \(\epsilon\) inversely proportional to a metric of the local density of points. Each point now uses its own \(\epsilon\) circles). Local density was measured similarly to using a radial basis kernel (gaussian if youre in physics; normal distribution if youre in statistics..) but instead uses a purely exponentially decaying weight.

Here \(\epsilon\) radius is proportional to the mean of the distance to second and third nearest neighbors.

Tau Rule Graph


This graph decides whether each pair of nodes are connected according to the tau rule. As of now I cant find the source where I learned about this.

im The same data set using different \(\tau =2.2\) values.

im \(\tau =2.2\) with 500 points.

function [edglst]=Create_Tau_Rule_graph(dat,tau)
% builds graph from data using tau rule
%INPUT: dat=data matrix [n x d] : n points in R^d
%tau = positive number >= 1

%OUTPUT: UNDIRECTED edge list [#edges x 3].  d is the distance
%(used as edge weight) along that edge
K=1;%do not alter!
[N, dist]=knnsearch(dat,dat,'K',K+1,'NSMethod','kdtree','Distance','Euclidean');%NOTE: nearest neighbor sets are not necessarily symmetric
N=N(:,2:end); %index of each point's nearest neighbor. first col is each point itself
dist=dist(:,2:end); %distance to each point's nearest neighbor

for u=2:M
    for v=1:u-1
        if (dist(u)<=tau*dist(v))&&(dist(v)<=tau*dist(u))
            if (norm(dat(u,:)-dat(v,:))<=tau*dist(u))||(norm(dat(u,:)-dat(v,:))<=tau*dist(v))
               edglst=[edglst; u, v, norm(dat(u,:)-dat(v,:))];


Create 2D rectangular lattice graph

The function Create_Lattice_Network_2D.m allows you to obtain the set of edges connecting points in a rectangular lattice. im