A block-based generative model for attributed network embedding

Attributed network embedding has attracted plenty of interest in recent years. It aims to learn task-independent, low-dimensional, and continuous vectors for nodes preserving both topology and attribute information. Most of the existing methods, such as random-walk based methods and GCNs, mainly focus on the local information, i.e., the attributes of the neighbours. Thus, they have been well studied for assortative networks (i.e., networks with communities) but ignored disassortative networks (i.e., networks with multipartite, hubs, and hybrid structures), which are common in the real world. To model both assortative and disassortative networks, we propose a block-based generative model for attributed network embedding from a probability perspective. Specifically, the nodes are assigned to several blocks wherein the nodes in the same block share the similar linkage patterns. These patterns can define assortative networks containing communities or disassortative networks with the multipartite, hub, or any hybrid structures. To preserve the attribute information, we assume that each node has a hidden embedding related to its assigned block. We use a neural network to characterize the nonlinearity between node embeddings and node attributes. We perform extensive experiments on real-world and synthetic attributed networks. The results show that our proposed method consistently outperforms state-of-the-art embedding methods for both clustering and classification tasks, especially on disassortative networks.

     

Active exploration for large graphs

Modern information networks, such as social networks, communication networks, and citation networks, are often characterized by very large sizes and dynamically changing structures. Common solutions to graph mining tasks (e.g., node classification) usually employ an unrestricted sampling-then-mining paradigm to reduce a large network to a manageable size, followed by subsequent mining tasks. However, real-world networks may be unaccessible at once and must be crawled progressively. This can be due to the fact that the size of the network is too large, or some privacy/legal concerns. In this paper, we propose an Active Exploration framework for large graphs, where the goal is to simultaneously carry out network sampling and node labeling in order to build a sampled network from which the trained classifier can have the maximum node classification accuracy. To achieve this goal, we consider a network as a Markov chain and compute the stationary distribution of the nodes by deriving supervised random walks. The stationary distribution helps identify specific nodes to be sampled in the next step, and the labeling process labels the most informative node which in turn strengthens the sampling of the network. To improve the scalability of active exploration for large graphs, we also propose a more efficient multi-seed algorithm that simultaneously runs multiple, parallel exploration processes, and makes joint decisions to determine which nodes are to be sampled and labeled next. The simultaneous, mutually enhanced sampling and labeling processes ensure that the final sampled network contains a maximum number of nodes directly related to the underlying mining tasks. Experiments on both synthetic and real-world networks demonstrate that our active exploration algorithms have much better chance to include target nodes in the sampled networks than baseline methods.     

Mechanisms for building autonomically scalable services on cooperatively shared computing platforms

We present here a system architecture and its underlying mechanisms for building autonomically scalable and resilient services on cooperatively shared computing platforms. Specifically, our focus is on utilizing computing platforms exhibiting the following characteristics. The resources at a node in such platforms are allocated to competing users on fair‐share basis, without any reserved resource capacities for any user. There is no platform‐wide resource manager for the placement of users on different nodes. The users independently select nodes for their applications. Moreover, a node can become unavailable at any time due to crashes or shutdowns. Building scalable services in such environments poses unique challenges due to node‐level fluctuations in the available resource capacities and node crashes. The service load may surge in a short time due to flash crowds. Autonomic scaling of service capacity is performed by dynamic control of the degree of service replication based on the estimated service capacity and the observed load. We present here models for estimating the service capacity at a node under fluctuating operating conditions. Furthermore, we develop adaptive and agile load distribution mechanisms for distributing load among replicas based on their time‐varying service capacities. We present the results of our evaluations of these mechanisms on PlanetLab, which exemplifies the platform level characteristics considered here.Copyright © 2013 John Wiley & Sons, Ltd.     

Accurate and efficient detection of critical links in network to minimize information loss

