NIST - Bell Labs Workshop on Large-Scale Complex Networks

--------------------------------------------------------------------------------------------

Edmond Jonckheere,   USC

Title:  Quantum Networks

Abstract:  

A quantum network is a physical arrangement of spins with Heisenberg or XX coupling energy. In the single excitation subspace of the Hamiltonian H, a message is encoded as excitation pattern |i> of a spin and read out as |j> at any other spin. We develop a distance d(i,j) between quantum states that reflects the fidelity <i|exp(-Ht)|j>  or Information Transfer Capacity (ITC) from spin i to spin j in an amount of time t. The dependency on the time forces us to deviate from the polarized distance arcos|<i|j>| and its simple positively curved geometry to a distance of the form log(1/pmax(i,j)), where pmax is the maximum over all t's of the transfer probability of the excitation from spin I to spin j in an amount of time t. The major difficulty is twofold: (1) prove that the maximum transfer probability can be reached and (2) prove that log(1/pmax(i,j)) is indeed a distance, that is, it satisfies the triangle inequality. Next, we examine the geometry of the distance, with special attention to spin chains (quantum wires) and spin rings (quantum token rings). Contrary to traditional network where packets follow a single path, here, the excitation is multi-path, as specified by the Feynman path integral. It will be shown that this single fact only gives the geometry an "anti-core," contrary to the congestion "core" of classical networks. Finally, as an illustration of the concept of "control enabled geometry," it will be shown how the "anti-core" can be removed by local magnetic field control. (Note: This is joint work with S. Schirmer and F. Langbein.) --------------------------------------------------------------------------------------------

Iraj Saniee,   Alcatel-Lucent Bell Labs

Title: Large-scale curvature of complex networks and its applications

Abstract:

We argue for the need for detection of possible large-scale features in complex networks as a contrast to detection and analysis of only local features (such as degree distribution and clustering coefficient) and test for hyperbolicity via careful adoption of Gromov's theory for large but finite networks. We will present the key pros and cons of delta-hyperbolicity, such as efficient tree approximation but also core congestion, while illustrating the discussion with ample tests on communication and social networks. We'll conclude with evidence that while hyperbolicity aids targeted spread thanks to its small world property, it appears to be hostile to random spread, a natural cyber-security asset in complex information networks. (This talk is an overview of key results obtained by the Bell Labs team and collaborators.)

--------------------------------------------------------------------------------------------

Yuliy Baryshnikov,   UIUC

Title: Space of Networks and Traffic Patterns

Abstract:

In this talk I will describe a framework for introducing a metric structure on the space of networks with traffic data, and will discuss several examples and implications.

--------------------------------------------------------------------------------------------

Jie Goa,   Stonybrook University

Title: Greedy Routing on Curved Networks

Abstract:

In the talk we consider a network embedded in a geometric space and greedy routing that forwards the message to a neighbor whose distance to the destination is the smallest. We consider the deformation of the network geometry using curvature flow and show that greedy routing on differently curved space have a number of desirable properties such as guaranteed delivery, traffic load balancing, multipath routing, and fast recovery upon node/link failures.

--------------------------------------------------------------------------------------------

John Lavery,  Army Research Laboratory

Title: Social Informatics Program

Abstract:

The Social Informatics Program at the Army Research Office is a program of fundamental research the objectives of which are to quantify technology-based social interaction phenomena, to develop metrics for the quantified phenomena and to develop forensic and predictive analytical and computational models based on these quantifications and metrics. The objects of interest will generally be social phenomena (social groups/structure) and socio-cognitive phenomena (human intentions in a social context). The quantification and metrics of interest to this program are those based on domain-scientific principles of social and socio-cognitive science that are at the same time mathematically consistent and computationally feasible. Analytical and computational models for both forensic and predictive purposes are of interest, especially those in the less-investigated area of weak-tie sociology that is important for technology-based social interaction.

--------------------------------------------------------------------------------------------

Vladimir Marbukh,  NIST

Title: Systemic Risk of Resource Sharing in Critical National Infrastructures

Abstract:

Critical national infrastructures are typically supplied, maintained and used by a large number of strategically behaving participants. We suggest that this strategic behavior may significantly affect systemic risks in critical national infrastructures with shared resources.

--------------------------------------------------------------------------------------------

Michael W. Mahoney,  Stanford University

Title:  Toward Tree-like Structure in Large Informatics Graphs 

Abstract:

Large informatics graphs such as large social and information networks are often thought of as having some sort of ``tree-like'' or ``hierarchical'' structure. Although empirical results typically indicate the presence of some sort of locally-biased or small-scale clustering structure, these empirical results also clearly indicate that large social and information networks are expander-like in the sense that there do not exist good large clusters. For various technical yet very fundamental reasons, these empirical properties make it very challenging to identify and exploit the hypothesized tree-like structure in these networks using traditional tools such as the theory of delta hyperbolicity and the theory of tree decompositions. Recent theoretical and empirical results as well as possible future directions that aim at extracting meaningful tree-like structure in a scalable and robust way will be described.

--------------------------------------------------------------------------------------------

John S. Baras,  UMD

Title: Complex Network Problems Solutions via Greedy Hyperbolic Embedding

Abstract: 

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 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. Using the mathematics of Radon transform inversion in symmetric spaces we solve some of these problems, illustrating how the solutions are inspired by the famous Calderón electric impedance tomography problem. 

--------------------------------------------------------------------------------------------

Brian Cloteaux,  NIST

Title:  Examining Affiliations in Complex Networks 

Abstract:

One way to help understand the structure of complex networks is to examine what common group memberships (or affiliations) the entities in the network share. Linking entities to their common affiliations gives an alternative type of network commonly called an affiliation network. We will examine some of the useful properties of affiliation networks, and our efforts in using them in network modeling and analysis.

Information about Hotels/Motels, Food/Dining, Weather, Transportation can be found at the NIST Visitor Information Homepage.

The NIST campus is closed to the general public. As a result, all attendees must be pre-registered. Visitors can access the Gaithersburg campus from the main gate at West Diamond Avenue and Bureau Drive only. On the day of the workshop, visitors should stop in at the Visitor Center outside the main gate to pick up registration materials. Photo identification must be presented at this time. International attendees are required to present a passport. Attendees must wear their conference badge at all times while on the campus.

Please also note that additional information is needed to register international attendees. Please provide the information on this form to the registration contact at NIST.