The Dimensionality Reduction Of Network Data Using Kirchhoff Resistance

Faced with the ‘Curse of Dimensionality’from high-dimensional data, we nowa-daystreatdimensionalityreductionasoneofthemainmethodsindealingwithlarge-scalehigh-dimensional data (whose purpose is to map high-dimensional data to a lower spacewhile discovering the intrinsic structure of high-dimensional data). Existing dimension-ality reduction algorithms such as MDS, Isomap and LLE have been properly applied tomany fields, but all these dimensionality reduction algorithms have their merit and de-merit. Especially in the field of manifold learning, how to learn from manifold with holesis a problem that has not been solved yet by the algorithms above.ThispaperproposesanimprovedalgorithmbasedonIsomapbytreatingtheweightedgraph as a resistor network, calculating the effective resistance between any pairs of thenodes, and then using the resistance distance to modify the shortest path. Since the resis-tance distance can reflect the‘distance’between two nodes in some sense, this modifiedIsomap algorithm will be able to retain more information of data or manifolds.Based on the traditional Isomap, the improved algorithm will choose the appropriatecorrection function using the resistance distance. This algorithm not only handles thetraditional manifold in dimensionality reduction well, but also works well for manifoldwith holes.This improved method mainly relies on the following three parameters, theneighborhood-parameter n, the parameter of peak value peak and the parameter of vari-ance var of the correction function.Numerical simulations show that after choosing appropriate parameters of peakvalue and variance, this improved algorithm can reduce sensitivity to the neighborhood-parameter n. Meanwhile, by calculating complexity of the algorithm we find that if weonlyneedtochangetheparametersofpeakvalueandvariance, wedon’tneedtorecalcu-latetheshortestpathofthegraph,whichisthemosttime-consumingpartofthealgorithm.Numerical simulations also show that the modified Isomap has achieved better results onhandling some variation manifold compared with the traditional Isomap.