class: title-slide middle center inverse # Projecting Signed Two-Mode Networks ### David Schoch The Mitchell Centre for Social Network Analysis University of Manchester .date[Sunbelt 2020] <img src="https://imgs.xkcd.com/comics/complex_numbers.png" height="300px"> .date[15/07/2020] --- layout: true <div class="logo-header"></div> --- # research on signed networks .center[ <img src="figures/balance_triples.png" height="200px"> ] .huge[.center[**strong focus on balance theory**]] -- **empirically** testing theory on Social Media, Wikipedia, international relations, etc. **methodologically** measures of "balancedness" -- **"non-balance" research** centrality in signed networks .cite[[e.g. Bonacich, 2004]] general applicability of network analytic tools .cite[[Everett & Borgatti, 2014]] blockmodeling .cite[[Doreian and collaborators]] --- # projecting two-mode networks .center[ <img src="figures/proj_flow.png" height="250px"> ] **projecting** onto relevant mode ⇒ weighted network **filtering** and **dichotomizing** ⇒ unweighted network ("backbone extraction" .cite[[[Neal, 2014]](http://www.sciencedirect.com/science/article/pii/S0378873314000343)]) -- <br> **aim** method to project signed two-mode networks onto its modes make any dichotomization method available for signed two-mode networks --- # "naive" approach <img src="figures/small_signed2mode.png" height="250px" style="margin-right:20px;margin-bottom:20px;float: left;" > -- $$ A=\begin{pmatrix} \begin{array}{rrr} 1 & 1 & -1 \\\ 1 & -1 & 0 \\\ \end{array}\end{pmatrix} $$ $$ AA^T= \begin{pmatrix} \begin{array}{rr} 3 & 0 \\\ 0 & 2\\\ \end{array} \end{pmatrix} \text{ and } A^TA= \begin{pmatrix} \begin{array}{rr} 2 & 0 & -1\\\ 0 & 2 & -1\\\ -1 & -1 & 1 \\\ \end{array} \end{pmatrix} $$ --- # multiplication approach <img src="figures/small_signed2mode.png" height="250px" style="margin-right:20px;margin-bottom:20px;float: left;" > $$ A=\begin{pmatrix} \begin{array}{rrr} 1 & 1 & -1 \\\ 1 & -1 & 0 \\\ \end{array}\end{pmatrix} $$ -- $$ A^+=\begin{pmatrix}1 & 1 & 0 \\\ 1 & 0 & 0 \\\ \end{pmatrix} \quad A^-=\begin{pmatrix}0 & 0 & 1 \\\ 0 & 1 & 0 \\\ \end{pmatrix} $$ -- $$ P=A^+{A^+}^T + A^-{A^-}^T \text{ and } N=A^+{A^-}^T $$ -- $$ P=\begin{pmatrix} \begin{array}{rr} 3 & 1 \\\ 1 & 2 \\\ \end{array} \end{pmatrix} \text{ and } N=\begin{pmatrix} \begin{array}{rr} 0 & 1 \\\ 1 & 0 \\\ \end{array} \end{pmatrix} $$ -- <br> .center[ .huge[ ** How to combine P and N ?** ] ] --- # ambivalent ties .box[ **symbolic (psycho) logic** .citew[[Abelson & Rosenberg, 1958]] "Of all the conceivable relations between cognitive elements, we choose to consider only four: .center[*positive (p), negative (n), null (0), and .gold-highlight[ambivalent (a)]*] Ambivalent relations are defined as conjunctions of positive and negative relations; they are psychologically secondary or "derived", [...] " ] -- **Working with `\(\boldsymbol{p}\)`, `\(\boldsymbol{n}\)`, `\(\boldsymbol{0}\)`, and `\(\boldsymbol{a}\)`** <table style="float: left"> <tr style="border-bottom: 1px solid black;"> <td>⊕</td> <td style="font-weight: bold;">p</td> <td style="font-weight: bold;">n</td> <td style="font-weight: bold;">0</td> <td style="font-weight: bold;">a</td> </tr> <tr> <td style="font-weight: bold;">p</td> <td>p</td> <td>a</td> <td>p</td> <td>a</td> </tr> <tr> <td style="font-weight: bold;">n</td> <td>a</td> <td>n</td> <td>n</td> <td>a</td> </tr> <tr> <td style="font-weight: bold;">0</td> <td>p</td> <td>n</td> <td>0</td> <td>a</td> </tr> <tr> <td style="font-weight: bold;">a</td> <td>a</td> <td>a</td> <td>a</td> <td>a</td> </tr> </table> <table style="float: left;margin-left:75px; margin-right:75px"> <tr> <td>⊙</td> <td style="font-weight: bold;">p</td> <td style="font-weight: bold;">n</td> <td style="font-weight: bold;">0</td> <td style="font-weight: bold;">a</td> </tr> <tr> <td style="font-weight: bold;">p</td> <td>p</td> <td>n</td> <td>0</td> <td>a</td> </tr> <tr> <td style="font-weight: bold;">n</td> <td>n</td> <td>p</td> <td>0</td> <td>a</td> </tr> <tr> <td style="font-weight: bold;">0</td> <td>0</td> <td>0</td> <td>0</td> <td>0</td> </tr> <tr> <td style="font-weight: bold;">a</td> <td>a</td> <td>a</td> <td>0</td> <td>a</td> </tr> </table> -- <div style="margin-top:-50px;"><img src="figures/ambi_paths.png" height="250px"></div> --- # multiplication approach <img src="figures/small_signed2mode.png" height="250px" style="margin-right:20px;margin-bottom:20px;float: left;" > $$ A=\begin{pmatrix} \begin{array}{rrr} 1 & 1 & -1 \\\ 1 & -1 & 0 \\\ \end{array}\end{pmatrix} $$ $$ A^+=\begin{pmatrix}1 & 1 & 0 \\\ 1 & 0 & 0 \\\ \end{pmatrix} \quad A^-=\begin{pmatrix}0 & 0 & 1 \\\ 0 & 1 & 0 \\\ \end{pmatrix} $$ $$ P=A^+{A^+}^T + A^-{A^-}^T \text{ and } N=A^+{A^-}^T $$ $$ P=\begin{pmatrix} \begin{array}{rr} 3 & 1 \\\ 1 & 2 \\\ \end{array} \end{pmatrix} \text{ and } N=\begin{pmatrix} \begin{array}{rr} 0 & 1 \\\ 1 & 0 \\\ \end{array} \end{pmatrix} $$ <div style="clear:left;"></div> -- **dichotomize** `\(A^{(P)} = \begin{pmatrix}\begin{array}{rr}0 & 1 \\\ 1 & 0 \end{array}\end{pmatrix}\)` and `\(A^{(N)} = \begin{pmatrix}\begin{array}{rr}0 & 1 \\\ 1 & 0 \end{array}\end{pmatrix}\)` -- **combine** `\(A^{(P)} \oplus A^{(N)}=\begin{pmatrix}\begin{array}{rr}0 & p \\\ p & 0 \end{array}\end{pmatrix} \oplus \begin{pmatrix}\begin{array}{rr}0 & n \\\ n & 0 \end{array}\end{pmatrix}=\begin{pmatrix}\begin{array}{rr}0 & a \\\ a & 0 \end{array}\end{pmatrix}\)` --- # vertex duplication approach **signed → unsigned two-mode network** (vertex duplication) .center[<img src="figures/signed2mode_duplicate.png" height="225px">] -- **unsigned projection → signed projection** (vertex contraction) .center[<img src="figures/signed2mode_contract.png" height="225px">] --- # matrices for networks with ambivalent ties <br> <img src="figures/real_line.png" height="100px" style="margin-top:-20px;margin-bottom:20px;float: right;"> **which value should be assigned to ambivalent ties?** <div style="clear:right;"></div> -- .box[**extending the two-value system for signed networks** .cite[[Cartwright & Harary, 1970]] a tie `\(e\)` is encoded by `\(m(e)=(\rho,\eta)\)`, where `\(\rho\)` is a measure of positivity and `\(\eta\)` is a measure of negativity (both in `\([0,1]\)`) strict positive tie: `\(m(e)=(1,0)\)`     strict negative tie: `\(m(e)=(0,1)\)` null tie: `\(m(e)=(0,0)\)`          ambivalent tie: `\(m(e)=(0.5,0.5)\)` ] -- **expressing tie values as complex numbers** $$ m(e) =(\rho,\eta) \sim \rho+\eta i $$ --- # adjacency matrix .box[**Definition** The *complex adjacency matrix* `\(\mathcal{A}\in \mathbb{C}^{n,n}\)` of an undirected signed network `\(\Gamma=(G,\sigma)\)` with `\(\sigma: E \to \{p,n,a\}\)` is a Hermitian matrix defined as $$ \mathcal{A}_{jk} = \begin{cases} 1+ 0i & \sigma(\{j,k\})=p \\\ 0+ 1i & \sigma(\{j,k\})=n \\\ 0.5+ 0.5i & \sigma(\{j,k\})=a \\\ 0+0i & \text{else}. \\\ \end{cases} $$ if `\(j\leq k\)` and `$$\mathcal{A}_{kj} = \mathcal{A}_{jk}^*$$` for `\(j>k\)`. ] --- # Laplacian matrix .box[**Definition** The *complex Laplacian matrix* `\(\mathcal{L}\in \mathbb{C}^{n,n}\)` is defined as `\(\mathcal{L} = \mathcal{D}- \mathcal{A}\)`, where `\(\mathcal{D}\)` is a diagonal matrix with entries `$$\mathcal{D}_{jj}=\sum_{k=1}^n \lvert \mathcal{A}_{jk}\rvert$$` The *normalized complex Laplacian matrix* is given by $$ \mathcal{L}^{norm} = \mathcal{D}^{-\frac{1}{2}}\mathcal{L}\mathcal{D}^{-\frac{1}{2}}= I-\mathcal{D}^{-\frac{1}{2}}\mathcal{A}\mathcal{D}^{-\frac{1}{2}}, $$ where `\(I\)` is the identity matrix. ] <br> -- .box[**Theorem** The complex Laplacian matrix is positive semi-definite ] --- # structural balance with ambivalence .box[**Theorem** The following statements are equivalent for a symmetric signed network `\(\Gamma=(G,\sigma)\)`, where `\(\sigma:E\to\{+1,-1\}\)`. (i) The value of every cycle is `\(+1\)`. (ii) For every pair of vertices, the values of all paths joining them are the same. (iii) The set `\(V\)` can be partitioned into two subsets (one of which may be empty) such that the value of each tie between two vertices of the same set is `\(+1\)` and the value of each tie between two vertices of different subsets is `\(-1\)`. ] -- **extending partiton balance** .center[ <img src="figures/strong_partition.png" height="250px" style="margin-right:50px;margin-top:-30px"> <img src="figures/weak_partition.png" height="250px" style="margin-right:50px;margin-top:-30px"> <img src="figures/unbalanced_partition.png" height="250px" style="margin-top:-30px"> ] --- # partition balance and Laplacian matrix .box[**Theorem** (balance without ambivalence) .cite[[Kunegis, 2010]] The signed Laplacian matrix of a graph is positive-definite if and only if the graph is unbalanced. ] <br> -- .box[**Theorem** (balance with ambivalence) The complex Laplacian matrix of a graph is positive-definite if and only if the graph is partition unbalanced. ] -- **Proof** I have discovered a truly remarkable proof of this theorem which this slide is too small to contain. --- # summary <br><br> **signed projections** *multiplication approach*: produces two matrices that need to be combined (or analysed separately) *vertex duplication approach*: allows the application of any "unsigned tool" -- **ambivalence** hard to measure(?) arise naturaly in projections -- **complex matrices** allow the integration of ambivalent ties desirable properties (also for regular signed networks?) --- # get in touch Schoch, David. "Projecting signed two-mode networks." *The Journal of Mathematical Sociology* (2020): 1-14. https://doi.org/10.1080/0022250X.2019.1711376 <br> <img src="figures/signnet.png" height="125px" style="float:left; margin-right:50px"> **R package** (signnet) `install.packages("signnet")` http://signnet.schochastics.net/ <br> <br> <br> .center[ .huge[ <svg style="height:0.8em;top:.04em;position:relative;fill:#660099;" viewBox="0 0 576 512"><path d="M280.37 148.26L96 300.11V464a16 16 0 0 0 16 16l112.06-.29a16 16 0 0 0 15.92-16V368a16 16 0 0 1 16-16h64a16 16 0 0 1 16 16v95.64a16 16 0 0 0 16 16.05L464 480a16 16 0 0 0 16-16V300L295.67 148.26a12.19 12.19 0 0 0-15.3 0zM571.6 251.47L488 182.56V44.05a12 12 0 0 0-12-12h-56a12 12 0 0 0-12 12v72.61L318.47 43a48 48 0 0 0-61 0L4.34 251.47a12 12 0 0 0-1.6 16.9l25.5 31A12 12 0 0 0 45.15 301l235.22-193.74a12.19 12.19 0 0 1 15.3 0L530.9 301a12 12 0 0 0 16.9-1.6l25.5-31a12 12 0 0 0-1.7-16.93z"/></svg> http://schochastics.net/ <svg style="height:0.8em;top:.04em;position:relative;fill:#660099;" viewBox="0 0 512 512"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> david.schoch@manchester.ac.uk <svg style="height:0.8em;top:.04em;position:relative;fill:#660099;" viewBox="0 0 512 512"><path d="M459.37 151.716c.325 4.548.325 9.097.325 13.645 0 138.72-105.583 298.558-298.558 298.558-59.452 0-114.68-17.219-161.137-47.106 8.447.974 16.568 1.299 25.34 1.299 49.055 0 94.213-16.568 130.274-44.832-46.132-.975-84.792-31.188-98.112-72.772 6.498.974 12.995 1.624 19.818 1.624 9.421 0 18.843-1.3 27.614-3.573-48.081-9.747-84.143-51.98-84.143-102.985v-1.299c13.969 7.797 30.214 12.67 47.431 13.319-28.264-18.843-46.781-51.005-46.781-87.391 0-19.492 5.197-37.36 14.294-52.954 51.655 63.675 129.3 105.258 216.365 109.807-1.624-7.797-2.599-15.918-2.599-24.04 0-57.828 46.782-104.934 104.934-104.934 30.213 0 57.502 12.67 76.67 33.137 23.715-4.548 46.456-13.32 66.599-25.34-7.798 24.366-24.366 44.833-46.132 57.827 21.117-2.273 41.584-8.122 60.426-16.243-14.292 20.791-32.161 39.308-52.628 54.253z"/></svg> @schochastics ] ]