We address the problem of efficiently detecting critical links in a large network. Critical links are such links that their deletion exerts substantial effects on the network performance such as the average node reachability. We tackle this problem by proposing a new method which consists of three acceleration techniques: redundant-link skipping (RLS), marginal-node pruning (MNP) and burn-out following (BOF). All of them are designed to avoid unnecessary computation and work both in combination and in isolation. We tested the effectiveness of the proposed method using two real-world large networks and two synthetic large networks. In particular, we showed that the proposed method can estimate the performance degradation by link removal without introducing any approximation within a computation time comparable to that needed by the bottom-k sketch which is a summary of dataset and can efficiently process approximate queries, i.e., reachable nodes, on the original dataset, i.e., the given network. Further, we confirmed that the measures easily composed by the well known existing centralities, e.g. in/out-degree, betweenness, PageRank, authority/hub, are not able to detect critical links. Links detected by these measures do not reduce the average reachability at all, i.e., not critical at all.     

A distributed reliable collusion-free algorithm for selecting multiple coordinators in IOTA using fog computing

IOTA is a distributed ledger technology with a new structure called Tangle, which offers high scalability, no fees, and near-instant transfers for the internet-of-things (IoT) networks. The most important issue of IOTA is consensus achievement, which is handled by a single node acting as a coordinator. A single and default coordinator node exposes IOTA to the single point of failure and incomplete distribution issues. In this paper, a novel algorithm for selecting multiple coordinators to participate in the consensus process at milestones is proposed (i.e., MCS algorithm) to overcome the problem of a single coordinator in IOTA network. The MCS algorithm is applied in a two-layered architecture including IoT devices (i.e., Layer 1) and fog nodes (i.e., Layer 2). We define and formulate four different properties as metrics to select multiple coordinators in this architecture. Moreover, a collusion list is defined to decrease the risk of collusion between fog nodes in the network. Experimental results show that using multiple fog nodes as coordinators in IOTA network can improve the average response time and average throughput while does not considerably sacrifice the total cost and system utilization in comparison with the use of a single default coordinator in IOTA network.     

Discrete time tandem networks of queues: Effects of different regulation schemes for simultaneous events

We consider tandem networks of discrete time Bernoulli servers with state dependent service rates and a state dependent Bernoulli arrival stream at the first node of the tandem. We investigate the effects of different regulation schemes for simultaneous events (e.g. joint arrivals and departures at some node, or joint departures at different nodes) on the performance behaviour of the network. The most serious effects occur with respect to arrival theorems which describe the distribution of the other customers present in the network and seen by an arriving customer, or observed by a customer during a jump inside the network. We prove necessary and sufficient conditions on the regulation scheme for a customer to observe always the time stationary behaviour of the network during his jumps. It turns out that we have to distinguish between local and global control for the regulation of simultaneous jumps. For different arrival schemes we compute the joint sojourn time distribution for a customer traversing the tandem. As a consequence we identify from this a regulation scheme which is known in the literature, where Little’s formula cannot be applied directly.     

Deterministic broadcasting time with partial knowledge of the network

We consider the time of deterministic broadcasting in networks whose nodes have limited knowledge of network topology. Each node v knows only the part of the network within knowledge radius r from it, i.e., it knows the graph induced by all nodes at distance at most r from v. Apart from that, each node knows the maximum degree Δ of the network. One node of the network, called the source, has a message which has to reach all other nodes. We adopt the widely studied communication model called the one-way model in which, in every round, each node can communicate with at most one neighbor, and in each pair of nodes communicating in a given round, one can only send a message while the other can only receive it. This is the weakest of all store-and-forward models for point-to-point networks, and hence our algorithms work for other models as well, in at most the same time.

We show trade-offs between knowledge radius and time of deterministic broadcasting, when the knowledge radius is small, i.e., when nodes are only aware of their close vicinity. While for knowledge radius 0, minimum broadcasting time is Θ(e), where e is the number of edges in the network, broadcasting can be usually completed faster for positive knowledge radius. Our main results concern knowledge radius 1. We develop fast broadcasting algorithms and analyze their execution time. We also prove lower bounds on broadcasting time, showing that our algorithms are close to optimal.     

