Abstract Parameterized complexity, introduced to efficiently solve NP‐hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity () for several graph theoretic problems in : Maximum ‐Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular‐width () and consequently—as is a special case of —by . However, the proposed novel algorithms allow for improving the computational complexity from time —where and denote, respectively, the number of vertices and edges in the input graph—to time which is only additive in the size of the input. Then we consider some classical NP‐hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter.

Abstract We consider the problem of keeping under control the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node’s resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and $$\ell $$ ℓ , is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most $$\ell $$ ℓ nodes? We consider several parameters associated with the input, including the bounds k and $$\ell $$ ℓ , the maximum node degree $$\Delta $$ Δ , the number $$\zeta $$ ζ of initially contaminated nodes, the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.

Given a discrete random variable X that takes values in a finite set χ according to a probability mass function (pmf) P, a truncated pmf Q of P is a conditional pmf that results from restricting the domain of X to some subset of χ. Truncated pmf arise in several problems of statistics and probability. In this paper, we propose and analyze a few criteria to truncate pmf's so that the truncated one is as much close as possible to the original pmf, under different information theoretic measures of distance.

Given two discrete random variables X and Y, with probability distributions p = (p1, ..., pn) and q = (q1, ..., qm), respectively, let us denote by C(p, q) the set of all couplings of p and q, that is, the set of all bivariate probability distributions that have p and q as marginals. In this paper, we study the problem of finding a joint probability distribution in C(p, q) of minimum entropy (equivalently, a coupling that maximizes the mutual information between X and Y), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in C(p, q) with entropy exceeding the minimum possible at most by 1 bit, thus providing an approximation algorithm with an additive gap of at most 1 bit. Leveraging on this algorithm, we extend our result to the problem of finding a minimum-entropy joint distribution of arbitrary k ≥ 2 discrete random variables X1, ..., Xk, consistent with the known k marginal distributions of the individual random variables X1, ..., Xk. In this case, our algorithm has an additive gap of at most log k from optimum. We also discuss several related applications of our findings and extensions of our results to entropies different from the Shannon entropy.

We consider a population of interconnected individuals that, with respect to a piece of information, at each time instant can be subdivided into three (time‐dependent) categories: agnostics, influenced, and evangelists. A dynamical process of information diffusion evolves among the individuals of the population according to the following rules. Initially, all individuals are agnostic. Then, a set of people is chosen from the outside and convinced to start evangelizing, that is, to start spreading the information. When a number of evangelists, greater than a given threshold, communicate with a node v, the node v becomes influenced, whereas, as soon as the individual v is contacted by a sufficiently much larger number of evangelists, it is itself converted into an evangelist and consequently it starts spreading the information. The question is: How to choose a bounded cardinality initial set of evangelists so as to maximize the final number of influenced individuals? We prove that the problem is hard to solve, even in an approximate sense. On the positive side, we present exact polynomial time algorithms for trees and complete graphs. For general graphs, we derive exact parameterized algorithms. We also study the problem when the objective is to select a minimum number of evangelists capable of influencing the whole network. Our motivations to study these problems come from the areas of Viral Marketing and spread of influence in social networks. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 346–357 2018

It is well known that the entropy $H(X)$ of a discrete random variable $X$ is always greater than or equal to the entropy $H(f(X))$ of a function $f$ of $X$, with equality if and only if $f$ is one-to-one. In this paper, we give tight bounds on $H(f(X))$ when the function $f$ is not one-to-one, and we illustrate a few scenarios where this matters. As an intermediate step towards our main result, we derive a lower bound on the entropy of a probability distribution, when only a bound on the ratio between the maximal and minimal probabilities is known. The lower bound improves on previous results in the literature, and it could find applications outside the present scenario.

