User:Asafkor12/sandbox

This Wikipedia article describes the concept of finding power couples in social networks graphs and the associated algorithms as written in the book "Analyzing narratives in social networks" by prof. Zvi Lotker.

In the 20th chapter of his book "Analyzing Narratives in Social Networks: Taking Turing to the Arts", prof. Zvi Lotker describes one of two methods of rising to power and accumulating social influence. One of them he coins as a power couple, formally defined as "two people who are married to each other, or in a relationship with each other, and both have extremely successful careers, especially in politics or entertainment". in his book prof. Zvi Lotker defines couples through the use of social graphs, specifically a tournament tree in which each node must select another node on the graph. A power couple is a couple who also holds significant centrality in the graph (chapter 20).

Definition

Power couples are defined as two nodes in a tournament social graph that both hold high centrality and choose each other in this tournament graph.

Finding couples

The process of determining couples has two steps. First, each node must select its candidate. Second, we must find a pair in which both nodes select one another. Couples are determined over the graph of selection. the following code finds a couple in a tournament graph:

C <- {}
for {(u,v)} in E do:
    if (v, u) ∈ E and (v,u) ∈/ C then
    C ← C ∪ (v,u) 
    end if
end for
return C
end procedure

Algorithms

General algorithm

The following general algorithm for finding power couples is as follows: first, we ask each of the nodes to rank the other nodes in the graph. We'll summarize the preferences of each node in a decision matrix. This decision matrix is denoted by $\Psi ^{S}\in M_{n,n}[R]$, also named the Stanislavski matrix.

Once the Stanislavski matrix was obtained, the tournament forest can be made. To this, each proposes its preferred matching according to the decision matrix $\Psi ^{S}$ (see chapter 5 algorithm 3 in the book for further inspection).

Finding power couples using a space approach

The decision matrix $\Psi ^{S}$ can be computed by selecting anchors, and using a conflict function to split the rest of the nodes into parties. This method is suitable for small networks, but for larger networks, the number of pairs that need to be considered must be reduced.

All to all decision matrix is defined by:

$\Psi _{i,j}^{S}=|\{u\in V:v_{i}\in (\Xi (Pm|_{\{(u,v_{j})\},G}))(v_{j})^{-1}\}|$

Where $\Psi _{i,j}^{S}$ is the number of times that the node $v_{i}$ is in the partition of the anchor $v_{j}$.

After the decision matrix $\Psi ^{S}$ was obtained, the next step is to construct a tournament forest, using the following algorithm:

Algorithm Construct Tournament Forest From All to All Decision Matrix

1: procedure FindingTournamentForest(V,[Ψ^S_i,j], >, direction)]) ^*

2: E ← {}

3: Ψ' ← [Ψ^S_i,j]

4: for v_i ∈ V do

5: ψ'_i,i = − > ∗. // − > ∗ is the worst alternative option for node v_i

6: u ← Optimal Option ((ψ_i,1, ..., ψ_i,n) , >, direction) ^**

7: E ← E ∪ {(v_i, u)}

8: end for

9: return T (V, E) ^***

10: end procedure

* Where V is the set of all nodes, [ψSi,j] is a decision matrix, i, j ∈ {1, 2, ..., n}, > is the total order, and direction is the set of the optimal direction.
** See algorithm 3 in: Lotker, Zvi (28 August 2021). Analyzing Narratives in Social Networks: Taking Turing to the Arts. Springer Cham. p. 83. ISBN 978-3-030-68299-6.

(chapter 5.4 of the book- Utility Anchors)

*** Return the list of couples.

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

After calculating the tournament forest with the algorithm above, the power-couple finding algorithm could be used on the result.

Finding power couples using Dynamics

Similarly to the space-approach algorithm, this algorithm relies on individuals in the network to choose the best candidates themselves. The process is represented using a decision forest.

This method is more specific, utilizing real functions' correlations, instead of the general method of using conflict functions (in the space approach).

Idea

The idea here is to use a real function $F_{i}$ for all of the characters $v_{i}\in V$ in the evolving $\gamma$ graph. Then, compute the correlation matrix $\rho$ between all of the functions:

$\rho =[\rho (F_{i},F_{j})]$

Where $\rho$ is the correlation. Now, in order to compute $\Psi ^{s}$ using $\gamma$:

$\Psi ^{s}=[(\psi _{i,j})^{cor}]=[\rho (d_{v_{i}},d_{v_{j}})]$

Where $d_{v_{i}}$ is the degree function for every character $v_{i}\in V$:

$d_{v_{i}}:T\rightarrow G$

And finally, after using the FindingTournamentForest algorithm on $\Psi ^{s}$, the finding couples algorithm could be used to find couples.

Examples from the book

Example of the Space Approach to compute the decision matrix

Zvi shows an example of a simplified script- where characters A, B, and C have a conversation.

$S_{c}=((A,r_{1}),(B,r_{2}),(A,r_{3}),(B,r_{4}),(A,r_{5})(C,r_{6}),(B,r_{7}),(C,r_{8})).$

The 3 possible anchors are as such:

${\mathcal {A}}_{1}=({1},{2}),{\mathcal {A}}_{2}=({1},{3}),{\mathcal {A}}_{3}=({1},{3}).$

Now, using the voting algorithm (as discussed in chapter 7) gives us these decision matrices:

$\Psi _{1,2}^{Voting}={\begin{bmatrix}1&0\\0&1\\{\frac {2}{3}}&{\frac {1}{3}}\end{bmatrix}},\Psi _{1,3}^{Voting}={\begin{bmatrix}1&0\\{\frac {3}{4}}&{\frac {1}{4}}\\0&1\end{bmatrix}},\Psi _{2,3}^{Voting}={\begin{bmatrix}{\frac {3}{5}}&{\frac {2}{5}}\\1&0\\0&1\end{bmatrix}}$

And the Voronoi decision matrices (explained further in chapter 6) are as follows:

$\Psi _{1,2}^{Voronoi}={\begin{bmatrix}1&{\frac {1}{3}}\\{\frac {1}{3}}&0\\{\frac {1}{2}}&{\frac {5}{6}}\end{bmatrix}},\Psi _{1,3}^{Voronoi}={\begin{bmatrix}0&{\frac {1}{2}}\\{\frac {1}{3}}&{\frac {5}{6}}\\{\frac {1}{2}}&0\end{bmatrix}},\Psi _{2,3}^{Voronoi}={\begin{bmatrix}{\frac {1}{3}}&{\frac {1}{2}}\\0&{\frac {5}{6}}\\{\frac {5}{6}}&0\end{bmatrix}}$

The next step is computing the partition for each conflict, which gives the following results:

${\begin{array}{lcl}{\mathcal {A}}\qquad \qquad \qquad \Xi (Pm|_{\{(u,v_{j})\},G}))(v_{j})^{-1}\\\{1,2\}\qquad \qquad \qquad \{\{1,3\},\{2\}\}\\\{1,3\}\qquad \qquad \qquad \{\{1,2\},\{3\}\}\\\{2,3\}\qquad \qquad \qquad \{\{1,2\},\{3\}\}\\\end{array}}$

By counting the number of appearances of each node in the respective anchors’ partitions, we can form the decision matrix:

$\Psi ^{S}={\begin{bmatrix}2&1&0\\1&2&0\\1&0&2\end{bmatrix}}$