Controlling Segregation in Social Network Dynamics as an Edge Formation Game

(1) By representing the social network as a directed stochastic block model (DiSBM)[11], Section 2 formulates an edge formation game and shows that it leads to a Nash equilibrium where the network is segregated.

(2) Section 3 proposes an Algorithmic Recommendation Mechanism (ARM) which offers users additional rewards by inter-community recommendation. Incorporating this mechanism leads to a Bertrand-like game [12] with a unique Nash equilibrium where segregation is mitigated.

(3) Section 4 considers the case where ARM’s recommendation acceptance probability evolves as a semi-Markov process. Analysis within a stochastic game framework shows that users in the network reach the time-evolving Nash equilibrium of the resulting game.

(4) Finally, Section 5 presents numerical simulations to illustrate how the proposed ARM mitigates segregation and increases inter-community connections. The numerical study also suggests that higher recommendation acceptance probability is effective during polarizing events where the level of segregation is high.

(1) Social network segregation: Agent-based opinion dynamics models [6, 13, 14, 15] are the mainstream approach to study the segregation on social networks. Sasahara et al. [6] introduced social influence and unfriending into their model, where users can change both their opinions and connections based on the received information. Baumann et al. [13] proposed a radicalization mechanism which reinforces extreme opinions from moderate initial conditions. Banisch and Olbrich [14] considered the social feedback’s effect on users expressing alternative opinions and analyzed the sufficient conditions for stable bi-polarization on a stochastic block model-structured network. Blex and Yasseri [15] proposed a network-based solution to the Schelling’s model and derived that algorithmic bias in the form of rewiring is incapable of preventing segregation.

(2) Nash equilibrium analysis of social networks: Game theory is a widely used analysis tool for social networks. Jackson and Wolinsky [17] analyzed the stability and efficiency of social networks when self-interested users can form or cut links in a game setting. Bramoullé et al. [18] studied the edge formation as individual players choosing their partners in a 2-by-2 anti-coordination games. Avin et al. [19] constructed an evolutionary network formation game and demonstrated that preferential attachment is the unique Nash equilibrium. Alon et al. [20] formulated a game-theoretic model to deal with the incentives of interested parties outside the network in information diffusion. Mele [21] proposed a potential game on a network where user’s payoff depends on both directed links and link externalities. Game theoretic models have also been applied to structure identification of industrial cyber-physical systems [22], conflict mitigation through third party interventions [23], and trust management mechanism in mobile ad hoc network [24].

(3) Weak Ties and segregation mitigation strategies: In this paper, we propose an Algorithmic Recommendation Mechanism (ARM); an overview of the framework is shown in Fig. 2. The ARM incorporates the positive effect of weak ties, or ”friends of a friend”. Granovetter’s work [10] on Weak Ties-theory demonstrates that a person’s weak contacts are more likely to bring novel information such as job opportunities to him compared with his close contacts. Liu et al. [25] discussed the increased online weak ties with the emergence of new media platforms and functions such as ”follow the post”, and ”retweet”. Mele [21] proposed a network formation model involving indirect connections, which is an extended version of weak tie.

  Protocol 1. DiSBM Based Network Edge Formation  

Input: $G^{(t)}\textrm{=}\{V,E^{(t)}\}$ where $V\textrm{=}R\cup B$, $t=0,1,2,\cdots$

Output: $p_{R}^{(t)},p_{B}^{(t)}$

Process:

1. 1)

   $p_{R}^{(0)},p_{B}^{(0)}\sim\textrm{Unif}[0,1]$ (i.e., the initial parameters of the model are sampled from a uniform distribution).

