AR - 04 - Partizionamento in Comunità II

Ricordiamo che il problema 3-SAT prende in input una formula booleana in forma 3-CNF, ovvero formata da una congiunzione di clausole in cui ciascuna clausola è una disgiunzione di letterali, e si chiede se esiste o meno una assegnazione di verità che soddisfa la formula.

Volendo formalizzare, sia \(I = \langle f, X \rangle\) una istanza di 3-SAT, con \(X = \{x_1, x_2, ..., x_n\}\) insieme delle variabili e \(f = C_1 \land ... \land C_2\) funzione booleana in 3-CNF, con \(C_i = ( l_{i,1} \lor l_{i, 2} \lor l_{i, 3})\) clausola di letterali. In altre parole,

\[f = (l_{1, 1} \lor l_{1, 2} \lor l_{1, 3}) \land (l_{2, 1} \lor l_{2, 2} \lor l_{2, 3}) \land ... \land (l_{m, 1} \lor l_{m, 2} \lor l_{m, 3})\]

L'idea alla base della riduzione è quella di utilizzare la formula \(f\) per costruire un grafo. Il grafo sarà costruito in modo tale da poter essere partizionato in due (strong)-web communities nel caso in cui la formula sia soddisfacibile. A ciascuna partizione è poi associato un valore di verità (True o False).

Andiamo quindi a descrivere il modo in cui costruiamo il grafo a partire da \(f\).

Il metodo riportato a seguire è stato scoperto da Girvan e Newman.

Si inizia definendo il seguente termine

\[\forall s \in V: \,\,\, b_s(u, v) := \sum_{t \in V \setminus \{s\}} \frac{\sigma_{s,t}(u, v)}{\sigma_{s, t}}\]

Così facendo, una volta che sappiamo calcolare \(b_s(u, v)\) per ogni \(s \in V\), possiamo anche calcolare la betweenness tra \(u\) e \(v\) nel seguente modo

\[b(u, v) = \frac{1}{2} \sum_{s \in V} b_s(u, v)\]

L'algoritmo che calcola \(b_s(u, v)\) dopo aver fissato \(s \in V\) procede in tre passi:

• 1 - BFS su \(s\)

  Il primo passo consiste nell'eseguire una visita BFS (Breadth First Search) partendo dal nodo \(s\) sul grafo \(G\) per ottenere l'albero di visita \(T_s\).

• 2 - Calcolo \(\sigma_{s, u}\) per ogni \(u \in V\)

  Siano \(V_1, V2, ..., V_d\) i sottoinsiemi di \(V\) in base alla loro distanza da \(s\), dove con \(d\) indichiamo l'altezza dell'albero \(T_s\) calcolato prima. Notiamo che questi sottoinsiemi sono facilmente costruibili a partire dall'albero \(T_s\).

  Il secondo passo consiste nel calcolare il valore di \(\sigma_{s, u}\) per ogni \(u \in V\) nel seguente modo:

  • \(\forall u \in V_1: \sigma_{s, u} = 1\)

  • \(\forall u \in V_i: \sigma_{s, u} = \sum\limits_{\substack{v \in V_{i-1}:\\ (v, u) \in E}} \,\, \sigma_{s, v}\)

• 3: Procedimento bottom-up

  In questo passo simuliamo l'invio di una unità di informazione dal nodo \(s\) a tutti i nodi della rete. Definiamo quindi i seguenti termini:

  • \(\forall v \in V: \,\, f_s^v\) indica il flusso da \(s\) a \(v\).

  • \(\forall (u, v) \in E: \,\, f_s(u, v)\) indica il flusso da \(s\) passante per l'arco \((u, v)\).

  Notiamo che i nodi \(t\) appartenenti all'ultimo livello ricevono solamente \(1\) unità di informazione. Invece, Per quanto riguarda gli archi entranti nell'ultimo livello, ovvero della forma \((v, t)\) con \(v \in V_{d-1}\), abbiamo che ciascun arco poterà una frazione del flusso che deve arrivare a \(t\). In particolare quindi l'arco \((v, t)\) porterà la frazione \(\sigma_{s, v} / \sigma_{s, t}\) di flusso, in quanto tale frazione rappresenta proprio la frazione degli shortest paths che vanno da \(s\) a \(t\) e che passano per \(v\). Inizialmente troviamo quindi la seguente situazione per il caso base:

  \[\begin{cases} \forall t \in V_d&: f_s^t = 1 \\ \forall v \in V_{d-1}, \forall t \in V_d&: f_s(v, t) = 1 \cdot \frac{\sigma_{s,v}}{\sigma_{s,t}} \\ \end{cases}\]

  Supponiamo adesso di aver calcolato sia il valore del flusso \(f_s^t\) per ogni nodo \(t \in V_{i+1}\) e sia il flusso entrante su ogni arco che collega il livello \(V_i\) al livello \(V_{i+1}\). Notiamo che con questa conoscenza siamo anche in grado di calcolare il flusso su ogni nodo \(u \in V_i\) e il flusso su ogni arco che collega \(V_{i-1}\) a \(V_{i}\). Infatti, per quanto riguarda il flusso passante per i nodi, abbiamo che

  \[\forall u \in V_{i}: \,\,\,\, f_s^u = 1 \,\, + \sum\limits_{\substack{v \in V_i+1: \\ (u, v) \in E}} f_s(u, v)\]

  Per quanto riguarda il flusso passante per gli archi troviamo che

  \[\forall (u, v) \in E: u \in V_{i-1}, v \in V_{i}, \,\,\,\,\,\, f_s(u, v) = f_s^v \cdot \frac{\sigma_{s,u}}{\sigma_{s,v}}\]

Arrivati a questo punto ci basta notare che

\[f_s(u, v) = b_s(u, v)\]

Quindi, al variare di \(s\), tramite questa simulazione di invio di informazioni a partire da \(s\) siamo in grado di calcolare i vari \(b_s(u, v)\), che possono poi essere utilizzati a loro volta per calcolare la edge-between di ogni arco.

Notiamo che tanto più è elevata la betweenness di un arco e tanto più è elevata l'informazione passante su quell'arco. Notiamo poi che tanta più informazione passa in un arco e tanto più quell'arco si avvicina ad essere un bridge o un local-bridge.

L'idea che hanno avuto Girvan e Newmann è la seguente: si calcola la betweenness per ogni arco e si comincia a togliere dal grafo gli archi con la più alta betweenness finché il grafo si sconnette. I due pezzi del grafo rimanenti saranno quindi le nostre due comunità ricercate.

A seguire riportiamo un frammento del codice python presente nel file edge_betweenness.py, in cui è possibile trovare anche una implementazione in python del calcolo della edge_betwenness.

     # partition graph using girvan newman betwenness centrality measure.
     def girvan_newman(G):
         connected = is_graph_connected(G)

         # graph is already disconnected, no need to partition it    
         if not connected:
             return G
        
         # iterate over all edges of the graph to compute the
         # edge_betweenness
         betweenness_value = {}
         for u in G:
             for v in G[u]:
                 betweenness_value[(u, v)] = edge_betwenness(G, u, v)

         # start removing edges with highest edge-betweenness until graph
         # disconnects
         while connected:
             # find edge with max betweenness value
             max_edge = max(betweenness_value, key=betweenness_value.get)
             u, v = max_edge
        
             # remove edge from graph
             G[u].remove(v)
             G[v].remove(u)
        
             # remove edge from betweennes dictionary
             betweenness_value.pop(max_edge, None)
        
             # check if graph is still connected
             connected = is_graph_connected(G)

         return G