Try Detection Algorithm on your DATA

Legitimacy function

It is possible to add more meaning in order to decide which community a given node should join. The legitimacy function serves to measure the node involvement in a community and other results to show community overlapping. The more strongly a node is linked to other nodes in a community, the greater its legitimacy to belong to the particular community. The legitimacy function can thus be formalized as follows:

$$L(u_{i}\in c)=\frac{\sum{}_{j}A_{ij}\delta(c_{j})}{|\{v\in c\}|}$$

where $$c$$ is a community, and $$\delta$$ is Kronecker delta symbol.

Reassignment Modularity function

Reassigning node $$w$$ from $$C_{1}$$ to $$C_{2}$$ either increases or decreases the modularity. Such a change is referred to as Reassignment Modularity. Let $$w$$ be a node,  if $$w$$ is withdrawn from $$C_{1}$$ and reassigned to $$C_{2}$$, then we can define:

$$RM_{w:C_{1}\rightarrow C_{2}} =Q_{w\in C_{2}}^{B}-Q_{w\in C_{1}}^{B}$$

• $$Q^{B}$$ is the modularity value in: $$Q^{B}=\sum_{c}[\frac{|e_{c}|}{m}-(\frac{(d_{u|c}+d_{v|c})}{2\times m})^{2}]$$,
• $$l_{w|i}=l_{w,w’|w’\in C_{i}}$$ be the number of edges between a node $$w$$ and all other nodes $$w’$$ where $$w’\in C_{i}$$,
• $$d_{w}$$ be the degree of $$w$$,
• $$|e_{i}|$$ the number of edges in $$C_{i}$$,
• $$d_{C_{i}} = \sum d_{u|u\in c_{i}}$$.

We consider that the node $$w$$ which belongs to $$C_{1}$$ is bound to be withdrawn from this community and assigned to the community $$C_{2}$$. $$Q_{w\in C_{2}}^{B}$$ is $$Q_{w\in C_{1}}^{B}$$ with correction after $$w$$ is reassigned. Then

$$Q_{w\in C_{1}}^{B} = [\frac{1}{m}|e_{1}|-\frac{(d_{C_{1}})^{2}}{(2m)^{2}}+\frac{1}{m}|e_{2}|-(\frac{(d_{C_{2}})^{2}}{(2m)^{2}})]+ K_{others}$$

where $$K_{others}$$ is the contribution to modularity brought by other communities than $$C_{1}$$ and $$C_{2}$$. This last value does not change when reassigning a node from $$C_{1}$$ to $$C_{2}$$. And after simplification we obtain the Reassignment Modularity function :

$$RM_{w:C_{1}\rightarrow C_{2}}=\frac{1}{m}(l_{w|2}-l_{w|1})-\frac{1}{2m{}^{2}}[d_{w}^{2}+d_{w}(d_{C_{2}}-d_{C_{1}})]\label{eq:11-1}$$

Reassignment is a very interesting measure. It allows detection of nodes that are not properly assigned to a community. Since most community detection algorithms are greedy algorithms some nodes may not be in a stable situation. The $$RM$$ value reveals unstable nodes and the community to which they should be assigned.