CIShell Manual : K-Nearest Neighbor (Java)
This page last changed on Jan 12, 2011 by dapolley.
DescriptionThe K-Nearest-Neighbor is a measure of the correlation between the degree of a node and that of its neighbors. In many systems strong correlations are observed, and one distinguishes networks into assortative and disassortative. A network is assortative if large (small) degree nodes tend to be linked with large (small) degree nodes. Social networks are typical examples of assortative networks. A network is disassortative if large (small) degree nodes tend to be linked with small (large) degree nodes. Biological and technological networks (like the Internet) are examples of disassortative networks. where is the second moment of the distribution (i.e. the expected value of the degree squared) and is the average degree of the network. For this reason, the function calculated by the algorithm is normalized in that we divide it by the constant . Pros & ConsThe network to analyze must be undirected, otherwise there are no special constraints. ApplicationsThe algorithm is used to disclose affinities/diversities between neighboring nodes. Many properties of networks and of processes that take place on networks are affected by the presence of degree-degree correlations. Implementation DetailsThe algorithm requires two inputs, the file where the edges of the network are listed and the number of points one wishes to have in the binned correlation function described below. A first read-in of the inputfile will set the values of the number of nodes and edges of the network. In the second read-in the degrees of all nodes will be calculated and the edges are stored in an array. Then the of all nodes are calculated. Usage HintsA simple application of this algorithm could be to calculate the for networks created by the modeling algorithms of the NWB. For instance, the inputfile can be created through the Barabasi-Albert model. LinksAcknowledgementsThe algorithm was implemented and documented by S. Fortunato, integrated by S. Fortunato and W. Huang. ReferencesPastor-Satorras, R., Vazquez, A., Vespignani, A. (2001) Dynamical and Correlation Properties of the Internet. See Also |
![]() |
Document generated by Confluence on May 31, 2011 16:37 |