Search

• Structural similarity metrics and learning techniques are introduced. • A method for classifying algorithms by network structure is proposed. • General applications and research directions of network embedding are promoted. Social networks have a plethora of applications, and analysis of these applications has been gaining much interest from the research community. The high dimensionality of social network data poses a significant obstacle in its analysis, leading to the curse of dimensionality. The mushrooming of representation learning in various research fields facilitates network representation learning (also called network embedding), which will help us address the above-mentioned issue. Structural Representation Learning aims to learn low-dimensional vector representations of high-dimensional network data, allowing maximal preservation of network structural information. This representation can then serve as a backbone for various network-based applications. First, we investigate the techniques used in network representation learning and similarity indices. We then categorize the representative algorithms into three types based on the network structural level used in their learning process. We also introduce algorithms for representation learning of edges, subgraphs, and the whole network. Finally, we introduce the evaluation metrics and the applications of network representation learning and promising future research directions. [ABSTRACT FROM AUTHOR]

In a multiple-message broadcast, an arbitrary number of messages originate at arbitrary nodes in the network at arbitrary times. The problem is to disseminate all these messages to the whole network. This paper gives the first randomized distributed multiple-message broadcast algorithm with worst-case performance guarantee in wireless ad hoc networks employing the SINR interference model which takes interferences from all the nodes in the network into account. The network model used in this paper also considers the harsh characteristics of wireless ad hoc networks: there is no prior structure, and nodes cannot perform collision detection and have little knowledge of the network topology. Under all these restrictions, our proposed randomized distributed multiple-message broadcast protocol can deliver any message m to all nodes in the network in O ( D + k + log 2 ⁡ n ) timeslots with high probability, where D is the network diameter, k is the number of messages whose broadcasts overlap with m , and n is the number of nodes in the network. We also study the lower bound for randomized distributed multiple-message broadcast protocols. In particular, we prove that any uniform randomized algorithm needs Ω ( D + k + log 2 ⁡ n log ⁡ log ⁡ log ⁡ n ) timeslots to disseminate k messages initially stored at k nodes. [ABSTRACT FROM AUTHOR]

In multi-hop radio networks, such as wireless ad-hoc networks and wireless sensor networks, nodes employ a MAC (Medium Access Control) protocol such as TDMA to coordinate accesses to the shared medium and to avoid interference of close-by transmissions. These protocols can be implemented using standard node coloring. The ( Δ + 1 ) -coloring problem is to color all nodes in as few timeslots as possible using at most Δ + 1 colors such that any two nodes within distance R are assigned different colors, where R is a given parameter and Δ is the maximum degree of the modeled unit disk graph using R as a scaling factor. Being one of the most fundamental problems in distributed computing, this problem is well studied and there is a long chain of algorithms prescribed for it. However, all previous works are based on abstract models, such as message passing models and graph based interference models, which limit the utility of these algorithms in practice. In this paper, for the first time, we consider the distributed ( Δ + 1 ) -coloring problem under the more practical SINR interference model. In particular, without requiring any knowledge about the neighborhood, we propose a novel randomized ( Δ + 1 ) -coloring algorithm with time complexity O ( Δ log ⁡ n + log 2 ⁡ n ) . For the case where nodes cannot adjust their transmission power, we give an O ( Δ log 2 ⁡ n ) randomized algorithm, which only incurs a logarithmic multiplicative factor overhead. [ABSTRACT FROM AUTHOR]

Abstract: Acyclic coloring problem is a specialized problem that arises in the efficient computation of Hessians. A proper edge coloring of a graph is called acyclic if there is no -colored cycle in . The acyclic edge chromatic number of is the least number of colors in an acyclic edge coloring of . Alon et al. conjectured that . In this paper, we consider the sufficient conditions for the planar graphs satisfying and . [Copyright &y& Elsevier]

As an important concept to depict the freshness of an information when it arrives at the destination, the Age-of-Information (AoI) and its relative scheduling works can be a very useful tool to aggregate the information from the end devices to the edge servers in Internet of Vehicles, which can strongly support those time-sensitive services in intelligent transportation system. However, most of the previous works about the AoI scheduling on edge computing are the centralized ones, rely on the reliable communications, and ignore the mobility of vehicles, which may not suit the dynamic environment in Internet of Vehicles. In this paper, we consider the AoI optimization problem in a more comprehensive vehicle model, and present a distributed AoI optimization algorithm based on a single hop end-to-edge wireless network. With an arbitrary power control technique, our algorithm reaches an asymptotically optimal performance on minimizing the expectation of AoI. Both of theoretical analysis and extensive simulations are conducted to verify the correctness and efficiency of our proposed algorithm. [ABSTRACT FROM AUTHOR]

Highlights: [•] We propose a novel clustering protocol ECDS, which considers coverage and energy efficiency simultaneously. [•] We propose two new metrics CI p and CI a and for coverage performance. [•] ECDC has better performance compared with some other clustering protocols. [ABSTRACT FROM AUTHOR]

