14.  Automorphic equivalence

• Defining automorphic equivalence
• Uses of the concept
• Finding equivalence Sets
  • All permutations (i.e. brute force)
  • Optimization by tabu search
  • Equivalence of distances: Maxsim
• Summary

Automorphic equivalence is not as demanding a definition of similarity as structural equivalence, but is more demanding than regular equivalence. There is a hierarchy of the three equivalence concepts: any set of structural equivalences are also automorphic and regular equivalences. Any set of automorphic equivalences are also regular equivalences. Not all regular equivalences are necessarily automorphic or structural; and not all automorphic equivalences are necessarily structural.

Formally "Two vertices u and v of a labeled graph G are automorphically equivalent if all the vertices can be re-labeled to form an isomorphic graph with the labels of u and v interchanged. Two automorphically equivalent vertices share exactly the same label-independent properties." (Borgatti, Everett, and Freeman, 1996: 119).

More intuitively, actors are automorphically equivalent if we can permute the graph in such a way that exchanging the two actors has no effect on the distances among all actors in the graph. If we want to assess whether two actors are automorphically equivalent, we first imagine exchanging their positions in the network. Then, we look and see if, by changing some other actors as well, we can create a graph in which all of the actors are the same distance that they were from one another in the original graph.

In the case of structural equivalence, two actors are equivalent if we can exchange them one-for-one, and not affect any properties of the graph. Automorphically equivalent actors are actors that can be exchanged with no effect on the graph -- given that other actors are also moved. If the concept is still a bit difficult to grasp at this point, don't worry. Read on, and then come back after you've looked at a few examples.

table of contents

Structural equivalence focuses our attention on pair-wise comparisons of actors. By trying to find actors who can be swapped for each other, we are really paying attention to the positions of the actors in a particular network. We are trying to find actors who are clones or substitutes.

Automorphic equivalence begins to change the focus of our attention, moving us away from concern with individual's network positions, and toward a more abstracted view of the network. Automorphic equivalence asks if the whole network can be re-arranged, putting different actors at different nodes, but leaving the relational structure or skeleton of the network intact.

Suppose that we had 10 workers in the University Avenue McDonald's restaurant, who report to one manager. The manager, in turn, reports to a franchise owner. The franchise owner also controls the Park Street McDonald's restaurant. It too has a manager and 10 workers. Now, if the owner decided to transfer the manager from University Avenue to the Park Street restaurant (and vice versa), the network has been disrupted. But if the owner transfers both the managers and the workers to the other restaurant, all of the network relations remain intact. Transferring both the workers and the managers is a permutation of the graph that leaves all of the distances among the pairs of actors exactly as it was before the transfer. In a sense, the "staff" of one restaurant is equivalent to the staff of the other, though the individual persons are not substitutable.

The hypothetical example of the restaurants suggests the main utility of the automorphic equivalence concept. Rather than asking what individuals might be exchanged without modifying the social relations described by a graph (structural equivalence), the somewhat more relaxed concept of automorphic equivalence focuses our attention on sets of actors who are substitutable as sub-graphs, in relation to other sub-graphs. In many social structures, there may well be sub-structures that are equivalent to one another (or approximately so). The number, type, and relations among such sub-structures might be quite interesting. Many structures that look very large and complex may actually be composed (at least partially) of multiple identical sub-structures; these sub-structures may be "substitutable" for one another. Indeed, a McDonalds is a McDonalds is a McDonalds...

table of contents

With binary data, numerical algorithms are used to search for classes of actors that satisfy the mathematical definitions of automorphic equivalence.  Basically, the nodes of a graph are exchanged, and the distances among all pairs of actors in the new graph are compared to the original graph.  When the new graph and the old graph have the same distances among nodes, the graphs are isomorphic, and the "swapping" that was done identifies the isomorphic sub-graphs.

One approach to binary data, "all permutations," (Network>Roles & Positions>Automorphic>All Permutations) literally compares every possible swapping of nodes to find isomorphic graphs.  With even a small graph, there are a very large number of such alternatives, and the computation is extensive.  An alternative approach with the same intent ("optimization by tabu search") (Network>Roles & Positions>Exact>Optimization) can much more quickly sort nodes into a user-defined number of partitions in such a way as to maximize automorphic equivalence.  There is no guarantee, however, that the number of partitions (equivalence classes) chosen is "correct," or that the automorphisms identified are "exact."  For larger data sets, and where we are willing to entertain the idea that two sub-structures can be "almost" equivalent, optimization is a very useful method.

