000231443 001__ 231443
000231443 005__ 20190507143833.0
000231443 0247_ $$2doi$$a10.1109/Tnse.2017.2690258
000231443 022__ $$a2327-4697
000231443 02470 $$2ISI$$a000409524600001
000231443 037__ $$aARTICLE
000231443 245__ $$aHyperbolic Embedding for Efficient Computation of Path Centralities and Adaptive Routing in Large-Scale Complex Commodity Networks
000231443 260__ $$bIeee Computer Soc$$c2017$$aLos Alamitos
000231443 269__ $$a2017
000231443 300__ $$a14
000231443 336__ $$aJournal Articles
000231443 520__ $$aComputing the most central nodes in large-scale commodity networks is rather important for improving routing and associated applications. In this paper, we introduce a novel framework for the analysis and efficient computation of routing path-based centrality measures, focusing on betweenness and traffic load centrality. The proposed framework enables efficient approximation and in special cases accurate computation of the aforementioned measures in large-scale complex networks, as well as improving/adapting commodity (traffic) routing by identifying and alleviating key congestion points. It capitalizes on network embedding in hyperbolic space and exploits properties of greedy routing over hyperbolic coordinates. We show the computational benefits and approximation precision of our approach by comparing it with state-of-the-art path centrality computation techniques. We demonstrate its applicability on real topologies, characteristic of actual large-scale commodity networks, e.g., data, utility networks. Focusing on two graph embedding types, Rigel and greedy, we compare their impact on the performance of our framework. Then, we exemplify and statistically analyze the dynamic routing adaptation, via the variation of the minimum-depth spanning tree employed for greedy embedding in hyperbolic space. Notably, this allows for efficient routing adaptation according to a simple, distributed computation that can be applied during network operation to alleviate arising bottlenecks.
000231443 6531_ $$aBetweenness centrality
000231443 6531_ $$atraffic load centrality
000231443 6531_ $$ahyperbolic geometry
000231443 6531_ $$agreedy routing
000231443 6531_ $$agreedy network embedding
000231443 6531_ $$atraffic congestion
000231443 6531_ $$arigel embedding
000231443 6531_ $$acommodity networks
000231443 700__ $$g266333$$0249767$$aStai, Eleni
000231443 700__ $$aSotiropoulos, Konstantinos
000231443 700__ $$aKaryotis, Vasileios
000231443 700__ $$aPapavassiliou, Symeon
000231443 773__ $$j4$$tIeee Transactions On Network Science And Engineering$$k3$$q140-153
000231443 909C0 $$0252373$$pIC$$xU10387
000231443 909CO $$particle$$ooai:infoscience.tind.io:231443
000231443 937__ $$aEPFL-ARTICLE-231443
000231443 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000231443 980__ $$aARTICLE