Multirelational networks

A multirelational network is denoted by

It contains different relations (sets of lines), £,-, 1 < i < k, over the same set of vertices. Also, the weights from W are defined for different relations or their unions.

Examples of multirelational networks include: transportation systems in a city (stations/stops and lines[1]); networks of words in statements (e.g. WordNet with words, semantic relations: synonymy, antonymy, hyponymy, meronymy, etc.); the KEDS network (described briefly in Chapter 1) where actors are states and organizations and relations between them: visiting, asking for information, warning, expelling person(s), etc.

An often used way for obtaining networks is by computer-assisted text analysis (CaTA). Popping (2000) distinguishes three main approaches to CaTA: thematic TA, semantic TA, and network TA. The terms considered in TA are collected into a dictionary (which can

Time slice December 1922.

Figure 2.5 Time slice December 1922.

be fixed in advance, or built dynamically). The main two problems with terms are the equivalence of different words (synonyms) representing the same term and the ambiguity with the same word (homonym) representing different terms. These problems imply a need for the coding - transformation of raw text data into formal descriptions - to be done often manually or semiautomatically. The units of TA are usually clauses, statements, paragraphs, news, messages, etc.

Hitherto, both thematic and semantic TAs mainly used statistical methods for analyzing coded data. In thematic TA, the units are organized in a rectangular matrix, Text units x Concepts, which is essentially a two-mode network.[2] In semantic TA the units (usually clauses) are encoded according to the S-V-O (Subject-Verb-Object) model or its improvements.10 A generic encoding form is:

The encoded text can be directly considered as a multirelational network with Subjects u Objects as vertices and Verbs as relations.

In Pajek, a line can be assigned to a relation in two ways:

• By adding to a keyword for descriptions of lines (*arcs, *edges, *arcslist, * edges list, *matrix) the number of a relation followed by its name:

*arcslist :3 "sent a letter to" All lines controlled by this keyword belong to the specified relation.

• Any line controlled by *arcs or *edges can be assigned to a selected relation by starting its description by the number of this relation (followed by a colon, :,). For example:

3: 47 14 5

states: a line with end-vertices 47 and 14 and weight 5 belongs to relation 3.

An example of a multirelational temporal network

The KEDS project, described in Chapter 1, includes political event data focused on the Middle East, the Balkans, and West Africa. Figure 2.6 shows how KEDS data can be transformed into Pajek's temporal multirelational network for an example concerning the Balkans. At the bottom right side of Figure 2.6 in each line the corresponding text encoding on KEDS file is presented. It has 325 vertices representing different countries, their institutions and

A fragment of the Balkan KEDS network.

Figure 2.6 A fragment of the Balkan KEDS network.

international organizations. The first six and last eight vertices are listed in Figure 2.6. Each vertex is assumed to be active all the time [ 1 - * ]. The vertices are followed by a list of *arcs keywords linking the relation number to the corresponding label. The events data follow the simple *arcs keyword and have the form r: uv 1 [t]

In words: the arc (u, v) with weight 1 belonging to relation r is active in time point t.

Two-mode networks

Examples of such networks include: persons belonging to societies with years of membership as weights, consumers buying goods with quantity or value as weights, Supreme Court justices 'voting' on decisions with agreeing or dissenting as signed weights, authors publishing in journals with publication counts as weights.

Formally, in a two-mode network N = ((V, V), £, V, W), the set of vertices consists of two disjoint sets of vertices V and V, and all the lines from £ have one end-vertex in V and the other in V. Often also a weight w : £ ->• R e W is given; if not, we assume w(u, v) = 1 for all (u, v) e £. A two-mode network can be described also by a rectangular matrix A = [auv]VxV.

In Pajek, a two-mode network is announced by * vert ices n nv with the keyword * vert ices followed by two numbers: the total number of vertices11 n = V + V and the number of vertices in the first set nv = U.U is followed by the list of all vertices from the first set, followed by the list of all vertices from the second set.

An example of a two-mode network is shown in Figure 2.7. The data came from the Deep South study of Davis and Gardner (1941). The figure is a redrawn version of Figure 8.3 from Doreian et al. (2005). Part of the Pajek file for this network is in Figure 2.8. There were nv = 18 women (shown as ellipses) who attended nv = 14 events (shown as boxes); n = 32.

Three numbers following the vertex label are its x, y, z coordinates.12 The tags ell ipse and box determine the shapes of the vertices and are valid until changed by another tag. Figure 2.8 shows a partition of the women into two subsets and the events into three subsets according to which women tended to attend which events.

  • [1] On the London Underground, all successive pairs stations between Baker Street and Liverpool Street have edges corresponding to the Circle, the Metropolitan, and the Hammersmith and City lines.
  • [2] Examples of the available software include: M.M. Miller: VBPro, H. Klein: Text Analysis/ TextQuest. 10 Examples include: Roberto Franzosi; KEDS and Tabari; RDF triples in semantic web, SPARQL.
< Prev   CONTENTS   Next >