Piet Van Mieghem

Stojan Trajanovski, Yezekael Hayel, Eitan Altman et al.

Defining an optimal protection strategy against viruses, spam propagation or any other kind of contamination process is an important feature for designing new networks and architectures. In this work, we consider decentralized optimal protection strategies when a virus is propagating over a network through a SIS epidemic process. We assume that each node in the network can fully protect itself from infection at a constant cost, or the node can use recovery software, once it is infected. We model our system using a game theoretic framework and find pure, mixed equilibria, and the Price of Anarchy (PoA) in several network topologies. Further, we propose both a decentralized algorithm and an iterative procedure to compute a pure equilibrium in the general case of a multiple communities network. Finally, we evaluate the algorithms and give numerical illustrations of all our results.

Stojan Trajanovski, Fernando A. Kuipers, Yezekael Hayel et al.

Designing an optimal network topology while balancing multiple, possibly conflicting objectives like cost, performance, and resiliency to viruses is a challenging endeavor, let alone in the case of decentralized network formation. We therefore propose a game-formation technique where each player aims to minimize its cost in installing links, the probability of being infected by a virus and the sum of hopcounts on its shortest paths to all other nodes. In this article, we (1) determine the Nash Equilibria and the Price of Anarchy for our novel network formation game, (2) demonstrate that the Price of Anarchy (PoA) is usually low, which suggests that (near-)optimal topologies can be formed in a decentralized way, and (3) give suggestions for practitioners for those cases where the PoA is high and some centralized control/incentives are advisable.

Gabriel Budel, Ying Jin, Piet Van Mieghem et al.

Interpreting natural language is an increasingly important task in computer algorithms due to the growing availability of unstructured textual data. Natural Language Processing (NLP) applications rely on semantic networks for structured knowledge representation. The fundamental properties of semantic networks must be taken into account when designing NLP algorithms, yet they remain to be structurally investigated. We study the properties of semantic networks from ConceptNet, defined by 7 semantic relations from 11 different languages. We find that semantic networks have universal basic properties: they are sparse, highly clustered, and many exhibit power-law degree distributions. Our findings show that the majority of the considered networks are scale-free. Some networks exhibit language-specific properties determined by grammatical rules, for example networks from highly inflected languages, such as e.g. Latin, German, French and Spanish, show peaks in the degree distribution that deviate from a power law. We find that depending on the semantic relation type and the language, the link formation in semantic networks is guided by different principles. In some networks the connections are similarity-based, while in others the connections are more complementarity-based. Finally, we demonstrate how knowledge of similarity and complementarity in semantic networks can improve NLP algorithms in missing link inference.

Qiang Liu, Xiaoyu Zhou, Piet Van Mieghem

In networked spreading models, each node can infect its neighbors and cure spontaneously. The curing is assumed to occur uniformly over time. A pulse immunization/curing strategy is more efficient and broadly applied to suppressing spreading processes. We model the epidemic process by the basic Susceptible-Infected (SI) process with a pulse curing and incorporate the underlying contact network. The mean-field epidemic threshold of the pulse SI model is shown to be $\frac{1}{λ_1}\ln\frac{1}{1-p}$, where $λ_1$ and $p$ are the largest eigenvalue of the adjacency matrix and the fraction of nodes covered by each curing, respectively. Compared to the extensively studied uniform curing process, we show that the pulse curing strategy saves about $36.8$\%, i.e. $p\approx 0.632$, of the number of curing operations invariant to the network structure. Our results may help related policy makers to estimate the cost of controlling spreading processes.