2. 2)

   At each odd time instant (i.e., $t=1,3,5,\cdots$), red users take actions according to steps 2.1 and 2.2 below while the blue users adhere to the action they adopted at time $t-1$.

   • 2.1)

     $\forall i,j\in R$, $i$ connects with $j$ with probability³³3As will be discussed in the proof of Theorem 1 (Appendix A.1), $\mathbb{E}\left\{U_{i}^{(t)}\right\}$ is identical for any $i\in R$ and is a function of $p_{R}^{(t)}$.

     $${p_{R}^{(t)}}=\displaystyle\operatorname*{argmax}_{p_{R}^{(t)}\in(0,1]}\mathbb{E}\left\{U_{i}^{(t)}\right\}$$

     (4)

     where $\mathbb{E}$ is the expectation with respect to the probability distribution induced by the DiSBM model, and $U_{i}^{(t)}$ is the utility function defined in (2).

   • 2.2)

     $\forall i\in R,j\in B$, $i$ connects with $j$ with probability $\frac{1-p_{R}^{(t)}}{N}$.

3. 3)

   At each even time instant (i.e., $t=2,4,6,\cdots$), blue users take actions according to steps 3.1 and 3.2 below while the red users adhere to the action they adopted at time $t-1$.

   • 3.1)

     $\forall i,j\in B$, $i$ connects with $j$ with probability

     $${p_{B}^{(t)}}=\displaystyle\operatorname*{argmax}_{p_{B}^{(t)}\in(0,1]}\mathbb{E}\left\{U_{i}^{(t)}\right\}$$

     (5)

   • 3.2)

     $\forall i\in B,j\in R$, $i$ connects with $j$ with probability $\frac{1-p_{B}^{(t)}}{N}$.

Protocol 1 induces a DiSBM characterised by best response strategy:

In Protocol 1, red users and blue users take actions alternatively by maximizing utility functions. More specifically, at each odd time instant $t$, red users choose the probability ${p_{R}^{(t)}}$ via maximizing the expected utility of a sample uniformly drawn from the red community $R$, while blue users keep the probability ${p_{B}^{(t)}={p_{B}^{(t-1)}}}$. Blue users choose their parameters at even time steps according to similar steps. Therefore, Protocol 1 can be viewed as a DiSBM with time varying parameters resulting from the best response strategies played by users in the network. In other words, Protocol 1 corresponds to a DiSBM with the probability matrix

where $p_{R}^{(t)},p_{B}^{(t)}$ are the best response strategies taken by the red and blue users at each time instant, respectively.

Protocol 1 corresponds to the regime with dense intra- and sparse inter-community edges:

In the context of real world social networks, Protocol 1 corresponds to the regime with sparse inter-community edges and dense intra-community edges.⁴⁴4Note that $P^{(t)}$ does not need to be symmetric considering that the edges are directed; also the rows or columns in $P^{(t)}$ (given in (6)) do not need to sum to $1$. In other words, the the probability matrix $P^{(t)}$ is of the form,

A connection probability matrix of the form (7) emulates the structure of many real world social networks where individuals are densely connected within a community (i.e., $O(N^{2})$ edges within a community of size $N$) and sparsely connected between communities (i.e., $O(N)$ edges between two communities each of size $N$).

  Algorithm 1. Algorithmic Recommendation Mechanism (ARM)   Input: $E^{(t)}$ – the edge set at time $t$ and $R,B$ – the two node sets representing two communities.

Output: $\{(i,j)\}$ – the set of recommendation links.

Process: At time $t$, for any ordered pair $(i,j)$ such that $i,j$ are in different communities, ARM forms an edge from $i$ to $j$ according to steps below:

1. 1)

   If $j$ follows $i$, i.e., $(i,j)\in E^{(t)}$, then stop recommendation; otherwise proceed to step $2$.

