Methods for calculating regularity

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)

Arguments

.data

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().

decay

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.

beta

Deprecated; use decay instead.

iterations

Integer number of iterations. By default 3 for regularity_rege(); regularity_rolesim() iterates to convergence.

Value

A square similarity matrix with one row and column per node.

Cognitive social structures

A cognitive social structure records each node's report of the ties in the whole network, in a by column that names who reported each tie. Counting every report as a tie of its own would count each tie once for every perceiver who reports it. So the functions here first combine the reports into the locally aggregated structure of Krackhardt (1987), with the intersection rule: a tie exists if both of its ends report it, and a message says so. A tie that names no reporter is kept as it is.

A tie-level function still returns one value for each report, so that the result can be added back to the network it was given. Each report takes the value of the tie that it reports. A report of a tie that is not in the aggregated structure takes NA, or FALSE for a mark. tie_is_random() is the exception, and draws among the reports.

To combine the reports in a different way, do this before the function, e.g. with manynet::to_aggregated(over = "by").

Krackhardt, David. 1987. "Cognitive social structures". Social Networks 9(2): 109-134. doi:10.1016/0378-8733(87)90009-8

RoleSim

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

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.

References

On RoleSim

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

On REGE

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

See also

Other methods: method_coreness