Page 1 of 1

k-nearest neighbour networks

Posted: Fri Jun 7, 2013 09:36
by funnyfractals
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

Re: k-nearest neighbour networks

Posted: Wed Nov 20, 2013 12:02
by Norbert
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