When we have measures of the strength, cost, or probability of relations among nodes (i.e. valued data), exact automorphic equivalence is far less likely.  It is possible, however, to identify classes of approximately equivalent actors on the basis of their profile of distance to all other actors.  The "equivalence of distances" method (Network>Roles & Positions>Automorphic>MaxSim) produces measures of the degree of automorphic equivalence for each pair of nodes, which can be examined by clustering and scaling methods to identify approximate classes.  This method can also be applied to binary data by first turning binary adjacency into some measure of graph distance (usually, geodesic distance).

Let's look at these in a little more detail, with some examples.

table of contents

The automorphisms in a graph can be identified by the brute force method of examining every possible permutation of the graph. With a small graph, and a fast computer, this is a useful thing to do. Basically, every possible permutation of the graph is examined to see if it has the same tie structure as the original graph. For graphs of more than a few actors, the number of permutations that need to be compared becomes extremely large.

Let's use Networks>Roles & Positions>Automorphic>All Permutations to search the Wasserman-Faust network shown in figure 14.1.

Figure 14.1.  Wasserman-Faust network

The results of Networks>Roles & Positions>Automorphic>All Permutations for this graph are shown in figure 14.2.

Figure 14.2.  Automorphic equivalences by all permutations search for the Wasserman-Faust network

The algorithm examined over three hundred sixty two thousand possible permutations of the graph.  The isomorphism classes that it located are called "orbits."  And, the results correspond to our logical analysis (chapter 12).  There are five "types" of actors who are embedded at equal distances from other sets of actors: actor A (orbit 1), actor C (orbit 3), and actor G (orbit 7) are unique.  Actors B and D form a class of actors who can be exchanged if members of other classes are also exchanged; actors E, F, H, and I (5, 6, 8, and 9) also form a class of exchangeable actors.

