# Map equation centrality: community-aware centrality based on the map equation – Applied Network Science

Aug 16, 2022

### Generalisation for sets of nodes

We generalise map equation centrality and derive the expression in Eq. 12 that can be used to calculate the combined centrality for sets of nodes U. We follow the same approach as before, that is, we first derive an expression for the expected per-step codelength when silencing all nodes in U while using the old coding scheme; then we derive an expression for for the expected per-step codelength when designing a new coding scheme that does not assign codewords to nodes in U to start with.

Let (G = left( V, E, delta right)) be a network with nodes V, links E, weights (delta), (U subseteq V) be a set of nodes, and (p_U = sum _{u in U} p_u) be the visit rate sum of nodes in U. Further, for a module ({mathsf {m}}), let (p_{{mathsf {m}} cap U} = sum _{u in {mathsf {m}} cap U} p_u) be the visit rate sum of nodes that are members in ({mathsf {m}}) and in U, and let (P_{{mathsf {m}} cap U} = left{ p_u ,|, u in {mathsf {m}} cap U right}) be their set of visit rates.

We begin with the one-level partition ({mathsf {M}}_1) and obtain the expected per-step codelength for describing a random walk with nodes in U silenced while using the old coding scheme. Removing the silenced nodes from the summation in Eq. 1, we get

begin{aligned} L^Uleft( G, {mathsf {M}}_1right) = – sum _{v in V setminus U} p_v log _2 p_v. end{aligned}

(13)

We obtain the codelength for a new coding scheme that does not assign codewords to nodes in U by re-normalising the visit rates for the remaining nodes with (1-p_U,)

begin{aligned} L^{U*}left( G, {mathsf {M}}_1right) = – sum _{v in V setminus U} p_v log _2 frac{p_v}{1 – p_U}. end{aligned}

(14)

The difference between Eqs. 13 and 14 is the joint map equation centrality score of the nodes in U under ({mathsf {M}}_1,)

begin{aligned} uplambda left( G, {mathsf {M}}_1, Uright)&= L^Uleft( G, {mathsf {M}}_1right) – L^{U*}left( G, {mathsf {M}}_1right) nonumber \&= – left( 1-p_Uright) log _2 left( 1 – p_Uright) . end{aligned}

(15)

For two-level partitions, we begin by rewriting the map equation (Eq. 2) to distinguish explicitly between modules that have an overlap with U and those that do not,

(16)

The codelength for describing a random walk in partition ({mathsf {M}}) with nodes in U silenced when using the old coding scheme is

(17)

With a new code that does not assign codewords to nodes in U and that normalises accordingly, the codelength is

(18)

The difference between Eqs. 17 and 18 is the joint map equation centrality of the nodes in U under ({mathsf {M}},)

begin{aligned}uplambda left(G, {mathsf{M}}, Uright) &= L^Uleft( G,{mathsf {M}}right) – L^{U*}left(G,{mathsf{M}}right) \&= – sum limits _{{{mathsf {m}} in {mathsf {M}}, {mathsf {m}} cap U ne emptyset }} left( p_{mathsf {m}} – p_{{mathsf {m}} cap U}right) log _2 frac{{p_{mathsf{m}} – p_{{mathsf {m}} cap U}}}{{p_{mathsf{m}}}}. end{aligned}

(19)

### Descriptions of linear threshold model results

In the Facebook friends network, initially all measures perform similarly well. Modularity vitality, community hub-bridge, and community-based centrality outperform map equation centrality between (x = 0.02) and 0.04; beyond (x = 0.04), map equation centrality performs best, followed by betweenness centrality, degree centrality, modularity vitality, community-based centrality, and community hub-bridge (Fig. 5a).

In the Copenhagen network, up to (x = 0.03), all scores perform equally well, between (x = 0.03) and (x = 0.05), community hub-bridge and community-based centrality perform slightly better than map equation centrality and modularity vitality. Beyond (x = 0.05) and up to (x = 0.13), map equation centrality performs best; for (x ge 0.13), modularity vitality performs best and reaches an activation size of 1 (Fig. 5b).

In the Uni email network, initially, community hub-bridge and community-based centrality slightly outperform the other measures. Then, at (x = 0.06), map equation centrality and degree centrality reach an activation size of nearly 1, followed by betweenness centrality at (x = 0.07), modularity vitality at (x = 0.09), community-based centrality at (x = 0.12), and community hub-bridge at (x = 0.15) (Fig. 5c).

In the Polblogs network, community-based centrality, community hub-bridge, and betweenness centrality perform best, followed by degree centrality, modularity vitality, and finally map equation centrality (Fig. 5d).

In the Interactome yeast network, map equation centrality performs best, followed by degree centrality, and the remaining measures which have similar performance in this case (Fig. 5e).

In the Ego Facebook network, all four measures have similar performance up to (x = 0.05), beyond which map equation centrality dominates, followed by betweenness centrality, community-based centrality and community hub-bridge, and modularity vitality (Fig. 5f).

