University of Minnesota
University Relations
http://www.umn.edu/urelate
612-624-6868
myU OneStop


Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Wednesday, April 23, 2014

DTC Seminar Series

Hyperbolic Embedding to the Rescue in Communication and Social Networks

by

John S. Baras
Lockheed Martin Chair in Systems Engineering
The Institute for Systems Research
University of Maryland

Wednesday, April 23, 2014
3:30 p.m. reception
4:00 p.m. seminar

401/402 Walter Library

John S. Baras

We consider several challenging problems in complex networks; communication, social and hybrid. We use greedy hyperbolic embedding of such networks in hyperbolic space and the associated greedy routing that this embedding enables. We consider the following problems where this embedding provides high performance and efficient solutions. First, we develop greedy backpressure routing algorithms for both static and dynamic wireless networks that result in much better, and even controllable, trade-off between throughput and delay. The solution involves a new combination of greedy hyperbolic routing and backpressure scheduling. Second, we develop a context-aware routing scheme for social networks that aims to increase the relevance of messages shared across a social network. It achieves this by forwarding each message to the most relevant nodes, taking into account both user preferences and the network structure. Again greedy hyperbolic embedding is utilized and a new relevance metric is constructed that incorporates a context similarity measure and network structure, the latter represented by the hyperbolic distance between nodes. Third, we consider the advertisement allocation problem for large social networks. We show how hyperbolic embedding can be utilized again to formulate the underlying optimization problem in a continuum that not only reduces dramatically the dimensionality of the advertisement allocation problem from that of the associated integer programming formulation, but also provides a general framework for designing allocation strategies incorporating business rules. Fourth, we consider network tomography problems, whereby properties of internal nodes and links of the network are dynamically inferred from iterated adaptive measurements on a subset of nodes, called boundary nodes. Again using hyperbolic embedding we demonstrate that these tomography problems can be formulated as true tomography problems in hyperbolic space, involving inversion of Radon transforms on symmetric spaces; the tomographic "integrals" are now over paths of the graph.

 

John S. Baras: B.S. in Electrical and Mechanical Engineering from the National Technical University of Athens, Greece, 1970; M.S. and Ph.D. in Applied Mathematics from Harvard University 1971, 1973. Since 1973 with the Electrical and Computer Engineering Department, and the Applied Mathematics Faculty, at the University of Maryland College Park. Since 2000 faculty member in the Fischell Department of Bioengineering. Since 2014 faculty member in the Mechanical Engineering Department. Founding Director of the Institute for Systems Research (ISR) from 1985 to 1991. Since 1991, has been the Director of the Maryland Center for Hybrid Networks (HYNET). Since 2013, Guest Professor at the Royal Institute of Technology (KTH), Sweden. Life Fellow of the IEEE and a Foreign Member of the Royal Swedish Academy of Engineering Sciences. Received the 1980 George Axelby Prize from the IEEE Control Systems Society and the 2006 Leonard Abraham Prize from the IEEE Communications Society. Professor Baras' research interests include control, communication and computing systems.