AddingHigher-Order Interactions to Network Ontology

Douglas R. White

Vladimir Batagelj

Andrej Mrvar

Balazs Vedres

Sept 1, 2004, SFI (1.00)

Network ontologies typically assume that network interaction is of the first-order, at the level of interacting dyads. Here, we look at interactions where nodes interact with dyadic edges, in various types of second-order interactions. We use the idea of a tensorspace of potential interaction among n-tuples but are careful to limit our formalisms for such interactions to cases where such interactions are the most plausible and the best documented. Our canonical examples are supervisory relations (Nadel 1957) over co-workers or co-occupants of the same role, primate interventions, catalysts that act on interaction rates between dyads, and industries with horizontal or vertical integration of firms through common ownership relations.

Second-order interactions may differ from ordinary triadic interactions in various ways, as shown in Figure 1. Graph (a) shows an ordinary triad consisting of all three possible pairwise relations among three nodes. Figure (b) is not technically a graph but illustrates how a supervisor of two employees might attempt to or succeed in exerting influence not just on the two subordinates independently but on the dyadic edge or relationship between them. Figure (c) is also not a graph but illustrates how a pair of individuals of opposite sex (e.g., married couple) might engender a child, and also have individual relationships with the child. The basic idea here is that interaction with a pair of nodes is not always reducible to interaction to each node in the pair individually.

(a)(b)(c)

Figure 1. Ordinary Triadic versus Second-Order Node/Edge Interactions

It is the directed arrows between an individual and a pairwise relation that signal the kinds of second-order interaction in which we are interested. We consider the case where the receiving end of the arrow signals some sort of subordination, such as child/parents or employees/supervisor, in a relationship structure in which a dyad may be superordinate (parents) or subordinate (employees) to one or more other nodes.

DefiningSecond-Order Interaction as Join-Graphs

To model second-order interactions as graphs we use Harary’s (1971) definitions of digraphs, arcs and demiarcs. A digraph D=<V,A> is a setV of vertices or points and a set of arcs or ordered pairs of distinct elements in V2. A demiarcis a point in V together with a direction{>,<} for {out,in}. An out-demiarc u is denoted u> and an in-demiarc v is denoted >v. A u,v arc may be composed of two demiarcs, u> and >v, that joinat u◊v. A demiarc thus has a stub or join at which it may join with another demiarc to form an arc, and two demiarcs join to form an arc u,v when they share a u◊v join.

Characterizing all arcs in a digraph as pairs of demiarcs with stubs is useful for constructing a simulated digraph that has the same indegree and outdegree distribution as one observed by disconnecting its demiarcs and rejoining them according to some probability function.

A join-digraph D=<V,A,₪,J> is a digraph in which, in addition tonodes in V and arcs in AV2, there is a set ₪ of joins or stubs that join demiarcs in (V,{>,<}).

We now generalize to the joining of demiarcs with a new graph structure that allows joins to higher-order objects such as sets of interrelated elements. We will have in mind the case where this kind of structure conveys interaction that influences the edges or arcs among nodes rather than individually with the nodes themselves. A good example of this process is catalytic action, in which one a chemical substance X decays to Y at a rate that is governed not only by available heat energy but the presence of a third, catalytic, substance Z.

A demitongis a set T of points in V together with a direction{>,<} for {out,in}, and ak-demitong is one with cardinality k=|T|. An out-demitong t is denoted t> and can join an in-demitong (or in-demiarc) denoted >u. A k-demitong (1-demitong, 2-demitong, k-demitong), then, is a demitong directed towards k nodes and their edges (arcs, loops). By this definition, while a 1-demitong is directed towards a single node and thus has the structure of a demiarc, we might consider it to be directed toward a loop of that node. The idea of a demitong is that when it is part of a connection among nodes, it specifies how the nodes to which the k contacts of a k-tong connect are simultaneously acted upon so as to affect the relationships among the contact nodes. For this to occur, however, a demitong must be joined with a matching demi-object to connect one or more nodes to the kcontacts of the k-demitong, which we call an activation.

