Abstract The purpose of network representation is to learn a set of latent features by obtaining community information from network structures to provide knowledge for machine learning tasks. Recent research has driven significant progress in network representation by employing random walks as the network sampling strategy. Nevertheless, existing approaches rely on domain-specifically rich community structures and fail in the network that lack topological information in its own domain. In this paper, we propose a novel algorithm for cross-domain network representation, named as CDNR. By generating the random walks from a structural rich domain and transferring the knowledge on the random walks across domains, it enables a network representation for the structural scarce domain as well. To be specific, CDNR is realized by a cross-domain two-layer node-scale balance algorithm and a cross-domain two-layer knowledge transfer algorithm in the framework of cross-domain two-layer random walk learning. Experiments on various real-world datasets demonstrate the effectiveness of CDNR for universal networks in an unsupervised way.
All the previous works based on random walk to sample networks into a steam of nodes are under a common assumption of power-law distribution. The power-law distribution exists widely in real-world networks. It is a special degree distribution that follows @math , where @math is a node degree and @math is a positive constant @cite_6 . A network that follows the power-law distribution is also regarded as a scale-free network with the scale invariance property @cite_31 . The social networks, biological networks and citation networks being discussed in this paper are observed to be scale-free in nature @cite_11 . In @math - @math axes, the power-law distribution shows a linear trend on the slope ratio of @math (Figure and Figure ), which reflects that numerous edges connect small degree nodes and will not change regardless of network scale @cite_13 . It has been observed in @cite_1 that if a network follows the power-law distribution, the frequency at which a node undertakes in a short random walk will also follow the same distribution. Meanwhile, random walks in power-law distribution networks naturally gravitate towards high degree nodes @cite_42 .
@cite_42 @cite_1 @cite_6 @cite_31 @cite_13 @cite_11
2124637492 2080478510 2137465421 2025598851
The emergence of order in natural systems is a constant source of inspiration for both physical and biological sciences. While the spatial order characterizing for example the crystals has been the basis of many advances in contemporary physics, most complex systems in nature do not offer such high degree of order. Many of these systems form complex networks whose nodes are the elements of the system and edges represent the interactions between them. Traditionally complex networks have been described by the random graph theory founded in 1959 by Paul Erdohs and Alfred Renyi. One of the defining features of random graphs is that they are statistically homogeneous, and their degree distribution (characterizing the spread in the number of edges starting from a node) is a Poisson distribution. In contrast, recent empirical studies, including the work of our group, indicate that the topology of real networks is much richer than that of random graphs. In particular, the degree distribution of real networks is a power-law, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network. The scale-free topology of real networks has very important consequences on their functioning. For example, we have discovered that scale-free networks are extremely resilient to the random disruption of their nodes. On the other hand, the selective removal of the nodes with highest degree induces a rapid breakdown of the network to isolated subparts that cannot communicate with each other. The non-trivial scaling of the degree distribution of real networks is also an indication of their assembly and evolution. Indeed, our modeling studies have shown us that there are general principles governing the evolution of networks. Most networks start from a small seed and grow by the addition of new nodes which attach to the nodes already in the system. This process obeys preferential attachment: the new nodes are more likely to connect to nodes with already high degree. We have proposed a simple model based on these two principles wich was able to reproduce the power-law degree distribution of real networks. Perhaps even more importantly, this model paved the way to a new paradigm of network modeling, trying to capture the evolution of networks, not just their static topology. We find that scale-free random networks are excellently modeled by simple deterministic graphs. Our graph has a discrete degree distribution (degree is the number of connections of a vertex), which is characterized by a power law with exponent γ=1 + In 3 ln 2. Properties of this compact structure are surprisingly close to those of growing random scale-free networks with y in the most interesting region, between 2 and 3. We succeed to find exactly and numerically with high precision all main characteristics of the graph. In particular, we obtain the exact shortest-path-length distribution. For a large network ( In N>>1) the distribution tends to a Gaussian of width ∼ N centered at ∼ ln N. We show that the eigenvalue spectrum of the adjacency matrix of the graph has a power-law tail with exponent 2 + y. A power law degree distribution is established for a graph evolution model based on the graph class of k-trees. This k-tree-based graph process can be viewed as an idealized model that captures some characteristics of the preferential attachment and copying mechanisms that existing evolving graph processes fail to model due to technical obstacles. The result also serves as a further cautionary note reinforcing the point of view that a power law degree distribution should not be regarded as the only important characteristic of a complex network, as has been previously argued [D. Achlioptas, A. Clauset, D. Kempe, C. Moore, On the bias of traceroute sampling, or power-law degree distribution in regular graphs, in: Proceedings of the 37th ACM Symposium on Theory of Computing, STOC'05, 2005, pp. 694-703; L. Li, D. Alderson, J. Doyle, W. Willinger, Towards a theory of scale-free graphs: Definition, properties, and implications, Internet Mathematics 2 (4) (2005) 431-523; M. Mitzenmacher, The future of power law research, Internet Mathematics, 2 (4) (2005) 525-534]. One of the most influential recent results in network analysis is that many natural networks exhibit a power-law or log-normal degree distribution. This has inspired numerous generative models that match this property. However, more recent work has shown that while these generative models do have the right degree distribution, they are not good models for real-life networks due to their differences on other important metrics like conductance. We believe this is, in part, because many of these real-world networks have very different joint degree distributions, that is, the probability that a randomly selected edge will be between nodes of degree k and l. Assortativity is a sufficient statistic of the joint degree distribution, and it has been previously noted that social networks tend to be assortative, while biological and technological networks tend to be disassortative. We suggest understanding the relationship between network structure and the joint degree distribution of graphs is an interesting avenue of further research. An important tool for such studies are algorithms that can generate random instances of graphs with the same joint degree distribution. This is the main topic of this article, and we study the problem from both a theoretical and practical perspective. We provide an algorithm for constructing simple graphs from a given joint degree distribution, and a Monte Carlo Markov chain method for sampling them. We also show that the state space of simple graphs with a fixed degree distribution is connected via endpoint switches. We empirically evaluate the mixing time of this Markov chain by using experiments based on the autocorrelation of each edge. These experiments show that our Markov chain mixes quickly on these real graphs, allowing for utilization of our techniques in practice.