Given a network N and a set of nodes that are the starting point for the spread of misinformation across N and an integer k, in the influence blocking maximization problem the goal is to find k nodes in N as the starting point for a competing information (say, a correct information) across N such that the reach of the misinformation is minimized. In this paper we deal with a more realistic scenario for this problem where different nodes have different costs and the counter strategy has a “budget” for picking nodes for a solution. Our experimental results show that the success of a given strategy varies substantially depending on the cost function in the model. In particular, we investigate the cost function where all nodes have cost 1 and a cost function that assigns higher costs to higher degree nodes. We show that, even though strategies that perform well in these two diverse cases are very different from each other, both correlate well with simple (but different) strategies: greedily choose high degree nodes and choose nodes uniformly at random.

In this work we investigate the problem of estimating the percolation centrality of every vertex in a graph. This centrality measure quantifies the importance of each vertex in a graph going through a contagious process. It is an open problem whether the percolation centrality can be computed in O(n3-c) time, for any constant c>0. In this paper we present a ~O(m) randomized approximation algorithm for the percolation centrality for every vertex of G, generalizing techniques developed by Riondato, Upfal and Kornaropoulos. The estimation obtained by the algorithm is within ε of the exact value with probability 1- δ, for fixed constants 0 < ε,δ < 1. In fact, we show in our experimental analysis that in the case of real-world complex networks, the output produced by our algorithm is significantly closer to the exact values than its guarantee in terms of theoretical worst case analysis.

We consider a game-theoretic bin packing problem with identical items, and we study the convergence time to a Nash equilibrium. In the model proposed, users choose their strategy simultaneously. We deal with two bins and multiple bins cases. We consider the case when users know the load of all bins and a case with less information. We consider two approaches, depending if the system can undo movements that lead to infeasible states. In the two bins case, we show an O (log log n) bound when undo movements are allowed. In multiple bins case, we show an O (log n) and an O (nm) bounds when undo movements are allowed and when they are not allowed, respectively. In the case with less information, we show an O (m log n) and an O (n3m) bounds when undo movements are allowed and when they are not allowed, respectively.

The importance of digital information is constantly increasing in the last years. Such information often needs to be preserved for a long-term and this is the responsibility of digital archiving systems. This paper proposes a reliable replication model of immutable digital content to be used in long-term archiving systems. The archiving system is modeled as a set of storage repositories where each repository has an independent fail probability assigned to it. Items are inserted with a reliability that is satisfied by replicating them in subsets of repositories. Through simulation, we evaluated three different proposed strategies to create replicas. It is also proposed a completely distributed archiving system using this model over a structured peer-to-peer (P2P) network. The communication between the nodes (repositories) of the network is organized in a distributed hash table and multiple hash functions are used to select repositories that will keep the replicas of each stored item. The system is evaluated through experiments in a real environment. The proposed model and the algorithms, combined with the structured P2P scalability made possible the construction of a reliable and totally distributed digital archiving system.