2. 2)

   For any user $j^{\prime}$ such that $S^{(t)}(j^{\prime},j)=1$ , count the total number of edges between such $j^{\prime}$ and $i$, i.e., $\sum_{j^{\prime}}D^{(t)}(i,j^{\prime})+D^{(t)}(j^{\prime},i)$. Recommend $i$ to $j$ with probability

   $$\frac{\displaystyle\sum_{j^{\prime}\in R\cup B}\big{[}D^{(t)}(i,j^{\prime})+D^{(t)}(j^{\prime},i)\big{]}S^{(t)}(j^{\prime},j)}{\textstyle N-1}$$

   (9)

   where

   $$\displaystyle\sum_{j^{\prime}\in R\cup B}\big{[}D^{(t)}(i,j^{\prime})+D^{(t)}(j^{\prime},i)\big{]}S^{(t)}(j^{\prime},j)$$

   (10)

   is the number of 2 hop connections from i to j, and $N-1$ is used to offset the linear growth of 2 hop connections (between two users) to the number of users in the network.

3. 3)

   If $i$ was recommended to $j$ in step 2, $j$ accepts the recommendation (i.e., the edge $(i,j)$ is formed) according to a Bernoulli random variable with probability of success $C$, where $C$ is the acceptance probability.

Discussion of Algorithm $1$:

(1) Step $1$ considers the fact that an edge ARM recommends may already exist. In that case, no further steps are taken by ARM.

(2) Step $2$ recommends inter-community links with probability according to (9), which favors recommending links between users with more 2 hop connections. To justify how 2 hop connections increase the recommendation probability, suppose $i$ is a red user and $j$ a blue user, then as indicated in (10), $\displaystyle\sum_{j^{\prime}\in R\cup B}D^{(t)}(i,j^{\prime})S^{(t)}(j^{\prime},j)$ specifies the case that $i$ is followed by $j$’s blue friends; $\displaystyle\sum_{j^{\prime}\in R\cup B}D^{(t)}(j^{\prime},i)S^{(t)}(j^{\prime},j)$ specifies the case that $i,j$ share blue friends in common. In both cases, the bigger the value is, the more likely that ARM will recommend $i$ to $j$.

(3) Step $3$ considers the fact that each recommended link turns into an actual edge according to a Bernoulli random variable. In practice, the probability of success depends on the amount of incentive provided by the network administrator in the form of exogenous reward.

(4) We provide the complexity analysis of ARM as follows. Step 2 queries the union of $j$’s follower list and $i$’s follower list/friend list. With hash table based data structure, the query takes $O(1)$ time and the space complexity of the hash table is $O(N)$. The overall time complexity and space complexity are both $O(N^{2})$. There are specialized data structure for real-world large-scale graphs which is out of scope in this work, and we refer interested readers to a survey of graph database models[29].

  Protocol 2. DiSBM Based Network Edge Formation with ARM   Input: $G^{(t)}\textrm{=}\{V,E^{(t)}\}$ where $V\textrm{=}R\cup B$, $t=0,1,2,\cdots$

Output: $p_{R}^{(t)},p_{B}^{(t)}$

Process:

1. 1)

   $p_{R}^{(0)},p_{B}^{(0)}\sim\textrm{Unif}[0,1]$.

2. 2)

   At each odd time instant (i.e., $t=1,3,5,\cdots$), red users take actions according to steps 2.1 and 2.2 below while the blue users adhere to the action they adopted at time $t-1$.

   • 2.1)

     $\forall i,j\in R$, $i$ connects with $j$ with probability⁶⁶6As will be discussed in the proof of Theorem 2 (Appendix A.2), $\mathbb{E}\left\{{U^{(t)}_{\mathrm{ARM}}}_{i}\right\}$ is identical for any $i\in R$ and is a function of $p_{R}^{(t)}$.

     $${p_{R}^{(t)}}=\displaystyle\operatorname*{argmax}_{p_{R}^{(t)}\in(0,1]}\mathbb{E}\left\{{U^{(t)}_{\mathrm{ARM}}}_{i}\right\}$$

     (14)

     where $\mathbb{E}$ is the expectation with respect to the probability distribution induced by the DiSBM model, and ${U^{(t)}_{\mathrm{ARM}}}_{i}$ is the augmented utility function defined in (11).

   • 2.2)

     $\forall i\in R,j\in B$, $i$ connects with $j$ with probability $\frac{1-p_{R}^{(t)}}{N}$.

