Relational Algebras
Based on Wasserman and Faust (1994) Chapter 11
Relational algebras, also called role algebras, are methods for analyzing the structure of social roles by emphasizing multiple relations rather than actors.Role structures describe how relations are associated in the network, independent of the actors occupying those roles.Harrison White and his students pioneered this approach in the 1970s as an extension to blockmodeling.Relational algebras involve perhaps the most complex mathematics in network analysis, requiring intensive study to attain full comprehension.
RELATIONAL ALBEBRA– a formal structure consisting of sets of relations and operations to manipulate those relations.
Relational algebra can trace the indirect connections across multirelational networks.For a social structural analysis, the two required elements are:
(1)Dichotomous primitive relations (generator relations) among actors, represented by capital letters (e.g., U,T)
(2)The composition operation () that combines two or more primitive relations.Compound relation TU results from the composition operation, where tie i(T U)j occurs if there exists some actor k such thatiTk and kUj
Consider these graphs and matrices representing the advice-giver (A) and friendship (F) images for a three-position blockmodel of Krackhardt’s high-tech managers (W&F:439-442).The circling arrows show that high densities of ties occur among the individual actors within some jointly-occupied blocks:
ADVICE (A): FRIENDSHIP (F):
A / a / b / c / F / a / b / ca / 0 / 1 / 1 / a / 1 / 0 / 1
b / 0 / 1 / 1 / b / 0 / 0 / 0
c / 0 / 0 / 0 / c / 1 / 1 / 1
FORMING COMPOUNDS
A compound relation can be formed by the Boolean multiplication of two or sociomatrices.Boolean multiplication resembles to ordinary matrix multiplication, except that any cell entry greater than “0” is replaced by a “1”.A nonzero entry means that a compound relationship exist between that pair of actors/blocks.
Use “Tools/Matrix Algebra” in UCINET to open a window in which to write the matrix multiplication commands.Consult the Help Manual entries under “Algebra Package” and “Algebra, Binary Operation” for proper syntax.
In the example above, where the two UCINET binary matrices are named Advice & Friendship, the Boolean matrix product AF uses the command: “AF=bprod(Advice,Friendship)”Here’s the result:
AF / a / b / ca / 1 / 1 / 1
b / 1 / 1 / 1
c / 0 / 0 / 0
Each 1 entry in AF identifies an advice-giving block connected via one intermediary position to a friendship block .For example, in the advice network, block a gives advice to block c (aAc), while in the friendship network block c cites block b as its friend (cFb).Hence, the AF compound reveals a connection from block a to block b: (aAc)(cFb) = (aAFb).
Note that nonzero diagonal blocks in the image matrices are always used when composing a compound.Thus, block b’s compound tie to block c involves the latter’s within-block friendships: (bAc)(cFc) = (bAFc).
Because square images are conformable for matrix multiplication in reverse order, several distinct compound relations can be formed, including some self-multiplied compounds.
The FA product shows how one block can use their friends to pass advice to another block.For example, block c cites block a as friend and block a advises block b. Thus, the compound matrix reveals: (cFa)(aAb) = (cFAb).
FA / a / b / ca / 0 / 1 / 1
b / 0 / 0 / 0
c / 0 / 1 / 1
The FF product identifies that classic compound relationship “the friend of a friend”.Notice that, because block b cites no direct friends, it also can’t reach any indirect friends.However, the other blocks have friends who are connected to other friends: (aFc)(cFb) = (aFFb).
FF / a / b / ca / 1 / 1 / 1
b / 0 / 0 / 0
c / 1 / 1 / 1
Finally, the AA composition yields the “advisors of advisors” (evidently the experts’ mavens).But this compound matrix is identical to the original advice-giving ties!The relationship AA=A reveals that this advising network is transitive; for example, the compound (aAb)(bAc)=(aAAc) which is already a direct tie (aAc).Hence, we don’t need AA because A encompasses all the compound relations in its direct advising ties.
AA / a / b / ca / 0 / 1 / 1
b / 0 / 1 / 1
c / 0 / 0 / 0
ROLE TABLES for RELATIONS
Composition can involve sequences longer than two compounded primitive relations; e.g., AFFAAFA.A string of letters is a word, whose length is the number of primitive relations.Role algebraists inductively produce a “dictionary” containing the unique words (matrices/images), with the fewest letters, required for a complete description of a multiple-network system’s social role structure.
When a researcher generates a longer new word, she compares its sociomatrix to see whether any simpler word already in the dictionary also has that longer word’s sociomatrix.Words with identical matrices or images are equivalent, and the set of all words with identical images comprise an equivalence class.
For the Krackhardt high-tech images, the shortest unique words in the dictionary are A, F, AF, FA, and FF.See W&F440 for examples of longer words in those equivalence classes.
In a multiplication table, or role table, each row and column entry corresponds to a unique primitive or compound relation.Instead of displaying network images (as W&F show Fig. 11.2), each equivalence class in the table is labeled by the graph’s word.The cell entries in the table contain the smallest word that results from multiplying the row matrix by the column matrix.
- Matrix multiplication is associative: the order of performing successive multiplications does not affect the result: ABC=(AB)C=A(BC)
- Matrix multiplication is not commutative: the result of multiplying two matrices may differ by the sequence: AB≠BA
In mathematical theory, a semigroup is defined as a set elements with an associative binary operator on it.Thus, a social network semigroup is the set of images/matrices formed by a set of relations and the composition operation (Boyd 1990, 1992, 2000; Pattison 1993).If all compositions of the primitive relations are also members of the set, then a semigroup is closed under associative matrix multiplication (437: the role table contains “all possible images that can result from the operation of composition on the primitive relations”).
The role table for advice and friendship (W&F Fig. 11.5) shows that composing any pair of the five unique words yields four of these words.For example, multiplying (AF)(FA) = (AFFA).But, the first three terms can be factored: (AFF)=(AF)(F) and we find in the table that (AF)(F)=(AF).Hence, by substitution (AFFA)=(AFF)(A)=(AF)(A).Finally, the role table shows that (AF)(A)=(A), so the initial (AF)(FA) product reduces to just (A), as displayed in row 3 column 4.
/ A / F / AF / FA / FFA / A / AF / AF / A / FF
F / FA / FF / FF / FA / FF
AF / A / AF / AF / A / AF
FA / FA / FF / FF / FA / FF
FF / FA / FF / FF / FA / FF
Note that rows 1 & 3 are identical, as are rows 2, 4, & 5, as well as two column pairs, 1 & 4 and 2 & 3.These identities imply opportunities for further simplification of the social structure represented in Krackhardt high-tech manager role table.
SIMPLIFYING a ROLE TABLE
Role table simplification involves reducing the number of network images or words but preserving important structural properties.Each image in the initial set is mapped onto a smaller number of images in the simplified set.“The reduction of the role table is a partition of the distinct images, S, into a smaller collection of classes, Q.” (W&F:443).Unfortunately, a unique or “best” reduction may not be possible for some networks.
Image simplification strategies include: (1) substantive approaches that combine images with the identical meaning or similar operation; (2) sociometric approaches equate images with similar ties that may differ substantively.Sociometric similarity could be assessed using correlation to measure association, or finding images that are contained within (subset of) another image.See W&F:444-445 for an application of the latter technique to the A&F role table.
A homomorphic reduction of an original role table involves a mapping that preserves the composition operation.More than one homomorphic image may exist.
One homomorphic image for the A&F role table permutes and partitions the original 5x5 multiplication table into two groups of rows (and corresponding columns) that produce “nearly identical results”: {1,3} and {2,4,5} which have the word equivalences {A,AF} and {F,FA,FF}.The reduced matrix expresses a first letter law that “any two elements always result in an element that is in the same class as the first element of the composition“ (447).
An alternative homomorphic image groups the columns {1,4} and {2,3,5}, with word equivalences {A,FA} and {F,AF,FF}.Note that this reduction satisfies a last letter law that “the composition of any two elements results in an element that is in the same class as the second element the composition” (448).
COMPARING ROLE STRUCTURES
If the same or comparable relations are measured for two or more network systems, their role tables can be compared to describe and measure their formal similarities and/or differences.Boorman and White (1976) proposed the joint homomorphic reduction of two role structures as a method for summarizing common features (see W&F:451-460).JHR involves two mappings that preserve the composition operation, resulting in a new multiplication role table that is a reduction of both original tables.As the union of two roles structures, the role table contains all the word equations appearing in one or both systems.Breiger and Pattison (1978) interpreted the joint homomorphic reduction of three networks among political elites in a German town and a U.S. city as an instance of Granovetter’s strong-weak tie hypothesis.
REFERENCES
Breiger, Ronald L. and Philippa E. Pattison. 1978. “The Joint Role Structure of Two Communities’ Elites.” Sociological Methods & Research 7:213-226.
Boyd, John P. 1990. Social Semigroups: A Unified Theory of Scaling and Blockmodeling as Applied to Social Networks. Fairfax, VA: GeorgeMasonUniversity Press.
Boyd, John P. 1992. “Relational Homomorphisms.” Social Networks 14:163-186.
Boyd, John P. 2000. “Social Networks and Semigroups.” Politica y Sociedad 33:105-112.
Pattison, Phillipa. 1993. Algebraic Models for Social Networks. New York: CambridgeUniversity Press.
1
SOC8412 Social Network Analysis Fall 2008