The 2^{nd} NIST - Bell Labs Workshop aims at highlighting and discussing current and emerging research on:

- Large-scale geometry of complex networks, including hyperbolicity and its possible impact on network performance, reliability, robustness, and security.
- Processes on said complex networks, including percolation and diffusion.
- Interplay between processes on networks and network evolution.

The workshop will consist of eight 30-minute invited talks followed by a 60-minute discussion among the participants.

Friday, June 8th, 2012 (**Tentative Agenda**)

- 9:00 - 9:05am Brief welcome by organizers

- 9:05 - 9:10am Welcome -- Ronald Boisvert, Chief, NIST Applied & Computational Mathematics Division

- 9:10 - 9:30am Applied Mathematics at NIST -- Ronald Boisvert, Chief, NIST Applied & Computational Mathematics Division

- 9:30 - 10:00am Quantum Networks -- Edmond Jonckheere, USC

- 10:00 - 10:30am Large-scale curvature of complex networks and its implications -- Iraj Saniee, Alcatel-Lucent Bell Labs

- 10:30 - 11:00am Break

- 11:00 - 11:30am Space of Networks and Traffic Patterns --Yuliy Baryshnikov, UIUC

- 11:30 - 12:00am Greedy Routing on Curved Networks -- Jie Gao, Stony Brook University

- 12:00 - 1:00pm Lunch Break

- 1:00 - 1:30pm Social Informatics Program -- John Lavery, Army Research Laboratory

- 1:30 - 2:00pm Systemic Risk of Resource Sharing in Critical National Infrastructures -- Vladimir Marbukh, NIST

- 2:00 - 2:30pm Toward Tree-like Structure in Large Informatics Graphs -- Michael Mahoney, Stanford University

- 2:30 - 3:00pm Break

- 3:00 - 3:30pm Complex Network Problems Solutions via Greedy Hyperbolic Embedding -- John Baras, University of Maryland, College Park

- 3:30 - 4:00pm Examining Affiliations in Complex Networks -- Brian Cloteaux, NIST

- 4:00 - 5:00pm Open Discussion

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

**Edmond Jonckheere,** USC

**Title:** Quantum Networks

**Abstract**:

`|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.

**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.**

Created March 14, 2012, Updated May 13, 2016