Social networks have become a huge interdisciplinary research area with important links to sociology, economics, epidemiology, computer science, and mathematics.
We introduce a new threshold model of social networks, in which the nodes influenced by their neighbours can adopt one out of several alternatives. We characterize
social networks for which adoption of a product by the whole network is possible (respectively necessary) and the ones for which a unique outcome is guaranteed.
We also study algorithmic questions concerning these networks. In particular we consider the problem of computing the minimum (resp. maximum) possible spread
of a product and the problem of determining whether a given node has to adopt some (resp. a given) product in all final networks.
Some of these problems are efficiently computable, while others are co-NP complete, or NP-hard to approximate with an approximation ratio better than Omega(n).
This is a joint work with Evangelos Markakis.
back to the list of talks