In the Power network, map equation centrality performs best, followed by degree centrality, modularity vitality, community-based centrality, community hub-bridge, and betweenness centrality (Fig. 5g).

In the Facebook organizations network, community hub-bridge and community-based centrality perform best up to (x = 0.05). Beyond that, map equation centrality performs best; modularity vitality, betweenness centrality, degree centrality, and community-based centrality have similar performance, and community hub-bridge performs weakest with some distance. From (x = 0.14), betweenness centrality performs slightly better than map equation centrality (Fig. 5h).

In the Physics collaborations map equation centrality outperforms the other measures over the whole tested range, followed by betweenness centrality, degree centrality, modularity vitality, and community hub-bridge and community-based centrality (Fig. 5i).

In the Google network, betweenness centrality performs best while map equation centrality performs weakest in this scenario. The remaining measures have similar performance, but none clearly wins against the others (Fig. 5j).

In the PGP network, betweenness centrality outperforms the remaining measures, followed by map equation centrality, degree centrality, modularity vitality, community hub-bridge, and community-based centrality (Fig. 5k).

Finally, in the Facebook wall network, initially, map equation centrality based on unrecorded link teleportation and degree centrality perform best, followed by community-based centrality, community hub-bridge, betweenness centrality, and modularity vitality. Beyond (x = 0.04), map map equation centrality with recorded node teleporation and betweenness centrality perform best, followed by modularity vitality, degree centrality, community hub-bridge, and community-based centrality (Fig. 5l).

### Descriptions of the SIR model results

In the Facebook friends network, map equation centrality, degree centrality, community hub-bridge, and community-based centrality are nearly tied with an imprecision up to approximately 0.05, identifying the top spreaders accurately. Modularity vitality initially performs similarly well, but achieves imprecision values between around 0.2 and 0.3 beyond (x = 0.05) (Fig. 6a).

In the Copenhagen network, map equation centrality and degree centrality outperform the other measures. Community-based centrality performs slightly worse than map equation centrality, followed by community hub-bridge, betweenness centrality, and then modularity vitality (Fig. 6b).

In the Uni email network, map equation centrality and degree centrality outperform the other measures across the tested range of x-values, followed by community-based centrality, betweenness centrality, and modularity vitality and community hub-bridge, the latter two performing similarly in this scenario (Fig. 6c).

In the Polblogs network, community-based centrality and community hub-bridge perform best, followed by degree and betweenness centrality, modularity vitality, and finally map equation centrality (Fig. 6d).

In the Interactome yeast network, all measures perform similarly well, while community-based centrality and map equation centrality slightly outperform the rest (Fig. 6e).

In the Ego Facebook network, map equation centrality and degree centrality again outperform the other measures. Initially and up to (x approx 0.08), modularity vitality, community hub-bridge, and community-based centrality show similar performance. Beyond (x approx 0.08), modularity vitality’s performance remains stable at an imprecision of around 0.2 while community hub-bridge and community-based centrality improve and perform as well as map equation centrality at (x approx 0.2). Map equation centrality based on recorded node teleportation and betweenness centrality perform substantially worse than the other measures in this scenario with imprecision values roughly between 0.9 down to 0.5 (Fig. 6f).

In the Power network, community-based centrality performs best, followed by map equation centrality, community hub-bridge, degree centrality, modularity vitality, and finally betweenness centrality (Fig. 6g).

In the Facebook organizations network, map equation centrality and degree centrality outperform the other measures with a stable imprecision around 0.1. Modularity vitality performs second-best, with increasing imprecision as x increases, followed by betweenness centrality, community-based centrality, and community hub-bridge (Fig. 6h).

In the Physics collaborations network, modularity vitality initially performs best, but with slightly decreasing performance as x increases. Map equation centrality, degree centrality, community hub-bridge, and community-based centrality initially perform similarly, all with an imprecision of around 0.35, but outperform modularity vitality beyond (x approx 0.05), with community-based centrality performing best (Fig. 6i).

In the Google network, up to (x = 0.03), community hub-bride performs best. Beyond that, community-based centrality performs best, followed by degree centrality, community hub-bridge, modularity vitality, map equation centrality, and finally betweenness centrality (Fig. 6j).

In the PGP network, community-based centrality outperforms the other measures, followed by degree centrality. Community hub-bridge performs third-best, followed by map equation centrality, betweenness centrality, and modularity vitality. In this scenario, node teleportation-based map equation centrality performs nearly identical to modularity vitality. Beyond (x approx 0.05), community hub-bridge and map equation centrality are nearly tied (Fig. 6k).

Finally, in the Facebook wall network, community-based centrality outperforms the other measures, followed by degree centrality, community hub-bridge, map equation centrality, modularity vitality, and betweenness centrality. Here, map equation centrality when using recorded node teleportation performs considerably worse compared to unrecorded link teleportation (Fig. 6l).

### Further results for the linear threshold model

Further results for the linear threshold model with thresholds (t^{prime } = 0.4) and (t^{prime prime } = 0.6) are shown in Figs. 9 and 10, respectively.