These functions calculate how regularly equivalent each pair of nodes is,
returning a similarity matrix that node_in_regular() then clusters.
regularity_rolesim() calculates RoleSim similarity.
regularity_rege() calculates REGE similarity.
Both are recursive: two nodes are similar to the extent that their alters are similar, which is the defining property of regular equivalence. They differ in how they pair up two nodes' alters.
regularity_rolesim(.data, decay = 0.15, beta = NULL)
regularity_rege(.data, iterations = 3)A network object of class stocnet, igraph, tbl_graph, network, or similar.
Internally any of these will be coerced to an efficient implementation.
For more information on possible coercions, see e.g. manynet::as_stocnet().
A proportion between 0 and 1 giving how much of a contribution
survives each additional step of distance or walk length.
Lower values discount more steeply, so that only nearby others count;
higher values discount less, so that longer walks continue to contribute.
The measures that take a decay differ in what they discount and in what
value leaves the measure in its most familiar form,
so each documents its own default.
Deprecated; use decay instead.
Integer number of iterations.
By default 3 for regularity_rege(); regularity_rolesim() iterates to convergence.
A square similarity matrix with one row and column per node.
RoleSim pairs up two nodes' alters by finding the maximal matching
between them, that is, the one-to-one pairing that maximises total
similarity, and then averages over it:
$$s(u,v) = (1-\delta) \frac{\sum_{(x,y) \in M} s(x,y)}{|N(u)| + |N(v)| - |M|} + \delta$$
where \(M\) is that matching and \(\delta\) is decay,
which RoleSim calls \(\beta\); by default 0.15.
Because each alter can be used only once, two nodes are similar only if
their neighbourhoods can be lined up as wholes.
RoleSim satisfies the automorphic confirmation property, meaning that automorphically equivalent nodes always score 1, and it is a metric. It converges to a unique solution regardless of where it starts, so the result does not depend on initialisation.
REGE instead pairs each alter with its best counterpart, allowing the same alter to be used more than once: $$s(u,v) = \frac{\sum_{x \in N(u)} \max_{y \in N(v)} s(x,y) + \sum_{y \in N(v)} \max_{x \in N(u)} s(x,y)}{|N(u)| + |N(v)|}$$
Matching with replacement makes REGE more permissive than RoleSim: a node with many alters can be judged similar to one with few, if those few resemble all of the many. Which behaviour is wanted depends on whether having more alters of a kind is itself part of the role.
REGE is the algorithm UCINET implements, so use it when comparing results against that software. Unlike RoleSim it has no convergence guarantee and is sensitive to the number of iterations, so this is fixed rather than run to convergence.
Note that REGE is defined for valued networks, and weights each matched
pair by how similar the two ties' strengths are.
On an unweighted, connected network it is degenerate: since every node has
an alter that matches every other node's alter perfectly, all nodes come
out maximally equivalent, which is the correct but uninformative answer
that the maximal regular equivalence of a connected graph is a single
class. Use regularity_rolesim() for unweighted networks.
Jin, Ruoming, Victor E. Lee, and Hui Hong. 2011. "Axiomatic ranking of network role similarity". Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining: 922-930. doi:10.1145/2020408.2020561
White, Douglas R., and Karl P. Reitz. 1983. "Graph and semigroup homomorphisms on networks of relations". Social Networks 5(2): 193-234. doi:10.1016/0378-8733(83)90025-4
Other methods:
method_coreness