3. 3)

   At each even time instant (i.e., $t=2,4,6,\cdots$), blue users take actions according to steps 3.1 and 3.2 below while the red users adhere to the action they adopted at time $t-1$.

   • 3.1)

     $\forall i,j\in B$, $i$ connects with $j$ with probability

     $${p_{B}^{(t)}}=\displaystyle\operatorname*{argmax}_{p_{B}^{(t)}\in(0,1]}\mathbb{E}\left\{{U^{(t)}_{\mathrm{ARM}}}_{i}\right\}$$

     (15)

   • 3.2)

     $\forall i\in B,j\in R$, $i$ connects with $j$ with probability $\frac{1-p_{B}^{(t)}}{N}$.

4. 4)

   At each time instant, ARM forms inter-community edges according to Algorithm $1$.

Motivation: Real world social networks have time-variant level of segregation. We justify this phenomenon by the two motivating examples used in Sec. 2.2 as follows. During a politically polarizing event (e.g. election or legislation), Twitter users tend to segregate and reduce their connections with others from a different community. Similarly, on sports forums such as Reddit’s related channels, users’ online communication tend to be more polarized during sports league’s season (e.g. NBA’s playoff or NCAA’s March Madness), while less polarized during off-season. In the literature, [31] models Twitter users’ emotion dynamics as a Markov process. [8] characterizes the pattern of Twitter users’ retweets during the presidential election using a Markov bridge model. [32, 33] utilize Twitter users’ messages as signals to a hidden Markov model to determine when an anticipated event (e.g. social activities, sports, weather) starts.

  Protocol 3. DiSBM Based Network Edge Formation with Markovian Acceptance Probability   Input: $G^{(t)}\textrm{=}\{V,E^{(t)}\}$ where $V\textrm{=}R\cup B$, $t=0,1,2,\cdots$

Output: $p_{R}^{(t)},p_{B}^{(t)}$

Process:

1. 1)

   $p_{R}^{(0)},p_{B}^{(0)}\sim U[0,1]$; $C^{(0)}$ is the initial acceptance probability.

2. 2)

   At each odd time instant (i.e., $t=1,3,5,\cdots$), red users take actions according to steps 2.1 and 2.2 below while the blue users adhere to the action they adopted at time $t-1$.

   • 2.1)

     $\forall i,j\in R$, $i$ connects with $j$ with probability

     $${p_{R}^{(t)}}=\displaystyle\operatorname*{argmax}_{p_{R}^{(t)}\in(0,1]}\mathbb{E}\left\{{U^{(t)}_{\mathrm{ARM}}}_{i}\right\}$$

     (17)

     where $\mathbb{E}$ is the expectation with respect to the probability distribution induced by the DiSBM model, and ${U^{(t)}_{\mathrm{ARM}}}_{i}$ is the augmented utility function defined in (11).

   • 2.2)

     $\forall i\in R,j\in B$, $i$ connects with $j$ with probability $\frac{1-p_{R}^{(t)}}{N}$.

3. 3)

   At each even time instant (i.e., $t=2,4,6,\cdots$), blue users take actions according to steps 3.1 and 3.2 below while the red users adhere to the action they adopted at time $t-1$.

   • 3.1)

     $\forall i,j\in B$, $i$ connects with $j$ with probability

     $${p_{B}^{(t)}}=\displaystyle\operatorname*{argmax}_{p_{B}^{(t)}\in(0,1]}\mathbb{E}\left\{{U^{(t)}_{\mathrm{ARM}}}_{i}\right\}$$

     (18)

   • 3.2)

     $\forall i\in B,j\in R$, $i$ connects with $j$ with probability $\frac{1-p_{B}^{(t)}}{N}$.

4. 4)

   At each time instant, $C^{(t)}$ evolves according to the transition rule (16). ARM forms inter-community edges according to Algorithm $1$ with acceptance probability $C^{(t)}$.