On conditions for a product-form stationary probability distribution of states of a multimode service network

We consider open and closed queueing networks with Markovian routing and symmetric service policies. Single-server nodes may operate in several modes. In each node, the amount of work required for servicing an arrival or for switching the mode is distributed arbitrarily. The performance rate for each of these operations depends on the residual amount of work. For open networks, the arrival flow is Poissonian. We establish conditions for a productform stationary distribution of states of the piecewise continuous process that describes the network behavior.     

On the end-to-end flow allocation and channel assignment in multi-channel multi-radio wireless mesh networks with partially overlapped channels

The performance of wireless mesh networks (WMNs) can be improved significantly with the increase in number of channels and radios. Despite the availability of multiple channels in several of the current wireless standards, only a small fraction of them are non-overlapping and many channels are partially overlapped. In this paper, we formulate the joint channel assignment and flow allocation problem for multi-channel multi-radio WMNs as a Mixed Integer Linear Program (MILP). Unlike most of the previous studies, we consider the case when both non-overlapped and partially overlapped channels are being used. We consider an objective of maximizing aggregate end-to-end throughput and minimizing queueing delay in the network, instead of the sum of link capacities, since the traffic characteristics of a multi-hop WMN are quite different from a single hop wireless network. Our static channel assignment algorithm incorporates network traffic information, i.e., it is load aware. Our formulation takes into consideration several important network parameters such as the transmission power of each node, path loss information, the signal to interference plus noise ratio at a node, and the frequency response of the filters used in the transmitter and receiver. We show by simulations that our MILP formulation makes efficient use of the spectrum, by providing superior channel assignments and flow allocations with the addition of partially overlapped channels, without the use of any additional spectrum. We also justify the need to consider alternative objective functions such as, minimizing average queueing in the network. We also propose a polynomially bounded heuristic algorithm to scale the proposed algorithm to bigger network topologies.     

Minimal fault diameter for highly resilient product networks

We present a number of results related to the fault tolerance of Cartesian product networks. We start by presenting a method for building containers (i.e., sets of node-disjoint paths) between any two nodes of a product network based on given containers for the factor networks. Then, we show that the best achievable fault diameter (i.e., diameter under maximum fault conditions), under reasonable network regularity and connectivity conditions, is equal to the fault-free diameter plus one. The concept of high fault resilience is then defined. We then prove that if each factor network is highly resilient, then their Cartesian product has minimal fault diameter. We derive from these results that Cartesian products of several popular networks are highly resilient and have minimal fault diameter equal to diameter plus one. These results spare future efforts that would be needed to individually determine the fault diameter of such networks as has been the practice with previously studied networks.     

Recover Fault Services via Complex Service-to-Node Mappings in Wireless Sensor Networks

With the motivation of seamlessly extending wireless sensor networks to the external environment, service-oriented architecture comes up as a promising solution. However, as sensor nodes are failure prone, this consequently renders the whole wireless sensor network to seriously faulty. When a particular node is faulty, the service on it should be migrated into those substitute sensor nodes that are in a normal status. Currently, two kinds of approaches exist to identify the substitute sensor nodes: the most common approach is to prepare redundancy nodes, though the involved tasks such as maintaining redundancy nodes, i.e., relocating the new node, lead to an extra burden on the wireless sensor networks. More recently, other approaches without using redundancy nodes are emerging, and they merely select the substitute nodes in a sensor node’s perspective i.e., migrating the service of faulty node to it’s nearest sensor node, though usually neglecting the requirements of the application level. Even a few work consider the need of the application level, they perform at packets granularity and don’t fit well at service granularity. In this paper, we aim to remove these limitations in the wireless sensor network with the service-oriented architecture. Instead of deploying redundancy nodes, the proposed mechanism replaces the faulty sensor node with consideration of the similarity on the application level, as well as on the sensor level. On the application level, we apply the Bloom Filter for its high efficiency and low space costs. While on the sensor level, we design an objective solution via the coefficient of a variation as an evaluation for choosing the substitute on the sensor level.     

