Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
SUBMODULARITY OF INFLUENCE IN SOCIAL NETWORKS: FROM LOCAL TO GLOBAL
Ist Teil von
SIAM journal on computing, 2010-01, Vol.39 (6), p.2176-2188
Ort / Verlag
Philadelphia, PA: Society for Industrial and Applied Mathematics
Erscheinungsjahr
2010
Quelle
EBSCOhost Business Source Ultimate
Beschreibungen/Notizen
Social networks are often represented as directed graphs, where the nodes are individuals and the edges indicate a form of social relationship. A simple way to model the diffusion of ideas, innovative behavior, or "word-of-mouth" effects on such a graph is to consider an increasing process of "infected" (or active) nodes: each node becomes infected once an activation function of the set of its infected neighbors crosses a certain threshold value. Such a model was introduced by Kempe, Kleinberg, and Tardos (KKT), where the authors also impose several natural assumptions: the threshold values are random and the activation functions are monotone and submodular. The monotonicity condition indicates that a node is more likely to become active if more of its neighbors are active, while the submodularity condition indicates that the marginal effect of each neighbor is decreasing when the set of active neighbors increases. Here, the authors prove a conjecture of KKT: they show that the function ... is submodular under the assumptions above.(ProQuest: ... denotes formulae/symbols omitted.)