Note that automorphism classes identify groups of actors who have the same pattern of distance from other actors, rather than the "sub-structures" themselves (in this case, the two branches of the tree.

table of contents

For larger graphs, direct search for all equivalencies is impractical both because it is computationally intensive, and because exactly equivalent actors are likely to be rare.

Network>Roles & Positions>Exact>Optimization provides a numerical tool for finding the best approximations to a user-selected number of automorphism classes.  In using this method, it is important to explore a range of possible numbers of partitions (unless one has a prior theory about this), to determine how many partitions are useful. Having selected a number of partitions, it is useful to re-run the algorithm a number of times to insure that a global, rather than local minimum has been found.

The method begins by randomly allocating nodes to partitions. A measure of badness of fit is constructed by calculating the sums of squares for each row and each column within each block, and calculating the variance of these sums of squares. These variances are then summed across the blocks to construct a measure of badness of fit. Search continues to find an allocation of actors to partitions that minimizes this badness of fit statistic.

What is being minimized is a function of the dissimilarity of the variance of scores within partitions. That is, the algorithm seeks to group together actors who have similar amounts of variability in their row and column scores within blocks. Actors who have similar variability probably have similar profiles of ties sent and received within, and across blocks -- though they do not necessarily have the same ties to the same other actors, they are likely to have ties of the same distance to actors in other classes.

Let's examine the Knoke bureaucracies information exchange network again, this time looking for automorphisms.  In the Knoke information data there are no exact automorphisms. This is not really surprising, given the complexity of the pattern (and particularly if we distinguish in-ties from out-ties) of connections.

We ran the routine a number of times, requesting partitions into different numbers of classes.  Figure 14.3 summarizes the "badness of fit" of the models.

Figure 14.3.  Fit of automorphic equivalence models to Knoke information network

There is no "right" answer about how many classes there are. There are two trivial answers: those that group all the cases together into one partition and those that separate each case into its own partition. In between, one might want to follow the logic of the "scree" plot from factor analysis to select a meaningful number of partitions. Look first at the results for three partitions (figure 14.4).

Figure 14.4.  3-Class automorphic equivalence solution for the Knoke information network

 At this level of approximate equivalence, there are three classes - two individuals and one large group.  The newspaper (actor 7) has low rates of sending (row) and high rates of receiving (column); the mayor (actor 5) has high rates of sending and high rates of receiving.  With only three classes, the remainder of the actors are grouped into an approximate class with roughly equal (and higher) variability of both sending and receiving.

Because automorphic equivalence actually operates on the profile of distances of actors, it tends to identify groupings of actors who have similar patterns of in and out degree.  This goes beyond structural equivalence (which emphasizes ties to exactly the same other actors) to a more general and fuzzier idea that two actors are equivalent if they are similarly embedded.  The emphasis shifts from individual position, to the role of the position in the structure of the whole graph.

table of contents

When we have information on the strength, cost, or probability of relations (i.e. valued data), exact automorphic equivalence could be expected to be extremely rare.  But, since automorphic equivalence emphasizes the similarity in the profile of distances of actors from others, the idea of approximate equivalence can be applied to valued data.  Network>Roles & Positions>Automorphic>MaxSim generates a matrix of "similarity" between shape of the distributions of ties of actors that can be grouped by clustering and scaling into approximate classes.  The approach can also be applied to binary data, if we first convert the adjacency matrix into a matrix of geodesic near-nesses (which can be treated as a valued measure of the strength of ties).

The algorithm begins with a (reciprocal of) distance or strength of tie matrix. The distances of each actor re-organized into a sorted list from low to high, and the Euclidean distance is used to calculate the dissimilarity between the distance profiles of each pair of actors. The algorithm scores actors who have similar distance profiles as more automorphically equivalent. Again, the focus is on whether actor u has a similar set of distances, regardless of which distances, to actor v. Again, dimensional scaling or clustering of the distances can be used to identify sets of approximately automorphically equivalent actors.

Let's apply this idea to two examples, one simple and abstract, the other more realistic.  First, let's look at the "line" network (figure 14.5).

Figure 14.5.  Line network

Figure 14.6 shows the results of analyzing this network with  Network>Roles & Positions>Automorphic>MaxSim

Figure 14.6.  Automorphic equivalence of geodesic distances in the line network.

The first step is to convert the adjacency matrix into a geodesic distance matrix.  Then the reciprocal of the distance is taken, and a vector of the rows entries concatenated with the column entries for each actor is produced.  The Euclidean distances between these lists are then created as a measure of the non-automorphic-equivalence, and hierarchical clustering is applied.

We see that actors 3 and 5 (C and E) form a class; actors 2 and 6 (B and F) form a class; actors 1 and 7 (A and G) form a class, and actor 4 (D) is a class.  Mathematically, this is a sensible result; exchanges of labels of actors within these sets can occur and still produce an isomorphic distance matrix.  The result also makes substantive sense -- and is quite like that for the Wasserman-Faust network.

This approximation method can also be applied where the data are valued.  If we look at our data on donors to California political campaigns, we have measures of the strength of ties among the actors that are the number of positions in campaigns they have in common when either contributed.  Figure 14.7 shows part of the output of Network>Roles & Positions>Automorphic>MaxSim.

Figure 14.7.  Approximate automorphic equivalence of California political donors (truncated)

This small part of a large piece of output (there are 100 donors in the network) shows that a number of non-Indian casinos and race-tracks cluster together, and separately from some other donors who are primarily concerned with education and ecological issues.

The identification of approximate equivalence classes in valued data can be helpful in locating groups of actors who have a similar location in the structure of the graph as a whole.  By emphasizing distance profiles, however, it is possible to finds classes of actors that include nodes that are quite distant from one another, but at a similar distance to all the other actors.  That is, actors that have similar positions in the network as a whole.

table of contents

The kind of equivalence expressed by the notion of automorphism falls between structural and regular equivalence, in a sense. Structural equivalence means that individual actors can be substituted one for another. Automorphic equivalence means that sub-structures of graphs can can be substituted for one another. As we will see next, regular equivalence goes further still, and seeks to deal with classes or types of actors--where each member of any class has similar relations with some member of each other.

The notion of structural equivalence corresponds well to analyses focusing on how individuals are embedded in networks -- or network positional analysis. The notion of regular equivalence focuses our attention on classes of actors, or "roles" rather than individuals or groups. Automorphic equivalence analysis falls between these two more conventional foci, and has not received as much attention in empirical research. Still, the search for multiple substitutable sub-structures in graphs (particularly in large and complicated ones) may reveal that the complexity of very large structures is more apparent than real; sometimes very large structures are decomposable (or partially so) into multiple similar smaller ones.