An Approximate Analytical Method for General Queueing Networks

In this paper, we present an approximate solution for the asymptotic behavior of relatively general queueing networks. In the particular case of networks with general service time distributions (i.e., fixed routing matrix, one or many servers per station, FIFO discipline), the application of the method gives relatively accurate results in a very short time. The approximate stationary state probabilities are identified with the solution of a nonlinear system. The proposed method is applicable to a larger class of queueing networks (dependent routing matrix, stations with fimite capacity, etc.). In this case, the structure of the network studied must satisfy certain decomposability conditions.     

Nonstationary analysis of circuit-switched communication networks

Circuit-switched communication networks have been analyzed extensively in the stationary case, i.e. where the arrival and/or service rates are independent of time. In this paper, we study a circuit-switched network where the rates of external arrivals at the network are time-dependent functions. The circuit-switched network is modelled as a nonstationary queueing network with population constraints, which is analyzed approximately in order to obtain the blocking probability functions. Using this method we model two circuit-switched networks, namely, a traffic-groomed tandem optical network and a single-orbit LEO satellite network.     

Delays in a series of queues with correlated service times

In almost all applications of queueing network models it is assumed that for each customer the service times at different network nodes are independent. But service times in, for instance, computer and communication networks are typically essentially determined by properties like message or packet lengths that do not change substantially on the route through the network. Therefore, the service times of any customer in a queueing network are likely to be correlated, which can significantly influence quality of service (QoS) properties and performance measures such that results obtained with the independence assumption may be misleading. We consider delays in a series of queues with correlated service times at each network node where for each customer the service time at the first node is a random variable and the successive service times are correlated with the one at the first node. A recursive scheme for delays is provided. This scheme is used in order to efficiently conduct a simulation study where two types of correlation are studied, namely identical service times, and service times with an additional Gaussian noise. The simulation study focuses on comparisons of end-to-end delays for independent service times at different nodes and correlated service times, respectively. It turns out that for both correlation types, in light traffic the delays in case of correlated service times are larger than for independent service times by a factor that first increases with increasing traffic intensity up to a maximum value approached in medium traffic after which it decreases quickly and drops down to become significantly smaller than one in heavy traffic. This effect intensifies with increasing number of network nodes and depends, as well as the crossover point from which on correlated service times yield smaller delays, on the distribution of the service times at the first node.     

Arrival first queueing networks with applications in kanban production systems

In this paper, we introduce a new class of queueing networks called arrival first networks. We characterise its transition rates and derive the relationship between arrival rules, linear partial balance equations, and product form stationary distributions. This model is motivated by production systems operating under a kanban protocol. In contrast with the conventional departure first networks, where a transition is initiated by service completion of items at the originating nodes that are subsequently routed to the destination nodes (push system), in an arrival first network a transition is initiated by the destination nodes of the items and subsequently those items are processed at and removed from the originating nodes (pull system). These are similar to the push and pull systems in manufacturing systems.

Our characterisation provides necessary and sufficient conditions for the network to possess linear traffic equations, and sufficient conditions for the network to have a product form stationary distribution. We apply our results to networks operating under a kanban mechanism and characterise the rate at which items are pulled as well as the routing and blocking protocols that give rise to a product form stationary distribution.     

On the capacity of UWB-based wireless sensor networks

