|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
ChoiceGAPs: Competitive Diffusion as a Massive Multi-Player Game in Social Networks | | Edoardo Serra
; Francesca Spezzano
; V.S. Subrahmanian
; | | Date: |
22 Oct 2014 | | Abstract: | We consider the problem of modeling competitive diffusion in real world
social networks via the notion of ChoiceGAPs which combine choice logic
programs due to Sacca’ and Zaniolo and Generalized Annotated Programs due to
Kifer and Subrahmanian. We assume that each vertex in a social network is a
player in a multi-player game (with a huge number of players) - the choice part
of the ChoiceGAPs describe utilities of players for acting in various ways
based on utilities of their neighbors in those and other situations. We define
multi-player Nash equilibrium for such programs - but because they require some
conditions that are hard to satisfy in the real world, we introduce a new
model-theoretic concept of strong equilibrium. We show that stable equilibria
can capture all Nash equilibria. We prove a host of complexity (intractability)
results for checking existence of strong equilibria (as well as related
counting complexity results), together with algorithms to find them. We then
identify a class of ChoiceGAPs for which stable equilibria can be polynomially
computed. We develop algorithms for computing these equilibria under various
restrictions. We come up with the important concept of an estimation query
which can compute quantities w.r.t. a given strong equilibrium, and approximate
ranges of values (answers) across the space of strong equilibria. Even though
we show that computing range answers to estimation queries exactly is
intractable, we are able to identify classes of estimation queries that can be
answered in polynomial time. We report on experiments we conducted with a
real-world FaceBook data set surrounding the 2013 Italian election showing that
our algorithms have good predictive accuracy with an Area Under a ROC Curve
that, on average, is over 0.76. | | Source: | arXiv, 1410.6118 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER