Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

14: Automorphic Equivalence


\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

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.

  • 14.1: Defining automorphic equivalence
    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.
  • 14.2: Uses of the Concept
    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.
  • 14.3: Finding Equivalence Sets
    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.
  • 14.S: Automorphic Equivalence (Summary)
    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 other members.