# 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

Create_KNN_graph.m

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.

Using K=3

Varying K

# Epsilon ball Graph

Create_epsilonball_graph.m

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

### 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

Create_Tau_Rule_graph.m

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.

The same data set using different $$\tau =2.2$$ values.

$$\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
edglst=[];
M=size(dat,1);

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,:))];
end
end
end
end

end


# 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.

Categories:

Updated: