## k-nearest neighbour networks

General discussions and questions about recurrence plot and recurrence network related methods.
funnyfractals
Junior
Posts: 2
Joined: Fri Jun 7, 2013 09:27
Affiliation (Univ., Inst., Dept.): tampere univ of tech
Location: Tampere,TTY,Finland
Research field: Electrophysiological signals analysis

### k-nearest neighbour networks

Hi

I am interested in generating adjacency matrices using k-nearest networks approach. I have couple of questions regarding this .

1) Assuming the embedding dimension is m, i will get m-1 adjacency matrices ( for dimension 2 to m ). I am interesting in computing some network measures like clustering coefficient. Do I compute this measure for each dimension and then average it ? Or how do it take all the dimension into consideration while finding k-nearest neighbors for each observation vector ?

2) k-nearest neighbor approach gives asymmetric matix that is directed. I know i can obtain undirected network by artificially making it symmetric such that if r(i,j) = 1, make r(j,i) = 1 (Shimada et al. 2008). But is such an approach good ? Does it not change the network structure by introducing links which did not exist in the first place according to the 'nearest neighbors' condition ? So is it then better to derive measures for directed, asymmetric graph ?

Please note that I am trying to derive these measures for one channel EEG signal.

Thank You
Norbert
Expert
Posts: 194
Joined: Wed Jan 4, 2006 11:03
Affiliation (Univ., Inst., Dept.): Potsdam Institute for Climate Impact Research, Germany
Location: Potsdam, Germany
Location: Potsdam Institute for Climate Impact Research, Germany

### Re: k-nearest neighbour networks

funnyfractals wrote:1) Assuming the embedding dimension is m, i will get m-1 adjacency matrices ( for dimension 2 to m ). I am interesting in computing some network measures like clustering coefficient. Do I compute this measure for each dimension and then average it ? Or how do it take all the dimension into consideration while finding k-nearest neighbors for each observation vector ?
Perhaps I did not understand your question. When using embedding, you have only one recurrence matrix, i.e., one adjacency matrix. A link between A and B in the adjacency matrix is simply that state A and state B are neighbours or are very close in the m-dimensional phase space. The embedding dimension sets the dimension of the phase space.
funnyfractals wrote:2) k-nearest neighbor approach gives asymmetric matix that is directed. I know i can obtain undirected network by artificially making it symmetric such that if r(i,j) = 1, make r(j,i) = 1 (Shimada et al. 2008). But is such an approach good ? Does it not change the network structure by introducing links which did not exist in the first place according to the 'nearest neighbors' condition ? So is it then better to derive measures for directed, asymmetric graph ?
No, I would not make it symmetric. But there has been a discussion about it in
R. V. Donner, M. Small, J. F. Donges, N. Marwan, Y. Zou, R. Xiang, J. Kurths: Recurrence-based time series analysis by means of complex network methods, International Journal of Bifurcation and Chaos, 21(4), 1019–1046 (2011). DOI:10.1142/S0218127411029021