Composite Network Analysis

 

PRITHWISH BASU

BBN TECHNOLOGIES

 

Network science typically involves the study of large interconnected structures in diverse domains such as information (World Wide Web), communications (Internet), social interactions (Facebook, MySpace, LinkedIn), transportation (Road networks), the Semantic Web, and biological networks, to name a few. Often these networks are intertwined with each other rather than co-exist independently. For example, a group of friends richly linked via a social network such as LinkedIn communicate over a communication network such as the Internet or the telephone network. Friends gossip a particular piece of information and that can potentially reach all nodes in the particular connected component of the social network eventually. However, the piece of information that traverses a single "social link" may have to travel over multiple "communication links", and in fact the same message may have to travel several times over the same communication link due the specific location of friends in the social network. Such interactions between the two networks result in interesting "composite network" structures that essentially constitute a union of the two networks and a mapping of nodes and paths in the first type of network to nodes and paths in the second type of network. Such composite networks are common in daily life but lack adequate mathematical tools for their systematic analysis. We propose a model of composite networks that encompasses two networks and a mapping between them. In simple cases, the mapping can be a random permutation, whereas in more realistic cases there may be correlations between the relative locations of nodes in one network and those in the other. Such mappings can be many-to-one or one-to-many. We introduce metrics such as "constrained composite path stretch" and "constrained composite diameter (CCD)" to characterize the effect of a particular type of mapping on the elongation of a path in one network when embedded into another. We show that for simple networks such as one dimensional lattices (lines and cycles), it is possible to analytically characterize (in an exact manner) the difference between worst-case, best-case, and average-case permutation mappings with respect to the CCD metric. We conjecture that the ratio between the worst and the average case CCD for any line of N nodes mapped on any graph on N nodes is O(Sqrt(N)). In non-regular composite networks such as "command hierarchies" (which are trees) mapped onto random geometric graphs (an analytically tractable model for wireless multihop communication networks), it is possible to analyze the above mappings approximately. This is the first step in a research program that aims to study composite network analysis, and we believe our preliminary results indicate a promising direction towards understanding realistic massive composite networks (e.g., mapping of the Web graph on the Internet topology graph). [Research was sponsored by the Army Research Laboratory and was accomplished under Cooperative Agreement Number W911NF-09-2-0053. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.]