Abstract: One of the most important issues for wireless sensor networks is to get a long network lifetime without affecting either communication connectivity or sensing coverage. Many sensors that are deployed randomly in a dense sensor network in a redundant way waste a lot of energy. One effective way to save energy is to let only a subset of sensors work at any given time. In this paper, we mainly consider such a problem. Selecting the minimum number of connected sensor nodes that can provide k-coverage (k ≥1), i.e., selecting a subset S of working sensors, such that almost every point in the sensing region can be covered by at least k sensors and the sensors in S can form a connected communication subgraph. We propose a connected k-coverage working sets construction algorithm (CWSC) based on Euclidean distance to k-cover the sensing region while minimizing the number of working sensors. CWSC can produce different coverage degrees according to different applications, which can enhance the flexibility of the sensor network. Simulation results show that the proposed algorithm, which can conserve energy and prolong the lifetime of the sensor network, is better than the previous algorithms. [Copyright &y& Elsevier]

Abstract: Given a universe containing elements and a collection of multisets or sets over , the multiset multicover (MSMC) problem or the set multicover (SMC) problem is to cover all elements at least a number of times as specified in their coverage requirements with the minimum number of multisets or sets. In this paper, we give various exact algorithms for these two problems with or without constraints on the number of times a multiset or set may be chosen. First, we show that the MSMC without multiplicity constraints problem can be solved in time and polynomial space, where is the maximum coverage requirement and denotes the total number of given multisets over . (The notation suppresses a factor polynomial in .) To our knowledge, this is the first known exact algorithm for the MSMC without multiplicity constraints problem. Second, by combining dynamic programming and the inclusion–exclusion principle, we can exactly solve the SMC without multiplicity constraints problem in time. Compared with two recent results, in [Q.-S. Hua, Y. Wang, D. Yu, F.C.M. Lau, Set multi-covering via inclusion–exclusion, Theoretical Computer Science, 410 (38–40) (2009) 3882–3892] and [J. Nederlof, Inclusion exclusion for hard problems, Master Thesis, Utrecht University, The Netherlands, 2008], respectively, ours is the fastest exact algorithm for the SMC without multiplicity constraints problem. Finally, by directly using dynamic programming, we give the first known exact algorithm for the MSMC or the SMC with multiplicity constraints problem in time and space. This algorithm can also be easily adapted as a constructive algorithm for the MSMC without multiplicity constraints problem. [Copyright &y& Elsevier]

Abstract: Set multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion–exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes time and space where is the maximum value in the coverage requirement set (The notation omits a factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion–exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)]. [Copyright &y& Elsevier]

Multi-agent decision making is a fundamental problem in edge intelligence. In this paper, we study this problem for IoT networks under the distributed Multi-Armed Bandits (MAB) model. Most of existing works for distributed MAB demand long-time stable networks connected by powerful devices and hence may not be suitable for mobile IoT networks with harsh IoT constraints. To meet the challenge of resource constraints in mobile IoT environment, we propose a lightweight and robust learning algorithm in a dynamic network allowing topology changes. In our model, each agent is assumed to have only limited memory and communicate with each other asynchronously. Moreover, we assume that the bandwidth for exchanging information is limited and each agent can transmit O (log 2 K) bits (K denotes the number of arms) per communication. Rigorous analysis shows that despite these harsh constraints, the best arm/option can be identified collaboratively by the agents and the algorithm converges efficiently. Extensive experiments illustrate that the proposed algorithm exhibits good efficiency and stability in mobile settings. [ABSTRACT FROM AUTHOR]

Given a seller with k types of items and n single-minded buyers, i.e., each buyer is only interested in a particular bundle of items, to maximize the revenue, the seller must assign some amount of bundles to each buyer with respect to the buyer's accepted price. Each buyer b i is associated with a value function v i (⋅) such that v i (x) is the accepted unit bundle price b i is willing to pay for x bundles. In this paper, we assume that bundles can be sold fractionally. The single-minded item selling problem is proved to be NP-hard. Moreover, we give an O (k) -approximation algorithm. For the online version, i.e., buyers come one by one and the decision must be made immediately on the arrival of each buyer, an O (k ⋅ (log ⁡ h + log ⁡ k)) -competitive algorithm is given, where h is the highest unit item price among all buyers. [ABSTRACT FROM AUTHOR]

In this paper, we propose a robust communication-efficient decentralized learning algorithm, named RCEDL , to address data heterogeneity , communication heterogeneity and communication efficiency simultaneously in real-world scenarios. To the best of our knowledge, this is the first work to address the above challenges in a united framework. In detail, we design a compressed cross-gradient aggregation mechanism with delay to resolve the Non-IID issues, a blocking-resilient mechanism which allows receiving delayed parameters and gradients, and a communication-efficient mechanism including parameters compression and adaptive neighbors selection methods to reduce the communication cost as much as possible. In addition, we also provide convergence analysis of RCEDL and prove its convergence rate O (1 N K ) same with the state-of-the-art decentralized learning algorithms. Finally, we conduct extensive experiments to evaluate RCEDL algorithm on two widely used datasets CIFAR-10 and MNIST under different experimental settings. Compared with the state-of-the-art baseline methods, the proposed RCEDL is much more robust with higher accuracy and at least 3.4 × communication cost reduction under the heterogeneous environment. [ABSTRACT FROM AUTHOR]