Computational narratives in social networks​
​by Zvi Lotker and Yehuda Ben-Shimol

Background

The book “Analyzing Narratives in Social Networks” authored by Zvi lotker is divided into three main parts. This notebook provides some code used in the first part of the book.
Part I of the book analyzes narratives in static social networks. Questions are asked such as how to use algorithms to locate conflicts in drama scripts and social networks; how to partition a network into communities based on narrative; what constitutes a static point of view of an individual in a social network. The book presents new methods to analyse scripts of plays and movies.
This notebook was created by Zvi Lotker and Yehuda Ben-Shimol.
◼
  • Zvi Lotker is with the department of Computer Engineering, Bar Ilan University, ISRAEL.
    • ◼
  • Yehuda Ben-Shimol is with the Electrical and Computer Engineering School, Ben-Gurion University, ISRAEL.

    • What is a script

    Definition
    

    Example
    

    Frequency Graph
    

    From Script to AB Graph
    

    Common community detection vs. the algorithms proposed in the book

    For explanations on common community detection algorithms see
    ​https://en.wikipedia.org/wiki/Community_structure​
    ​http://digitalinterface.blogspot.com/2013/05/community-detection-in-graphs.html
    The various community detection schemes (which are also implemented in Mathematica) are not suitable to find the narrative embedded in the script. There are two main drawbacks
    1
    .
    There is no way to hint the community detection algorithms of the intentions of the human user.
    2
    .
    The existing community detection cannot “explain” their findings of the communities “found” in the graph.
    The analysis scheme proposed in the book takes care of these two issues by introducing the terms “anchors” and “decision matrix”, as will be discussed later. Both allow to “ask” the algorithm specific questions and provide hints to the algorithms. This way the human user can interact in a “two-way conversation” (i.e., dialog).

    “Traditional” graph communities algorithms
    

    Links

    In[]:=
    FindGraphCommunities/@{hamletABD,hamletAB}
    Out[]=
    {{{All,BERNARDO,Captain,First Ambassador,First Player,First Sailor,FRANCISCO,Ghost,GUILDENSTERN,HAMLET,HORATIO,Lord,LUCIANUS,MARCELLUS,OSRIC,PRINCE FORTINBRAS,ROSENCRANTZ,Servant},{CORNELIUS,Danes,First Priest,Gentleman,KING CLAUDIUS,LAERTES,LORD POLONIUS,Messenger,OPHELIA,Prologue,QUEEN GERTRUDE,REYNALDO,VOLTIMAND},{First Clown,Second Clown},{Player King,Player Queen}},{{All,BERNARDO,Captain,First Ambassador,First Player,First Sailor,FRANCISCO,Ghost,GUILDENSTERN,HAMLET,HORATIO,Lord,LUCIANUS,MARCELLUS,OSRIC,PRINCE FORTINBRAS,ROSENCRANTZ,Servant},{CORNELIUS,Danes,First Priest,Gentleman,KING CLAUDIUS,LAERTES,LORD POLONIUS,Messenger,OPHELIA,Prologue,QUEEN GERTRUDE,REYNALDO,VOLTIMAND},{First Clown,Second Clown},{Player King,Player Queen}}}
    In[]:=
    method={"Modularity","Centrality","CliquePercolation","Hierarchical","Spectral","VertexMoving"};​​Manipulate[Show[​​HighlightGraph[​​hamletABD,gc=FindGraphCommunities[hamletABD,Methodmet];lgc=Framed[Style[ToString[Length[gc]]<>" Communities",Bold,Large,Red,FontFamily"Times"]];gc]​​,ImageSize600,PlotLabel->lgc],​​{met,method},SaveDefinitionsTrue]
    Out[]=
    ​
    met
    Modularity
    Most of the common algorithms identify too many communities. Anyway, detecting communities needs to correspond to the narative embedded in the script.

    The proposed algorithms from the book

    The book uses two basic geometric narratives data structures: metric space and frequency graph. In the following subsections we define the metric space and show how to convert a frequency graph into a a metric space.

    Metric space

    Definition
    A metric space is a function which defines the distance between any two points or members of a set.
    A metric space is an ordered pair
    (V;dis)
    where
    V
    is a set, and
    dis
    is a metric on
    V
    .
    The distance function dis is defined as follows
    ​
    dis:V×V
    ​
    1. Identity of indiscernible:
    dis(x,y)=0
    if and only if
    x=y
    ​
    2. Symmetry:
    dis(x,y)=dis(y,x)
    ​
    3. Triangle Inequality:
    dis(x,y)+dis(y,z)>=dis(x,z)
    The frequency graph
    AB
    needs to transformed into a metric space. This is achieved in two steps:
    1
    .
    Convert the frequency to distance
    f
    i,j
    ->
    x
    i,j
    =1
    f
    i,j
    . The reflexive frequency becomes zero, i.e.,
    x
    i,i
    =0
    . Any vertices that are not connected in
    AB
    (i.e.,
    f
    i,j
    =0
    ) are associated with the distance
    x
    i,j
    =∞
    . The problem is that the matrix
    [
    x
    i,j
    ]
    does not always satisfies the triangle inequality.
    2
    .
    Using the Floyd-Warshall algorithm transforms the matrix
    [
    x
    i,j
    ]
    into a metric space, i.e.,
    [
    x
    i,j
    ]->[
    m
    i,j
    ]
    
    Compute the matrix of distances (metric space) from the Hamlet frequency graph
    In[]:=
    hamletMetricSpace=FromFrequencyGraph2Metricspace[hamletAB];
    checking the triangle inequality
    In[]:=
    With[{n=Length[hamletMetricSpace]},And@@Flatten[Table[hamletMetricSpace[[i,j]]+hamletMetricSpace[[j,k]]>=hamletMetricSpace[[i,k]],{i,n},{j,n},{k,n}]]]

    Decision matrix

    Definitions and explanations

    The decision matrix is a tool that allows us to “ask” vertices “what are their opinions” on various alternatives. One of the main drawbacks of community detection algorithms is the lack of the possibility to “explain” how and why they generated their results. The decision matrix is a mean that allows to overcome this drawback.
    DefinitionThe matrix ψ is called a decision matrix when the rows are the decision vectors which "grade" or "rate" the various options available to the node according to the total order
    
    .

    Functionality

    In[]:=
    DisanceFromSetToPoint[distMat_,S1_,p_]:=​​(* distMat - a distances matrix of the metricspace​​ S1 - a subset of indexes , ​​ p - an index of a point in the metricspace​​The output is the distans of p to S1​​ *)​​Min[distMat[[p]][[S1]]]
    In[]:=
    FromMetricspaceS2DecisionMatrix[distMat_,V1_]:=​​(* ​​ Input:​​ distMat - a distances matrix of the metricspace​​ A - a set of disjoint k subsets V1​​Output:​​ The Decision Matrix ψ​​*)​​Table[DisanceFromSetToPoint[distMat,V1[[j]],i],{i,Length[distMat]},{j,Length[V1]}]​​

    Example

    We generate the decision matrix for two characters (i.e., anchors) defining two distinct groups of characters in the play: King Claudius and Lord Polonius. The distance (in the metric space) of each character to the two anchors is computed. Since the the metric space does not relate to names, we associate the name of each character in the play to its corresponding position in the vertices list to ease the human use.
    Out[]=
    All1,BERNARDO2,Captain3,CORNELIUS4,Danes5,First Ambassador6,First Clown7,First Player8,First Priest9,First Sailor10,FRANCISCO11,Gentleman12,Ghost13,GUILDENSTERN14,HAMLET15,HORATIO16,KING CLAUDIUS17,LAERTES18,Lord19,LORD POLONIUS20,LUCIANUS21,MARCELLUS22,Messenger23,OPHELIA24,OSRIC25,Player King26,Player Queen27,PRINCE FORTINBRAS28,Prologue29,QUEEN GERTRUDE30,REYNALDO31,ROSENCRANTZ32,Second Clown33,Servant34,VOLTIMAND35
    In[]:=
    poloniusVsClaudiusDecisionMatrix=FromMetricspaceS2DecisionMatrix[hamletMetricSpace,{{namesToIndex["KING CLAUDIUS"]},{namesToIndex["LORD POLONIUS"]}}]

    Adapting the community detection algorithms to conflict functions (universal community detection)

    Background

    We will show two universal ways of doing that mapping: Voronoi diagram that work metric space and voting, which uses Markov chains.

    Voronoi (Chapter 6 in the book)

    Voronoi - background

    Voronoi - description

    The presented Voronoi partition algorithm is universal in the sense that it can generate any required partition, based on the selected anchors. In the extreme case that all vertices are set as distinct anchors, the resulted partition is the distinct vertices. By refining the selection of the anchors, this algorithm

    Voronoi examples from Hamlet’s script

    Example1 - KING CLAUDIUS (party 1) vs. LORD POLONIUS (party 2)
    Example 2 - 3 parties: KING CLAUDIUS (party 1) vs. LORD POLONIUS (party 2) vs. QUEEN GERTRUDE + OPHELIA (party 3)
    Example 3 - “GUILDENSTERN (party 1) vs. ROSENCRANTZ (party 2)
    Example 4 - affirmative action
    We would like to make the parties to have (approximately) the same power. This is done using affirmative action: we “normalize” the decision matrix such that each party has the (approximately) the same number of members. The median statistical function can be used for that.

    Voting (Chapter 7 in the book)

    Markov Process

    Voting: Algorithmic Description

    There are four steps in the voting algorithm
    The presented algorithms are written with the sake of clarity in mind. Large problems are preferably solved using matrix multiplications which are much more computationally efficient. This also holds if there are many parties.

    Voting examples from the Hamlet script

    Example1 - KING CLAUDIUS (party 1) vs. LORD POLONIUS (party 2)
    Example 2 - 3 parties: KING CLAUDIUS (party 1) vs. LORD POLONIUS (party 2) vs. QUEEN GERTRUDE + OPHELIA (party 3)
    Example 3 - “GUILDENSTERN (party 1) vs. ROSENCRANTZ (party 2)
    Example 4 - affirmative action
    We would like to make the parties to have (approximately) the same power. This is done using affirmative action: we “normalize” the decision matrix such that each party has the (approximately) the same number of members. The median statistical function can be used for that.

    Conclusions

    The book presents new methods to analyse scripts of plays and movies. Temporal analysis also shows the Lord Polonius is the real traitor since he also betrayed the faith of his daughter Ophelia. Polonuis, driven by his lust of power, cancels Ophelia’s engagements to Claudius, and after the murder sends Ophelia to the monastery, thus preventing her from being both a queen and a mother.