skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Thursday, October 10 until 2:00 AM ET on Friday, October 11 due to maintenance. We apologize for the inconvenience.


Title: Theoretical and Computational Characterizations of Interaction Mechanisms on Facebook Dynamics Using a Common Knowledge Model
Web-based interactions enable agents to coordinate and generate collective action. Coordination can facilitate the spread of contagion to large groups within networked populations. In game theoretic contexts, coordination requires that agents share common knowledge about each other. Common knowledge emerges within a group when each member knows the states and the thresholds (preferences) of the other members, and critically, each member knows that everyone else has this information. Hence, these models of common knowledge and coordination on communication networks are fundamentally di fferent from influence-based unilateral contagion models, such as those devised by Granovetter and Centola. Moreover, these models utilize different mechanisms for driving contagion. We evaluate three mechanisms of a common knowledge model that can represent web-based communication among groups of people on Facebook, using nine social (media) networks. We provide theoretical results indicating the intractability in identifying all node-maximal bicliques in a network, which is the characterizing network structure that produces common knowledge. Bicliques are required for model execution. We also show that one of the mechanisms (named PD2) dominates another mechanism (named ND2). Using simulations, we compute the spread of contagion on these networks in the Facebook model and demonstrate that di fferent mechanisms can produce widely varying behaviors in terms of the extent of the spread and the speed of contagion transmission. We also quantify, through the fraction of nodes acquiring contagion, di erences in the eff ects of the ND2 and PD2 mechanisms, which depend on network structure and other simulation inputs.  more » « less
Award ID(s):
1443054 1633028 1745207 1916805 1918656
NSF-PAR ID:
10300631
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Social network analysis and mining
ISSN:
1869-5450
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Web-based interactions enable agents to coordinate and generate collective action. Coordination can facilitate the spread of contagion to large groups within networked populations. In game theoretic contexts, coordination requires that agents share common knowledge about each other. Common knowledge emerges within a group when each member knows the states and the thresholds (preferences) of the other members, and critically, each member knows that everyone else has this information. Hence, these models of common knowledge and coordination on communication networks are fundamentally different from influence-based unilateral contagion models, such as those devised by Granovetter and Centola. Moreover, these models utilize different mechanisms for driving contagion. We evaluate three mechanisms of a common knowledge model that can represent web-based communication among groups of people on Facebook, using nine social (media) networks. We provide theoretical results indicating the intractability in identifying all node-maximal bicliques in a network, which is the characterizing network structure that produces common knowledge. Bicliques are required for model execution. We also show that one of the mechanisms (named PD2) dominates another mechanism (named ND2). Using simulations, we compute the spread of contagion on these networks in the Facebook model and demonstrate that different mechanisms can produce widely varying behaviors in terms of the extent of the spread and the speed of contagion transmission. We also quantify, through the fraction of nodes acquiring contagion, differences in the effects of the ND2 and PD2 mechanisms, which depend on network structure and other simulation inputs. 
    more » « less
  2. null (Ed.)
    Web-based interactions allow agents to coordinate and to take actions (change state) jointly, i.e., to participate in collective ac- tion such as a protest, facilitating spread of contagion to large groups within networked populations. In game theoretic contexts, coordination requires that agents share common knowledge about each other. Common knowledge emerges within a group when each member knows the states and the types (preferences) of the other members, and critically, each member knows that everyone else has this information. Hence, these models of common knowledge and coordination on communication networks are fundamentally different from influence-based unilateral contagion models, such as those devised by Granovetter and Centola. Common knowledge arises in many settings in practice, yet there are few operational models that can be used to compute contagion dynamics. Moreover, these models utilize different mechanisms for driving contagion. We evaluate the three mechanisms of a common knowledge model that can represent web-based communication among groups of people on Facebook. We evaluate these mechanisms on ve social (media) networks with wide-ranging properties.We demonstrate that di erent mechanisms can produce widely varying behaviors in terms of the extent of contagion spreading and the speed of contagion transmission. 
    more » « less
  3. null (Ed.)
    Web-based interactions allow agents to coordinate and to take actions (change state) jointly, i.e., to participate in collective action such as a protest, facilitating spread of contagion to large groups within networked populations. In game theoretic contexts, coordination requires that agents share common knowledge about each other. Common knowledge emerges within a group when each member knows the states and the types (preferences) of the other members, and critically, each member knows that everyone else has this information. Hence, these models of common knowledge and coordination on communication networks are fundamentally different from influence-based unilateral contagion models, such as those devised by Granovetter and Centola. Common knowledge arises in many settings in practice, yet there are few operational models that can be used to compute contagion dynamics. Moreover, these models utilize different mechanisms for driving contagion. We evaluate the three mechanisms of a common knowledge model that can represent web-based communication among groups of people on Facebook. We evaluate these mechanisms on five social (media) networks with wide-ranging properties. We demonstrate that different mechanisms can produce widely varying behaviors in terms of the extent of contagion spreading and the speed of contagion transmission. 
    more » « less
  4. Common knowledge (CK) is a phenomenon where each individual within a group knows the same information and everyone knows that everyone knows the information, infinitely recursively. CK spreads information as a contagion through social networks in ways different from other models like susceptible-infectious-recovered (SIR) model. In a model of CK on Facebook, the biclique serves as the characterizing graph substructure for generating CK, as all nodes within a biclique share CK through their walls. To understand the effects of network structure on CK-based contagion, it is necessary to control the numbers and sizes of bicliques in networks. Thus, learning how to generate these CK networks (CKNs) is important. Consequently, we develop an exponential random graph model (ERGM) that constructs networks while controlling for bicliques. Our method offers powerful prediction and inference, reduces computational costs significantly, and has proven its merit in contagion dynamics through numerical experiments. 
    more » « less
  5. null (Ed.)
    Protest is a collective action problem and can be modeled as a coordination game in which people take an action with the potential to achieve shared mutual benefits. In game-theoretic contexts, successful coordination requires that people know each others' willingness to participate, and that this information is common knowledge among a sufficient number of people. We develop an agent-based model of collective action that was the first to combine social structure and individual incentives. Another novel aspect of the model is that a social network increases in density (i.e., new graph edges are formed) over time. The model studies the formation of common knowledge through local interactions and the characterizing social network structures. We use four real-world, data-mined social networks (Facebook, Wikipedia, email, and peer-to-peer networks) and one scale-free network, and conduct computational experiments to study contagion dynamics under different conditions. 
    more » « less