A tong-digraph is then a join-digraph D=<V,A,₪,J > in which in addition to nodes in V and arcs in A, every arc has a corresponding pair of demiarcs, and there are an additional set J of joined demiarc/demitong or demitong/demitongpairs where the demitongs are ordered pairs in (Π(V),{>,<}) consisting of subsets in the power-set of Vordered with respect to their joined demiarcs or demitongs by a direction{>,<} for {out,in}. A tong-digraph is thus defined within a tensor structure where Π(V) is the power-set of V, and it is possible to simulatea tong-digraph that has the same indegree and outdegree distribution as one observed by disconnecting its demicomponents and rejoining them according to some probability function.

A k-tong-digraph is one for which the largest cardinality of sets in its tensor structure in Π(V) is k.A tong-digraph thus partitions the interactions in a network into those of simple dyads conventionally represented by arcs (or, if symmetric, edges), and potentially more complex interactions represented by joins withdemitongs.A 2-tong digraph is thus a tong digraph that contains at least one graph structure composed of joined demiarc/demitong ordemitongpairs (in addition to demiarc pairs). In Figure 2, demitong joins are represented by the graphic symbol . It shows the examples above diagrammed as 2-tong-digraphs as contrasted with ordinary triads.

(a)(b)(c)

Figure 2. Second-Order Interactions as Graphs versus Ordinary Triads

Figure 2(c) shows an ordinary triad which, as in (a) and (b), may coexist with higher order tong-structures. Figure 3 shows 2-demitongs and demiarcs as separate or elementary structures, with the same graphic element for the joins of DTs and Das. Figure 4 shows three ways that 2-demitongs may interlock with demiarcs or with one another, with a doubling of the graphic element for the joins of two DTs.

(a) DT to pair(b) DT from pair(c) DA to node(d) DA from node

Figure 3. Elementary 2-Demitongs (DTs) and Demiarcs (DAs)

(a) DT to a pair(b) DT from a pair(c) DTs to and from a pair

Figure 4. Interlocking DTs and DAs

A tong is thus an interlocked and ordered pair of demiarc/demitong relations between a single node and one or more nodes and their arcs (edges, loops). Figures 4 (a) and (b) show tongs but 4(c) is more complex. It is important to distinguish carefully the cases shown in Figure 5, where (a) shows two (out-) demiarcs joined to a 2-tong, (b) shows a 2-tong joined to two (in-) demiarcs, and (c) is as before, a 2-in-tong jointed to a 2-out-tong. The difference is that in (a) the upper pair have separate interests or influences on the relationship of the lower pair, while in (b) the upper pair have common interests or influences on each of the lower pair separately, while in (c) the upper pair have common interests or influences on the relationship of the lower pair.

(a) DT to a pair(b) DT from a pair(c) DTs to and from a pair

Figure 5. Interlocking DTs

It is important to note that in the general case, atong-digraph D=<V,A,₪,J > is not a bipartite graph with two sets of nodes, V and J, because set J is one of demiarc/demitong or demitong/demitong pairs that join to connect nodes in V but according to different orders of interaction. The demiarc and demitong construction of tong-digraphs, however, makes it possible to compare then to simulated graph structures with the same indegree and outdegree distributions. In some limited cases, however, it may be relevant and useful to define V and ₪ as two distinct sets of nodes.

Applying the Tong-Digraph Ontology

(1) Kinship

A bipartite p-graph is an example of a tong-digraphD=<V,A,₪,J > representing kinship and genealogical connections in which V is the set of people, ₪ the set of marriages and single (unmarried) individuals, J the mappings from V into ₪ according to who marries whom and from ₪ into V according to which couples are the parents of individuals in V, and A are the derivative arcs from individual parents to individual children. Figure 6 shows an example of such a bipartite kinship graph for 4-marriages in which two brother-sister pairs intermarry. Not shown are the derived parent-child arcs from the senior to the junior generation within each nuclear family. A bipartite graph such as this has some affinity to a Petri-net (refs) in which there are two types of nodes, one set (the square nodes for example) aggregating resources from the other set (here, individual parents) to pass down to other members of that set (individual chidren).

