k-cores di ensembles di reti finite

The k-core is the smallest sub-network obtainable eliminating, step by step, all nodes with degrees less than k. The number of loops of a given size in a random network increases at most as log N , while for uncorrelated random networks specified via a degree distribution it is constant. Therefore, for networks with significant nodes (N ∼ 10^4 ), loops can be neglected and is possible to implement a tree approximation for the network that is convenient to determine the k-cores. We compare the results for k-cores’ networks, obtained with this approximation, with those of k-cores’ networks that have a finite size (N ≤ 10^4 ) and which have degree sequences extracted from suitable statistical ensembles created using the expected degree distribution for N → ∞ and a specific number of nodes. Made those extractions, we implement two different methods to generate networks from these degree sequences and we calculate the average value of maximum k ad a function of nodes for sets of networks with different degree distributions. The aim is to understand for which statistical ensembles and generative methods it is possible to refer to the estimates of the tree approximation for the k-core of networks that have a given expected degree distribution for N → ∞.

Il k-core è la più piccola sottorete ottenibile eliminando, passo dopo passo, tutti i nodi con gradi inferiori a k. Il numero di loop di una rete casuale aumenta al massimo come log N , mentre per reti casuali non correlate ,con definita distribuzione di grado, è costante. Pertanto, per reti con nodi significativi (N ∼ 10^4), i loop possono essere trascurati ed è possibile implementare un'approssimazione ad albero per la rete, che è conveniente nel determinare i k-cores. Confrontiamo i risultati per le reti di k-core, ottenuti con questa approssimazione, con quelli di reti che hanno una dimensione finita (N ≤ 10^4) e che hanno sequenze di grado estratte da opportuni insiemi statistici creati utilizzando la distribuzione dei gradi attesa a N → ∞ e un numero specifico di nodi. Fatte queste estrazioni, implementiamo due diversi metodi da cui generare le reti da queste sequenze e calcoliamo il valore medio del massimo k in funzione di N per insiemi con diverse distribuzioni di grado. Lo scopo è capire per quali insiemi statistici e metodi generativi sia possibile fare riferimento alle stime dell'approssimazione ad albero per i k-cores di reti che hanno una data distribuzione dei gradi attesa per N → ∞.