Seeing the Bigger Picture: How Nodes Can Learn Their Place Within a Complex Ad Hoc Network Topology
- 5 April 2013
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Signal Processing Magazine
- Vol. 30 (3) , 71-82
Abstract
This article explained how nodes in a network graph can infer information about the network topology or its topology related properties, based on in-network distributed learning, i.e., without relying on an external observer who has a complete overview over the network. Some key concepts from the field of SGT were reviewed, with a focus on those that allow for a simple distributed implementation, i.e., eigenvector or Katz centrality, algebraic connectivity, and the Fiedler vector. This paper also explained how the nodes themselves can quantify their individual network-wide influence, as well as identify densely connected node clusters and the sparse bridge links between them. The addressed concepts, as well as more advanced concepts from the field of SGT, are believed to be crucial catalysts in the design of topology-aware distributed algorithms. Examples were provided on how these techniques can be exploited in several nontrivial distributed signal processing tasks.Keywords
This publication has 40 references indexed in Scilit:
- Hearing the clusters of a graph: A distributed algorithmAutomatica, 2012
- Scalable approach to uncertainty quantification and robust design of interconnected dynamical systemsAnnual Reviews in Control, 2011
- Decentralized estimation and control of graph connectivity for mobile sensor networksAutomatica, 2010
- Graph clusteringComputer Science Review, 2007
- Fast linear iterations for distributed averagingSystems & Control Letters, 2004
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problemsConcurrency: Practice and Experience, 1994
- New spectral methods for ratio cut partitioning and clusteringIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- Reaching a ConsensusJournal of the American Statistical Association, 1974
- The net of reciprocal influence; a problem in treating sociometric data.Canadian Journal of Psychology / Revue canadienne de psychologie, 1949