Figure 6. Tong-digraph for Kinship Networks

Bipartite p-graphs as diagrammed as tong-digraphs as in Figure 6 are highly effective in representing large kinship networks and in finding cycles of intermarriage within families and among sets of families.

(2) Role Interlock

Nadel (1957) argues that the coherence of interrelations among social roles in a community or society is brought about by supervisory relationships in which some individuals intervened to reshape the dyadic relationships of others. A doctor with several nurses, for example, will intervene in a supervisory capacity to shape the interactions among them, other supervisory interventions will occur between doctors and their patients, between patients and their insurance companies, and between the latter and the set of doctors. In an organized community of interaction, these interlocks will intermesh in ways that tend to create a coherent system of norms, sanctions, and interpersonal expectations.

Figure 7 illustrates a situation of role interlock commonly observed in societies in which marriage with a wife’s sister is allowed as a means of reinforcing or continuing an alliance between families or descent groups. Here there are now two sets of arcs, solid arrows representing actual kinship and marriage links, and dotted arrows representing potential claims in secondary marriages: a man with WiSi (sororal marriage), his brother with BrWiSi (extension of the sororate), the wife with a departed HuBr (levirate), and so forth. As Nadel noted in his discussion of kinship networks, it is in such cases that either (a) a man avoids his wife’s parents or (b) jokes with his siblings-in-law. This situation of role interlock is considered to be one of a potential conflict in supervisory authority: the husband, for example, has a potentialclaim over an unmarried WiSi, while the wife’s parents have a supervisory interest in the prospects for their unmarried daughter’s marriage that includes the possibility of her not marrying the SiHi but rather some other potential son-in-law from another family. Evidence that potential role conflict is solved through coherent behavior interlock is the fact that either of the possibilities (a) or (b) above almost invariably occur where sororatic or leviratic claims are present between families, and that outcomes (a) and (b) occur mutually exclusive of one another. The coherent logic here is that the potential conflict is resolved if the parents-in-law are avoided, but if not, then it surfaces in the form of ritualized joking between siblings-in-law, whose content is consistent (in ways of joking about sex) with the unresolved ambiguity over the unmarried WiSi/SiHu relationship.

Figure 7. Tong-digraph for Kinship Roles

(3) Alpha Primate Interventions in Juvenile Conflict Dyads

In studies of primate behavior, recurrent conflicts in pairs or larger sets of juveniles are easily and often observed and can be disruptive in a community if they escalate into series or serious conflicts with disrupt activities of community members or do them harm. Coding conflict dyads as demitongs and intervening adults as having demiarc potential to couple with a demitong intervention that may dampen or halt such conflicts has the potential, with appropriate use of simulating different probabilistic models of demiarc/demitong couplings in the activation of such interventions, to answer research questions such as:

What are the patterns of intervention as compared to different probability models of demiarc joins with demitongs? What is the probability structure of such joins for the adults, males or alphas?What is their probability structure with respect to the juvenile conflict dyads?

What are the higher-order patterns, such as if one adult tends to intervene for a given set of demitong pairs, will another adult’s probability of intervention decrease for these pairs?

(4) Catalytic Action

Catalytic action occurs not only among threesomes of chemical interactions but in actions that affect interaction rates between dyads in a variety of different network contexts.

(5) Effects of Co-Ownership

industries with horizontal or vertical integration of firms through common ownership relations.

The shift is from mundane relations among individuals to the higher order

(6) Three-Way Interaction Statistics

White, Pesner (1983)

Conclusions… (to be continued)

The substantive instantiation of a tong is the class of (often observable events of) supervisory (interventionist) relations. By itself, a tong, simply by its existence has no effect unless it is at some point activated by one (or more) supervisors. After a supervisory event operating through a tong has been activated one or more times, and perhaps habituated, it may become internalized so that the (supervised) parties to the tong may modify their dyadic behaviors in anticipation of the potential activation of supervision.

