Social Networks Research

Connecting People & Communities Detection

Try Detection Algorithm on your DATA

Acces to COMMET API :

community evaluation and transformation

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.