Comparing networks is always a complicated matter, whose efective implementation strongly depends on the amount of shared information between them, in particular whether nodes, edges, weights etc. are identical, or not. In the case of character networks and adaptations (from book to movie, from movie to theater, and so on), the formal challenge proves stimulating: some characters will be mapped from one work to the other, some will have no correspondence, and their weights, measuring their relative occurence, are bound to difer. This formal contribution, rooted in Multivariate Data Analysis, proposes a presumably novel similarity index, the generalized weighted RV coeficient, taking into account both the diference in character weights (nodes) and in character interactions (edges). This approach first requires to transform the character networks into weighted squared Euclidean configurations. We then compare a novel of C.S. Lewis, part of the series The Chronicles of Narnia, and the script of its film adaptation to illustrate the proposal and the results.
Networks of fictional characters often exist in two or more versions. For instance (section 4), network is built from a novel, and network from a movie adaptation. Besides the main characters common to both versions, there are characters proper to a single version only. Also, the importance of common characters (as measured, e.g., by their relative occurrence), is bound to vary between the two versions, as is the strength of their mutual relations (as e.g. measured by their relative co-occurrence). Hence, the networks and difer both along character weights (nodes) and interaction weights (edges).
Our contribution proposes the definition of a single index measuring the overall similarity between and . This index, noted RV, constitutes an innovative generalization, involving two distinct sets of object weights, of the weighted RV-coeficient [1], which is itself a generalization of the original, unweighted RV-coeficient [ 2] (where R did refer to "correlation" and V to "vector"). In particular, RV ∈ [0, 1], with RV = 1 if and are identical (i.e., same character weights and dissimilarities between characters), and RV = 0 if and have no character in common. This similarity coeficient can in turn be transformed into a dissimilarity coeficient, which can be additively decomposed into five components.
The formalism, exposed in section 2, is rooted into Weighted Data Analysis. It involves three major steps: 1. Transforming a weighted network into a weighted Euclidean configuration (section 2.1).
This step is chiefly dictated by the formalism, which requires squared Euclidean dissimilarities, but permits as a byproduct a visualization of the character network (by weighted multidimensional scaling) of interest in itself. 2. Transforming the weighted Euclidean configuration into a kernel, whose eigendecomposition permits to visualize the network nodes (section 2.2) 3. Computing the generalized RV coeficient (beginning of section 3), assessing the similarity between two networks whose node weights may difer, and its exact decomposition into ifve terms (sections 3.1 and 3.2).
We formalize character networks as weighted networks (f , C), where f is the vector of the character weights, obeying ≥ 0 and ∑︀=1 = 1. The × matrix of edge weights C = ( ) is non-negative, and quantifies the importance of edge , reflecting some kind of afinity between the characters and , such as the their co-occurrence in the present study (section 4). It can be symmetric (as for C = A, where A is a binary adjacency matrix in a non-directed network), or not (as for asymmetric social relationships), in which case the network is directed.
Network visualization is a boundless research topic, even restricted as done here to the Euclidean embedding of networks. Specifically, one seeks to extract from the network data (f , C) a matrix D = ( ) of squared Euclidean dissimilarities between nodes, that is of the form = ‖x − x ‖2, where x is the representative vector of node . Two proposals only, among many others possibilities (extracting squared Euclidean dissimilarities from a weighted network is a topic in itself), are considered in this contribution: commute-time distances (section 2.1.1) and difusive distances (section 2.1.2).
By construction, the square matrix P = ( ) with components = /∙ (where ∙ = ∑︀
=1 ) is non-negative, with ∙ = 1 : it therefore constitutes the transition matrix of a Markov chain, defining a random walk on the network. The commute time com is the average time needed to go from to and then back to [see e.g. 3]. The matrix Dcom = (com) of commute times is well-known to be squared Euclidean [see e.g. 4], irrespectively of the properties of C, as far as C is reducible – that is as far as any two states can be directly or indirectly connected by the random walk.
One considers the edge weights V as generating a so-called instantaneous jump process, permitting to navigate from node to node with a rate given by (minus) the components of the weighted Laplacian L = Π− 21 [diag(C1) − C]Π− 21 , where Π = diag(f ), and C must be taken as symmetric, that is replaced if necessary by 12 (C + C⊤). Then choose a difusion time > 0, and compute the joint probability () to be initially in and in at time (or the other way round) as The squared Euclidean difusive distances
Ddif () = (dif ()) finally obtain as [see e.g. 5] dif () =
(2) + (2) − 2 () .
Weighted multidimensional scaling constitutes the canonical procedure for the low-dimensional visualisation of a weighted configuration (f , D) (see figure 1): 1. define Π = diag(f ), as well as the weighted centering matrix H = I − 1f ⊤ 2. obtain by double centering the matrix of scalar products B = − 21 H D H⊤ 3. define the matrix of weighted scalar products or kernel as K as:
K = √Π B√Π = √︀
4. perform the spectral decomposition K = UΛU⊤ where U = ( ) is orthogonal and
Λ = diag( ) diagonal
5. finally, define = √ /√, which is the MDS coordinate of node in dimension
. By construction, ∑︀ ( − )2 = . Also, the total dispersion or inertia of the
weighted configuration (f , D) reads Δ = 12 ∑︀,=1 = tr(K) = ∑︀−=11 .
(
At this stage, the book and the movie networks of characters have been expressed into commute
time or difusive kernels (
CV
RV = RV = √CV CV
where CV = Trace()
(
In particular, RV ≥ 0 (since K and K are positive semi-definite: this condition is equivalent to the squared Euclidean nature of D and D), RV ≤ 1 (by the Cauchy-Schwarz inequality) and RV = 1.
The null distribution of the weighted RV coeficient, i.e. assuming no relationships between the two configurations, and in particular its statistical significance, have been extensively investigated during the last decades [see e.g. 6, 1, and references therein].
The crucial issue here is that the character weights f and f difer in the two character
networks, whence the naming generalized weighted RV coeficient for the same quantity (
K = √︀Π B √︀Π
1
B = − 2 H D H⊤ K = √︀Π B√︀Π
This circumstance generates new challenging issues, whose investigation was one of the motivations for embarking on the present piece of research.
Note that well-established statistical procedures permitting to test the statistical significance of the weighted coeficient RVℎ are available [see e.g. 6, 1, and references therein]. However, testing the generalized weighted RV coeficient is, at the present time, a completely open issue.
As mentioned, the relative weights f and f (set to the uniform weights 1/ in most applications of Multivariate Analysis) may difer to a spectacular extent: their supports supp(f) and supp(f) do not even coincide in general, since version may contain characters absent in version , and vice-versa.
Define the compromise weight h as ℎ =
− ln(1 + )
rela⏟tive disper⏞sion, movie ⏟centroid co⏞rrection
This choice, initially dictated by formal considerations, permitting to further transform the
square roots in (
CV = trace(KℎKℎ) +
2
= ℎ ℎ + 2 ∑︁ ℎℓℓ
where ℎ is the squared Euclidean distance between the gravity centers of (h, D) and
(f, D). The quantity ℎ is defined analogously. Naturally, the gravity centers of (f, D)
and (h, D) generally difer, as are the gravity centers of (f, D) and (h, D), but the
diferences are extremely small in the case study (see Figure 6). The second component in (
A similarity coeficient such as the generalized weighted coeficient RV ∈ [0, 1] can be simply
converted into a dissimilarity coeficient ∈ [0, ∞) by = − ln RV. Applying the
transformation to (
− ln RV comp⏟osite dissimilarity ⏞ =
1
adjuste−⏟d dilsnsimRi⏞laVritℎy ℎ dissimilarit y−⏟be2twelenn⏞character weights rela−⏟tive2displner⏞siΓon,book
(
RVℎ = √︁
trace(ℎℎ)
trace(ℎ2)trace(ℎ2)
∈ [0, 1]
is a normalized measure of the centroid correction occurring in (
The Lion, the Witch and the Wardrobe was the second of the seven novels of the The Chronicles of Narnia, written by C. S. Lewis in 1950, and adapted into a film directed by A. Adamson released in 2005 (figure 4).
After semi-manual annotation of all named entities throughout the book and the movie script with the module charnetto [7], then gathered into groups of aliases, a list of 37 distinct characters were identified: ∙ 16 characters are common to the book and the movie ∙ 8 characters occur in the book only ∙ 13 characters occur in the movie only.
For each work, we defined the edge weights as the cross-count matrix = "number of co-occurrences of characters and within a window of 5 paragraphs" (each paragraph being delimited by a line break), with = 0 (see figure 4). Similarly, the character weights were, for a given work, simply defined as = ∙ /∙ . Figure 4 depicts the corresponding networks.
The cross-count matrices C permit to compute commute-time distances (section 2.1.1) and difusive distances (section 2.1.2). Weighted MDS (section 2.2) allows to extract in turn character coordinates, as depicted in figure 6.
In the present study, the centroids of configurations (f, D) and (f, D) are located at
the origin by construction, while the first coordinates of the centroids of (h, D) and (h, D)
are (¯ℎ, ¯ℎ) = (0.002, 0.004), respectively (¯ℎ, ¯ℎ) = (− 0.0007, − 0.005), and fairly close to
the origin: ℎ = 5.6 · 10− 5, respectively ℎ = 4.0 · 10− 5. As a consequence, the terms
in (
The generalized coeficient RV defined in (
Lilith
White FWoxitch
Peter FathMeraCughrriismtmas iit.radeen720=% .00MargaBreeItvtyy PMrorfess.sMoarcrSeaudysanELGMidAaunrtms.RMcoutThmleraubyulemnbnuMfnidnrMsu.srB.eBaveearver ilapn Jadis ,x2e .-02 tfr o c a
BaSccilheunsus -0.2 -0.1 0.0 0.1 factor 1, explained inertia= 38.4% 0.2 for the difusive distances, and for the commute-time distances.
Representing the relations between characters of a work as a weighted Euclidean configuration (f , D) arguably constitutes an instance of very distant reading, but not more distant than the usual representation by a weighted network. In both cases, the underlying dyadic formalism (i.e. based upon character pairs) could, and maybe should, be extended to -adic formalism, taking into account the simultaneous co-occurrences of = 0, 1, 2, 3, . . . characters (cliques). Also, the simple co-occurrence relation is in itself particularly rudimentary, yet surprisingly eficient as attested in many applications of Data Analysis, Natural Language Processing and Machine Learning.
On the one hand, we recognize that the mathematical requirements needed to appreciate
(or not) the present proposal may distress some amateurs of character networks. Also, a fully
convincing literary interpretation of the various terms in decomposition (
On the other hand, quantifying the dissimilarity between two networks cannot ignore mathematical issues, and the proposed formalism permits to propose a procedure which can be made fully automatic, and yields dissimilarities which can be shown to be metric, namely such that ≤ + (triangle inequality) for three versions , and . Also, the exact decomposition permits a detailed, systematically comparable, analysis of sources of (dis)similarities between two character networks.
More generally, the present formalism may contribute to better anchor the study of character networks into mainstream Data Analysis, and draw attention to otherwise overlooked phenomena: for instance, the weights similarity index can be related to the Chernof information occurring in the Neyman-Pearson statistical testing framework [see e.g. 8]; dealing with distinct distributions on the same objects endowed with pair distances evokes Optimal Transportation theory, together with as the possible involving of the earth mover’s distance [see e.g. 9, 10] in comparing two character networks; finally, the quantities Γ and Γ, which can exceed or be inferior to one, should be interpreted as indicators of the diversity loss entailed by the disappearance of -specific characters in the compromise weighting, or, to the contrary, as a diversity gain reflecting distinct emphasis and specificity between two variants and . But, as demonstrated in the case study, such a behaviour turns out to depend on the choice of the character dissimilarities D, whose suitability from a more literary perspective should certainly be further investigated in future developments.