Source author record

Joseph Peters

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.CO Social and Information Networks Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

How to go Viral: Cheaply and Quickly

Given a social network represented by a graph $G$ , we consider the problem of finding a bounded cardinality set of nodes $S$ with the property that the influence spreading from $S$ in $G$ is as large as possible. The dynamics that govern the spread of influence is the following: initially only elements in $S$ are influenced; subsequently at each round, the set of influenced elements is augmented by all nodes in the network that have a sufficiently large number of already influenced neighbors. While it is known that the general problem is hard to solve --- even in the approximate sense --- we present exact polynomial time algorithms for trees, paths, cycles, and complete graphs.

preprint2015arXiv

Spread of Influence in Weighted Networks under Time and Budget Constraints

Given a network represented by a weighted directed graph G, we consider the problem of finding a bounded cost set of nodes S such that the influence spreading from S in G, within a given time bound, is as large as possible. The dynamic that governs the spread of influence is the following: initially only elements in S are influenced; subsequently at each round, the set of influenced elements is augmented by all nodes in the network that have a sufficiently large number of already influenced neighbors. We prove that the problem is NP-hard, even in simple networks like complete graphs and trees. We also derive a series of positive results. We present exact pseudo-polynomial time algorithms for general trees, that become polynomial time in case the trees are unweighted. This last result improves on previously published results. We also design polynomial time algorithms for general weighted paths and cycles, and for unweighted complete graphs.

preprint2012arXiv

Consensus vs Broadcast in Communication Networks with Arbitrary Mobile Omission Faults

We compare the solvability of the Consensus and Broadcast problems in synchronous communication networks in which the delivery of messages is not reliable. The failure model is the mobile omission faults model. During each round, some messages can be lost and the set of possible simultaneous losses is the same for each round. We investigate these problems for the first time for arbitrary sets of possible failures. Previously, these sets were defined by bounding the numbers of failures. In this setting, we present a new necessary condition for the solvability of Consensus that unifies previous impossibility results in this area. This condition is expressed using Broadcastability properties. As a very important application, we show that when the sets of omissions that can occur are defined by bounding the numbers of failures, counted in any way (locally, globally, etc.), then the Consensus problem is actually equivalent to the Broadcast problem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.