It is well known that the entropy H (X) of a finite random variable is always greater or equal to the entropy H (f (X)) of a function f of X, with equality if and only if f is one-to-one. In this paper, we give tights bounds on H(f (X) when the function f is not one-to-one, and we illustrate a few scenarios where this matters. As an intermediate step towards our main result, we prove a lower bound on the entropy of a probability distribution, when only a bound on the ratio between the maximum and the minimum probability is known. Our lower bound improves previous results in the literature, and it could find applications outside the present scenario.

Given two discrete random variables X and Y, with probability distributions p = (p1, ..., pn) and q = (q1, ..., qm), respectively, denote by C(p, q) the set of all joint distributions of X and Y that have p and q as marginals. In this paper, we study the problem of finding the joint probability distribution in C (p, q) of minimum entropy (equivalently, the joint probability distribution that maximizes the mutual information between X and Y), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in C(p, q) with entropy exceeding the minimum possible by at most 1, thus providing an approximation algorithm with additive approximation factor of 1. We also discuss some related consequences of our findings.

We consider the following multi-level opinion spreading model on networks. Initially, each node gets a weight, from the set {0,. . .,k – 1}, which measures the individual conviction of a new idea or product. Then, by proceeding in rounds, each node updates its weight according to those of its neighbours. We study k-dynamos that are initial assignments of weights leading each node to get the value k – 1 – e.g. unanimous maximum level of acceptance – within a given number of rounds; the goal is to minimize the sum of the initial weights of the nodes. We determine lower bounds on the sum of the initial weights under the irreversible simple majority rules, where a node increases its weight if and only if the majority of its neighbours have a weight that is higher than its own. We study the relations among 2-dynamos and k-dynamos, with and without a bound on the number of rounds needed to reach the desired all-(k – 1) configuration. Moreover, we provide constructive tight upper bounds for some classes of regular topologies: rings, tori and cliques.

Given a probability distribution p = (p1, ..., pn) and an integer m1, ..., qm) that is “the closest” to p, that is, that best approximates p? It is clear that the answer depends on the function one chooses to evaluate the goodness of the approximation. In this paper we provide a general criterion to approximate p with a shorter vector q by using ideas from majorization theory. We evaluate the goodness of our approximation by means of a variety of information theoretic distance measures.

Identifying the most influential spreaders is an important issue for the study of the dynamics of information diffusion in complex networks. In this paper we analyze the following spreading model. Initially, a few nodes know a piece of information and are active spreaders of it. At subsequent rounds, spreaders communicate the information to their neighbors. Upon receiving the information, a node becomes aware of it but does not necessarily become a spreader; it starts spreading only if it gets the information from a sufficiently large number of its neighbors. We study the problem of choosing a small set of initial spreaders so as to maximize the final number of nodes that become aware of the information.

We study the influence diffusion problem in online social networks. Formally, given a network represented by a directed graph G = (V,E), we consider a process of influence diffusion in G that proceeds as follows: Initially only the vertices of a given S ⊆ V are influenced; subsequently, at each round, the set of influenced vertices is augmented by all the vertices in the network that have a sufficiently large number of already influenced incoming neighbors. The question is to find a small subset of vertices that can influence the whole network (target set). This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known to be hard to approximate within a factor of 2log1--ϵn, for any ϵ > 0, and n = |V |.

We introduce two new information theoretic measures of distances among probability distributions and we discuss their possible applications to Econometrics.

Abstract The Chord protocol is the best known example of implementation of logarithmic complexity routing for structured peer‐to‐peer networks. Its routing algorithm, however, does not provide an optimal trade‐off between resources exploited (the size of the ‘finger table’) and performance (the average or worst‐case number of hops to reach destination). Cordasco et al. showed that a finger table based on Fibonacci distances provides lower number of hops with fewer table entries. In this paper we generalize this result, showing how to construct an improved finger table when the objective is to reduce the number of hops, possibly at the expense of an increased size of the finger table. Our results can also be exploited to guarantee low routing time in case a fraction of nodes fails. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract We propose a family of novel Chord‐based P2P schemes retaining all positive aspects that made Chord a popular topology for routing in P2P networks. The schemes, based on the Fibonacci number system, allow to simultaneously improve on the maximum/average number of hops for lookups and the routing table size per node. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

The well known Tunstall algorithm for discrete memoryless sources [17] produces optimal variable-to-fixed length source codes that maximize the expected number of source letters per codeword. Tun stall algorithm achieves this result by constructing parse trees with maximum average height for the source output. In the first part of this paper we introduce a simple variant of Tun stall algorithm in order to optimizes additional natural cost functions of interest. For instance we show how to select, among all parse trees with maximum average height, those having minimum height, minimum variance, minimum external length, and more general natural parameters. In the second part of the paper we consider the problem of selecting, among all parse trees of height bounded by some parameter L, those parse trees having maximum average height. We motivate the problem, and we quantify the loss of performance these parse trees suffer with respect to unrestricted Tuns tall parse trees, when they are used as variable-to-fixed length encoding for a discrete memoryless source.

The chord protocol is the best known example of implementation of logarithmic complexity routing for structured peer-to-peer networks. Its routing algorithm, however, does not provide an optimal trade-off between resources exploited (the size of the "finger table") and performance (the average or worst-case number of hops to reach destination). Cordasco et al. showed that a finger table based on Fibonacci distances provides lower number of hops with fewer table entries. In this paper, we generalize this result, showing how to construct an improved finger table when the objective is to reduce the number of hops, possibly at the expense of an increased size of the finger table. Our results can also be exploited to guarantee low routing time in case a fraction of nodes is assumed to fail.

