Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRandom walk based in-network computation of arbitrary functions
233
0
0.0
(
0
)
Added by
Iqra Altaf Gillani
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study in-network computation on general network topologies. Specifically, we are given the description of a function, and a network with distinct nodes at which the operands of the function are made available, and a designated sink where the computed value of the function is to be consumed. We want to compute the function during the process of moving the data towards the sink. Such settings have been studied in the literature, but mainly for symmetric functions, e.g. average, parity etc., which have the specific property that the output is invariant to permutation of the operands. To the best of our knowledge, we present the first fully decentralised algorithms for arbitrary functions, which we model as those functions whose computation schema is structured as a binary tree. We propose two algorithms, Fixed Random-Compute and Flexible Random-Compute, for this problem, both of which use simple random walks on the network as their basic primitive. Assuming a stochastic model for the generation of streams of data at each source, we provide a lower and an upper bound on the rate at which Fixed Random-Compute can compute the stream of associated function values. Note that the lower bound on rate though computed for our algorithm serves as a general lower bound for the function computation problem and to the best of our knowledge is first such lower bound for asymmetric functions. We also provide upper bounds on the average time taken to compute the function, characterising this time in terms of the fundamental parameters of the random walk on the network: the hitting time in the case of Fixed Random-Compute, and the mixing time in the case of Flexible Random-Compute.
rate research
Read More
Random-walk based network embedding algorithms like node2vec and DeepWalk are widely used to obtain Euclidean representation of the nodes in a network prior to performing down-stream network inference tasks. Nevertheless, despite their impressive empirical performance, there is a lack of theoretical results explaining their behavior. In this paper we studied the node2vec and DeepWalk algorithms through the perspective of matrix factorization. We analyze these algorithms in the setting of community detection for stochastic blockmodel graphs; in particular we established large-sample error bounds and prove consistent community recovery of node2vec/DeepWalk embedding followed by k-means clustering. Our theoretical results indicate a subtle interplay between the sparsity of the observed networks, the window sizes of the random walks, and the convergence rates of the node2vec/DeepWalk embedding toward the embedding of the true but unknown edge probabilities matrix. More specifically, as the network becomes sparser, our results suggest using larger window sizes, or equivalently, taking longer random walks, in order to attain better convergence rate for the resulting embeddings. The paper includes numerical experiments corroborating these observations.
As one of the most popular south-bound protocol of software-defined networking(SDN), OpenFlow decouples the network control from forwarding devices. It offers flexible and scalable functionality for networks. These advantages may cause performance issues since there are performance penalties in terms of packet processing speed. It is important to understand the performance of OpenFlow switches and controllers for its deployments. In this paper we model the packet processing time of OpenFlow switches and controllers. We mainly analyze how the probability of packet-in messages impacts the performance of switches and controllers. Our results show that there is a performance penalty in OpenFlow networks. However, the penalty is not much when probability of packet-in messages is low. This model can be used for a network designer to approximate the performance of her deployments.
Ubiquitous sensing devices frequently disseminate their data between them. The use of a distributed event-based system that decouples publishers of subscribers arises as an ideal candidate to implement the dissemination process. In this paper, we present a network architecture which merges the network and overlay layers of typical structured event-based systems. Directional Random Walks (DRWs) are used for the construction of this merged layer. Our first results show that DRWs are suitable to balance the load using a few nodes in the network to construct the dissemination path. As future work, we propose to study the properties of this new layer and to work on the design of Bloom filters to manage broker nodes.
An interrelation between a topological design of network and efficient algorithm on it is important for its applications to communication or transportation systems. In this paper, we propose a design principle for a reliable routing in a store-carry-forward manner based on autonomously moving message-ferries on a special structure of fractal-like network, which consists of a self-similar tiling of equilateral triangles. As a collective adaptive mechanism, the routing is realized by a relay of cyclic message-ferries corresponded to a concatenation of the triangle cycles and using some good properties of the network structure. It is recoverable for local accidents in the hierarchical network structure. Moreover, the design principle is theoretically supported with a calculation method for the optimal service rates of message-ferries derived from a tandem queue model for stochastic processes on a chain of edges in the network. These results obtained from a combination of complex network science and computer science will be useful for developing a resilient network system.
Network embedding aims to represent a network into a low dimensional space where the network structural information and inherent properties are maximumly preserved. Random walk based network embedding methods such as DeepWalk and node2vec have shown outstanding performance in the aspect of preserving the network topological structure. However, these approaches either predict the distribution of a nodes neighbors in both direction together, which makes them unable to capture any asymmetric relationship in a network; or preserve asymmetric relationship in only one direction and hence lose the one in another direction. To address these limitations, we propose bidirectional group random walk based network embedding method (BiGRW), which treats the distributions of a nodes neighbors in the forward and backward direction in random walks as two different asymmetric network structural information. The basic idea of BiGRW is to learn a representation for each node that is useful to predict its distribution of neighbors in the forward and backward direction separately. Apart from that, a novel random walk sampling strategy is proposed with a parameter {alpha} to flexibly control the trade-off between breadth-first sampling (BFS) and depth-first sampling (DFS). To learn representations from node attributes, we design an attributed version of BiGRW (BiGRW-AT). Experimental results on several benchmark datasets demonstrate that the proposed methods significantly outperform the state-of-the-art plain and attributed network embedding methods on tasks of node classification and clustering.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
