Flexible model of network embedding
Authors:
Preprint
Abstract
There has lately been increased interest in describing complex systems not merely as single networks but rather as collections of networks that are coupled to one another in different ways. Here we introduce a tractable model for embedding one network (A) into another (B), focusing on the case where network A has many more nodes than network B. In our model, nodes in network A are assigned, or embedded, to the nodes in network B using an assignment rule where the extent of node localization is controlled by a single parameter. We start by mapping an unassigned "source" node in network A to a randomly chosen "target" node in network B. We then assign the neighbors of the source node to the neighborhood of the target node using a random walk based approach. More specifically, each neighbor of the source node is assigned to the stopping node of a random walk that starts from the target node and has a per-step stopping probability $q$. We repeat this process until all nodes in network A have been embedded into network B. By varying the parameter $q$, we are able to produce a range of embeddings from local ($q = 1$) to global ($q \to 0$). The simplicity of the embedding mechanism allows us to calculate key quantities of interest in closed form, making it a useful starting point for more realistic models of network embedding.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Spatially Distributed Social Complex NetworksPhysical Review X, 2014
- Dynamical Interplay between Awareness and Epidemic Spreading in Multiplex NetworksPhysical Review Letters, 2013
- Geographic Constraints on Social Network GroupsPLOS ONE, 2011
- Hyperbolic geometry of complex networksPhysical Review E, 2010
- Catastrophic cascade of failures in interdependent networksNature, 2010
- Self-Similarity of Complex Networks and Hidden Metric SpacesPhysical Review Letters, 2008
- Uncovering collective listening habits and music genres in bipartite networksPhysical Review E, 2005
- Emergence of Scaling in Random NetworksScience, 1999