In this correspondence, we prove that the probability distribution induced on the leaves of a Tunstall parse tree for a given source is a (unique) lower bound in the partially ordered set of the probability distributions induced by all possible parse trees with a same number of leaves, and ordered according to the majorization partial order. We apply this result to the problem of optimally approximating a uniform distribution with flips of a biased coin

We propose routing schemes that optimize the average number of hops for lookup requests in peer-to-peer (P2P) systems without adding any overhead to the system. Our work is inspired by the recently introduced variation of greedy routing, called neighbor-of-neighbor (NoN), which allows to get optimal average path length with respect to the degree. Our proposal has the advantage of first "limiting" and then "eliminating" the use of randomization. As a consequence, the NoN technique can be implemented with our schemes without adding any overhead. Analyzed networks include several popular topologies: chord, hypercube based networks, symphony, skip-graphs. Theoretical results and extensive simulations show that the proposed simplifications (while maintaining the original node degree) do not increase the average path length of the networks, which is often improved in practice. The improvement is obtained with no harm to the operational efficiency (e.g. stability, ease of programming, scalability, fault-tolerance) of the considered systems.

Summary form only given. We study on-demand source initiated protocols for mobile wireless networks. In particular, we study the flooding procedure commonly used by these protocols to set up temporary communication paths. The benefit of the flooding technique is its generosity regarding changes in network structure. On the other hand, each time a message is sent, the entire network will be involved to set up the communication path from the source node, to the target node. We propose a new approach, which we call limited broadcasting. It is aimed to reduce the overhead by localizing the search for the target node both in terms of the time the process needs to globally stop after the target has been reached and/or in terms of the region which is affected by the search. It works in unknown networks and does not need any kind of additional information.

Greedy routing has been used in most of the proposed P2P networks because of several reasons. One of the main advantages is that greedy routing is very simple to implement and has some “implicit” fault-tolerance capabilities. It was however noticed that greedy routing usually produces paths of length larger than what would be required in a network of the given node degree. As an example some popular topologies like Chord have degree O(log n) and the greedy routing produces an average path length O(log n) whereas the lower bound is Ω(log n/log log n). The use of randomization allowed to show networks with optimal average path length. Recently a novel approach for routing in DHTs which improves on greedy routing has been proposed [4]. This approach, called NoN (Neighbors–of–Neighbors), substantially consists in making the greedy choice by looking not only at the neighbors of a node but at all the nodes at distance at most 2 from the node itself. The NoN approach together with the use of randomization in establishing the neighbors of the nodes which are present in the network, can optimally reduce the latency in several well known topologies. Hence the use of randomization, inspired by the Small-world idea introduced by Kleinberg [2], together with the NoN routing allows to maintain, to some extent, the advantages of greedy routing while optimizing the latency. Our goal is to retain the improvements given by the NoN routing over randomized networks, while eliminating the drawback in system overhead implied by this technique. In fact, randomization and NoN routing require the transmission to a node of its neighbors’s neighbors. While the authors in [4] argue that this can be done without extra cost by using keep-alive TCP messages, we eliminate the extracommunication at all and, similarly, eliminate the need of storing in each node its neighbors’s neighbors. To this aim we need to eliminate the random factor in establishing each neighbor of a node. In fact, determinism allows each node to calculate locally the neighbors of its neighbors. ∗ Work partially supported by EU RTN project ARACNE and by Italian FIRB WEBMINDS project

Abstract We consider the problem of disseminating messages in networks. We are interested in information dissemination algorithms in which machines operate independently without any knowledge of the network topology or size. Three communication tasks of increasing difficulty are studied. In blind broadcasting (BB), the goal is to communicate the source message to all nodes. In acknowledged blind broadcasting (ABB), the goal is to achieve BB and inform the source about it. Finally, in full synchronization (FS), all nodes must simultaneously enter the state terminated after receiving the source message. The algorithms should be efficient both in terms of the time required and the communication overhead they put on the network. We limit the latter by allowing every node to send a message to at most one neighbor in each round. We show that BB is achieved in time at most 2n in any n‐node network and show networks in which time 2n − o(n) is needed. For ABB, we show algorithms working in time (2 + ϵ)n, for any fixed positive constant ϵ and sufficiently large n. Thus, for both BB and ABB, our algorithms are close to optimal. Finally, we show a simple algorithm for FS working in time 3n and a more complicated algorithm which works in time 2.9n. The optimal time of full synchronization remains an open problem. © 2001 John Wiley & Sons, Inc.

Given a random variable X which takes n equiprobable values, we consider several algorithmic questions related to the classical problem of simulating the outcomes of X by using a limited number of biased coins.