Ultra-wideband (UWB) is a promising wireless communications technology and has great potential for emerging applications such as sensor networks. This paper studies the following fundamental problems for UWB-based sensor networks. For a given network instance, what is the maximum data rate (network capacity) that can be received at the base station (i.e., sink node)? What is the network capacity bound among arbitrary network instances? We show that these problems can be cast into a cross-layer formulation with joint consideration of routing, scheduling, power control, and rate assignment. For a given network instance, we find a closed-form network capacity as well as corresponding optimal routing, scheduling, power control, and rate assignment. We also find a network capacity bound among arbitrary network instances. Our results provide fundamental results for UWB-based sensor networks.     

Service discovery in mobile ad hoc networks: A field theoretic approach

Service discovery in mobile ad hoc networks is challenging because of the absence of any central intelligence in the network. Traditional solutions as used in the Internet are hence not well suited for mobile ad hoc networks. In this paper, we present a novel decentralized service discovery mechanism for ad hoc networks. The basic idea is to distribute information about available services to the network neighborhood. We achieve this by using the analogy of an electrostatic field: A service is modelled by a (positive) point charge, and service request packets are seen as (negative) test charges which are attracted by the service instances. In our approach, we map the physical model to a mobile ad hoc network in a way where each network element calculates a potential value and routes service requests towards the neighbor with the highest potential, hence towards a service instance. Our approach allows for differentiation of service instances based on their capacity. We define the required protocols and methods which we implemented in a network simulator. Using extensive simulations, we evaluate the performance and robustness of the mechanisms. The results indicate good performance and convergence even in highly mobile environments. We believe that this technique can and should be further exploited, e.g., as a routing protocol in mobile ad hoc networks.     

Transitive node similarity: predicting and recommending links in signed social networks

Online social networks (OSNs) like Facebook, Myspace, and Hi5 have become popular, because they allow users to easily share content. OSNs recommend new friends to registered users based on local features of the graph (i.e., based on the number of common friends that two users share). However, OSNs do not exploit the whole structure of the network. Instead, they consider only pathways of maximum length 2 between a user and his candidate friends. On the other hand, there are global approaches, which detect the overall path structure in a network, being computationally prohibitive for huge-size social networks. In this paper, we define a basic node similarity measure that captures effectively local graph features (i.e., by measuring proximity between nodes). We exploit global graph features (i.e., by weighting paths that connect two nodes) introducing transitive node similarity. We also derive variants of our method that apply to different types of networks (directed/undirected and signed/unsigned). We perform extensive experimental comparison of the proposed method against existing recommendation algorithms using synthetic and real data sets (Facebook, Hi5 and Epinions). Our experimental results show that our FriendTNS algorithm outperforms other approaches in terms of accuracy and it is also time efficient. Finally, we show that a significant accuracy improvement can be gained by using information about both positive and negative edges.     

Queueing Networks with Dynamic Routing and Dynamic Stochastic Bypass of Nodes

We consider open exponential networks with routing matrices that depend on a network state. A customer entering a node is either independently of other customers queued with probability that depends on the network state or instantly bypasses the node with complementary probability. After bypassing a node, customers are routed according to a stochastic matrix that depends on the network state and may differ from the routing matrix. Under certain restrictions on parameters of the model, we establish a sufficient ergodicity condition and find the final stationary distribution.     

A Single-Server Queueing System with Background Customers

A single-server queueing system with a Markov flow of primary customers and a flow of background customers from a bunker containing unbounded number of customers, i.e., the background customer flow is saturated, is studied. There is a buffer of finite capacity for primary customers. Service processes of primary as well as background customers are Markovian. Primary customers have a relative service priority over background customers, i.e., a background customer is taken for service only if the buffer is empty upon completion of service of a primary customer. A matrix algorithm for computing the stationary state probabilities of the system at arbitrary instants and at instants of arrival and completion of service of primary customers is obtained. Main stationary performance indexes of the system are derived. The Laplace—Stieltjes transform of the stationary waiting time distribution for primary customers is determined.__________Translated from Avtomatika i Telemekhanika, No. 6, 2005, pp. 74–88.Original Russian Text Copyright © 2005 by Bocharov, Shlumper.