A network with tongs is one with ordinary nodes, actors with dyadic interactions, and k-tongs that are activators of events that alter relations among other sets of nodes.

References

Harary, F. (1971). Demiarcs: An atomistic approach to relational systems and group
dynamics. Journal of Mathematical Sociology, Vol. 1, 195-205.

White, D. R., and R. Pesner. 1983. Internal Replication and the Systems Concept in Non-Experimental Research.Behavior Science Research 18:26-44.

White, D. R.,R. Pesner,andK.Reitz. 1983. An Exact Significance Test for Three-Way Interaction.Behavior Science Research 18:103-122.

  • Petri Nets: Properties, Analysis and Applications
    T. Murata, Proceedings of the IEEE, Vol. 77, No 4, April, 1989, pp. 541-580.
  • Petri Net Theory and the Modeling of Systems
    J. L. Peterson, Prentice-Hall, N.J., 1981.
  • Petri Nets, An Introduction
    W. Reisig, EATCS, Monographs on Theoretical Computer Science, W.Brauer, G. Rozenberg, A. Salomaa (Eds.), Springer Verlag, Berlin, 1985.
  • Lectures on Petri Nets I: Basic Models
    W. Reisig, G. Rozenberg (Eds.), Advances in Petri Nets, Lecture Notes in Computer Science, vol. 1491, Springer-Verlag, 1998, Originates from the Advanced Course on Petri Nets held in Dagstuhl, Germany, October 1996.
  • Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications
    C. Girault, R. Valk, Springer-Verlag, 2002,
  • Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use. Volume 1, Basic Concepts
    K. Jensen, Monographs in Theoretical Computer Science, Springer-Verlag, 2nd corrected printing 1997, More information available on book homepage
  • Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use. Volume 2, Analysis Methods
    K. Jensen, Monographs in Theoretical Computer Science, Springer-Verlag, 2nd corrected printing 1997. More information available on book homepage
  • Stochastic Petri Nets -- An Introduction to the Theory (2nd edition)
    F. Bause, P. Kritzinger, Vieweg Verlag, Germany, 2002, More information available on book homepage
  • Modelling with Generalized Stochastic Petri Nets
    M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, G. Franceschinis,
    Wiley Series in Parallel Computing, John Wiley and Sons, 1994, More information available on book homepage
  • Performance Modelling with Deterministic and Stochastic Petri Nets
    C. Lindemann, John Wiley and Sons, 1998. More information available on book homepage
  • Performance Analysis of Communication Systems: Modeling with Non-Markovian Stochastic Petri Nets
    R. German, John Wiley and Sons, 2000, More information available on book homepage
  • Stochastic Petri Nets: Modelling, Stability, Simulation
    P. Haas, Springer-Verlag, New York, 2002, More information available on book homepage
  • Timed Petri Nets, Theory and Application
    J. Wang, Kluwer Academic Publishers 1998.
  • Theoretische Informatik - Petri-Netze
    L. Priese, H. Wimmel, Springer-Verlag, Berlin Heidelberg, 2003, Note: In German
  • Free Choice Petri Nets
    J. Desel, J. Esparza, Cambridge Tracts in Theoretical Computer Science 40, Cambridge University Press, 1995.
  • Fuzziness in Petri Nets
    J. Cardoso, H. Camargo (Eds.), Studies in Fuzziness and Soft Computing series, Vol. 22, Springer-Verlag, 1999.
  • Supervision of Petri Nets
    Geert Stremersch, Kluwer International Series on Discrete Event Dynamic Systems, 2001.
  • Workflow Management: Models, Methods, and Systems
    Wil van der Aalst, Kees van Hee, MIT Press, 2002.
  • Notations and Terminology on Petri Net Theory
    E. Best, C. Fernandez, Arbeitspapiere der GMD 195, March 1987.
  • Advanced Course on Petri Nets
    Bad Honnef, West Germany, September 1986. Published in `Advances' series, LNCS Vols 254, 255, 1987.
  • Petri Nets and Grafcet -- Tools for Modeling Discrete Event Systems
    R. David, H. Alla, Prentice Hall, 1992.

1