Collective communication operations play an important role in message-passing systems and have been extensively investigated. We study two widely used collective communication operations: gossiping and all-to-all personalized communication. We assume the multiport postal model of communication that seems particularly suited for developing fast and portable algorithms on current technology parallel computers. Unlike most of the previous work on the subject, we assume that processors communicate by sending messages of limited size. Indeed, when the maximum size of a message is fixed, the number of rounds required by a communication algorithm gives a realistic measure of the performance of the algorithm. We provide an optimal algorithm for the gossiping operation and an almost-optimal algorithm for the all-to-all personalized communication operation. © 1998 John Wiley & Sons, Inc. Networks 31:67–79, 1998

Gossiping is the process of information diffusion in which each node of a network holds a packet that must be communicated to all other nodes in the network. We consider the problem of gossiping in communication networks under the restriction that communicating nodes can exchange up to a fixed number p of packets at each round. In the first part of the paper we study the extremal case p=1 and we exactly determine the optimal number of communication rounds to perform gossiping for several classes of graphs, including Hamiltonian graphs and complete k-ary trees. For arbitrary graphs we give asymptotically matching upper and lower bounds. We also study the case of arbitrary p and we exactly determine the optimal number of communication rounds to perform gossiping under this hypothesis for complete graphs, hypercubes, rings, and paths. Finally, we investigate the problem of determining sparse networks in which gossiping can be performed in the minimum possible number of rounds.

Abstract Broadcasting is the process of disseminating a message originated at one node of a network to all other nodes. In this paper, we consider the problem of broadcasting reliably in the hypercube in presence of either transmission or link failures. We propose broadcasting protocols under various assumptions on the communication model. Our broadcasting protocols make use of Rabin's Information Dispersal Algorithm. © 1993 by John Wiley & Sons, Inc.

Abstract Consider a network in which n processors are connected by unreliable lines and are allowed to communicate with at most one other processor at a time. In this paper, the problems of broadcasting and gossiping are considered. Broadcast is the task of transmitting a message, originated at one node, to all other nodes in the network. Gossiping refers to the process of information dissemination when each processor knows a unique item of information and must transmit it to all the other processors in the network. In this paper, new bounds on fault‐tolerant broadcasting and gossiping times are obtained. The given bounds improve on previously known results. In particular, if n is a power of two, the given broadcast and gossiping schemes require minimum time and are supported by a network having the minimum possible number of edges.

Consider a network in which n processors are connected by communication lines and are allowed to communicate with at most one other processor at a time. Broadcast is the task of transmitting a message originated at one node to all other nodes in the network. Presented in this paper is a broadcasting scheme that can tolerate up to $k\leqq \lfloor \log \,n \rfloor $ line failures; that is, it assures that each node in the network will receive the message from the originator when up to $k \leqq \lfloor \log n \rfloor $ lines are faulty. The time required by the broadcast protocol is minimum, except in some cases that might require one unit of time more than the minimum. Moreover, an algorithm for constructing networks supporting the broadcast scheme and having approximately the minimum possible number of lines is given.

The problem of constructing statistically synchronizable codes over arbitrary alphabets and for any finite source is considered. It is shown how to efficiently construct a statistically synchronizable code whose average codeword length is within the least likely codeword probability from that of the Huffman code for the same source. Moreover, a method is given for constructing codes having a synchronizing codeword. The method yields synchronous codes that exhibit high synchronizing capability and low redundancy.>

Abstract Broadcast is the task of transmitting a message originated at a node in a network to all the other nodes. In this paper, we consider the problem of constructing minimal broadcast networks, that is, communication networks such that broadcast can be performed, from any node, in minimum time. The algorithms we propose allow us to improve known bounds on the minimum number of communication lines needed in minimal broadcast networks. We give some numerical evidence that our algorithms also perform well in practice.

Immutable codes, which have recently been introduced as a tool for preventing undesirable changes of data recorded over write-once memories, are considered. The have the property that any change of recorded information over such memories can be detected. A fast algorithm for testing whether a variable-length code is immutable is presented. The complexity of the algorithm is O(L/sup 2/), where L is the sum of the codeword lengths.>

The authors consider statistically synchronizable variable-length codes, i.e. codes that admit decoders able to self-synchronize with high probability if the input sequence of code symbols is long enough. They show that a necessary and sufficient condition for the existence of a statistically self-synchronizing decoder and, therefore, for a code to be statistically synchronizable, is that the code has a synchronizing sequence. They also give a decision procedure to test whether a code has a synchronizing sequence. Finally, they specialize the procedure to obtain a simple and efficient algorithm to test the statistical synchronizability property of prefix codes.>