Group Conformity in Social Networks

Abstract

Diffusion in social networks is a result of agents’ natural desires to conform to the behavioral patterns of their peers. In this article we show that the recently proposed “propositional opinion diffusion model” could be used to model an agent’s conformity to different social groups that the same agent might belong to, rather than conformity to the society as whole. The main technical contribution of this article is a sound and complete logical system describing the properties of the influence relation in this model. The logical system is an extension of Armstrong’s axioms from database theory by one new axiom that captures the topological structure of the network.

Monotonic Boolean Functions

In this appendix we prove the property of monotonic Boolean functions that we referred to in the introduction.

Lemma 20

Any monotonic Boolean formula can be written as a disjunction of several disjuncts where each disjunct is a conjunction of several propositional variables.

Proof

Consider any monotonic Boolean formula $\varphi (x_1,\ldots ,x_n)$. If $b_1,\ldots ,b_n$ are Boolean values, then by $\varphi \left( \begin{array}{ccccc} 1 &{} 2 &{} 3 &{} \cdots &{} n \\ b_1 &{} b_2 &{} b_3 &{} \cdots &{} b_n \end{array}\right)$ we denote the Boolean value of formula $\varphi$ on Boolean arguments $b_1,\ldots ,b_n$. Consider Boolean expression

$$\begin{aligned} \psi = \bigvee \left\{ x_{i_1}\wedge x_{i_2}\wedge \dots \wedge x_{i_k}\;\big |\; \varphi \left( \begin{array}{ccccccccccc} 1 &{} \dots &{} i_1-1 &{} i_1 &{} i_1+1 &{} \dots &{} i_k-1 &{} i_k &{} i_k+1 &{} \dots &{} n\\ 0 &{} \dots &{} 0 &{} 1 &{} 0 &{} \cdots &{} 0 &{} 1 &{} 0 &{} \dots &{} 0 \end{array}\right) = 1 \right\} . \end{aligned}$$

(2)

Next we show that formulae $\varphi$ and $\psi$ are equivalent. Consider any Boolean values $b_1,\ldots ,b_n$. We will show that $\varphi \left( \begin{array}{ccccc} 1 &{} 2 &{} 3 &{} \cdots &{} n \\ b_1 &{} b_2 &{} b_3 &{} \cdots &{} b_n \end{array}\right) = 1$ if and only if $\psi \left( \begin{array}{ccccc} 1 &{} 2 &{} 3 &{} \cdots &{} n \\ b_1 &{} b_2 &{} b_3 &{} \cdots &{} b_n \end{array}\right) =1$

$(\Rightarrow )$ Let $i_1,\ldots ,i_n$ be all indices i such that $b_i=1$. Then,

$$\begin{aligned} \varphi \left( \begin{array}{ccccccccccc} 1 &{} \dots &{} i_1-1 &{} i_1 &{} i_1+1 &{} \dots &{} i_k-1 &{} i_k &{} i_k+1 &{} \dots &{} n\\ 0 &{} \dots &{} 0 &{} 1 &{} 0 &{} \cdots &{} 0 &{} 1 &{} 0 &{} \dots &{} 0 \end{array}\right) = 1. \end{aligned}$$

Hence, conjunction $x_{i_1}\wedge x_{i_2}\wedge \dots \wedge x_{i_k}$ is one of disjuncts in formula $\psi$. Note that

$$\begin{aligned} (x_{i_1}\wedge x_{i_2}\wedge \dots \wedge x_{i_k}) \left( \begin{array}{ccccccccccc} 1 &{} \dots &{} i_1-1 &{} i_1 &{} i_1+1 &{} \dots &{} i_k-1 &{} i_k &{} i_k+1 &{} \dots &{} n\\ 0 &{} \dots &{} 0 &{} 1 &{} 0 &{} \cdots &{} 0 &{} 1 &{} 0 &{} \dots &{} 0 \end{array}\right) = 1\wedge \dots \wedge 1=1. \end{aligned}$$

Therefore,

$$\begin{aligned} \psi \left( \begin{array}{ccccccccccc} 1 &{} \dots &{} i_1-1 &{} i_1 &{} i_1+1 &{} \dots &{} i_k-1 &{} i_k &{} i_k+1 &{} \dots &{} n\\ 0 &{} \dots &{} 0 &{} 1 &{} 0 &{} \cdots &{} 0 &{} 1 &{} 0 &{} \dots &{} 0 \end{array}\right) = 1. \end{aligned}$$

because conjunction $x_{i_1}\wedge x_{i_2}\wedge \dots \wedge x_{i_k}$ is one of disjuncts in formula $\psi$.

$(\Leftarrow )$ In order for a disjunction to have value 1 at least one disjunct must have value 1. Thus, assumption $\psi \left( \begin{array}{ccccc} 1 &{} 2 &{} 3 &{} \cdots &{} n \\ b_1 &{} b_2 &{} b_3 &{} \cdots &{} b_n \end{array}\right) =1$ and Eq. (2) imply that there are indices $i_1,\ldots ,i_k$ such that

$$\begin{aligned} (x_{i_1}\wedge x_{i_2}\wedge \dots \wedge x_{i_k})\left( \begin{array}{ccccc} 1 &{} 2 &{} 3 &{} \cdots &{} n \\ b_1 &{} b_2 &{} b_3 &{} \cdots &{} b_n \end{array}\right) =1 \end{aligned}$$

(3)

and

$$\begin{aligned} \varphi \left( \begin{array}{ccccccccccc} 1 &{} \dots &{} i_1-1 &{} i_1 &{} i_1+1 &{} \dots &{} i_k-1 &{} i_k &{} i_k+1 &{} \dots &{} n\\ 0 &{} \dots &{} 0 &{} 1 &{} 0 &{} \cdots &{} 0 &{} 1 &{} 0 &{} \dots &{} 0 \end{array}\right) = 1. \end{aligned}$$

(4)

Note that $(x_{i_1}\wedge x_{i_2}\wedge \dots \wedge x_{i_k})\left( \begin{array}{ccccc} 1 &{} 2 &{} 3 &{} \cdots &{} n \\ b_1 &{} b_2 &{} b_3 &{} \cdots &{} b_n \end{array}\right) = b_{i_1}\wedge \dots \wedge b_{i_k}$. Thus, equality (3) implies that $b_{i_1}=\dots =b_{i_k}=1$. Hence, it follows from Eq. (4) that

$$\begin{aligned} \varphi \left( \begin{array}{ccccccccccc} 1 &{} \dots &{} i_1-1 &{} i_1 &{} i_1+1 &{} \dots &{} i_k-1 &{} i_k &{} i_k+1 &{} \dots &{} n\\ 0 &{} \dots &{} 0 &{} b_i &{} 0 &{} \cdots &{} 0 &{} b_k &{} 0 &{} \dots &{} 0 \end{array}\right) = 1. \end{aligned}$$

Therefore,

$$\begin{aligned} \varphi \left( \begin{array}{ccccccccccc} 1 &{} \dots &{} i_1-1 &{} i_1 &{} i_1+1 &{} \dots &{} i_k-1 &{} i_k &{} i_k+1 &{} \dots &{} n\\ b_1 &{} \dots &{} b_{i-1} &{} b_i &{} b_{i+1} &{} \cdots &{} b_{k-1} &{} b_k &{} b_{k+1} &{} \dots &{} b_n \end{array}\right) = 1. \end{aligned}$$

due to the assumption that formula $\varphi$ is monotonic. $\square$