logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-01042023-135508


Tipo di tesi
Tesi di laurea magistrale
Autore
ZITO, MORENO
URN
etd-01042023-135508
Titolo
Edge Centrality Measures for Hypergraphs
Dipartimento
MATEMATICA
Corso di studi
MATEMATICA
Relatori
relatore Prof.ssa Meini, Beatrice
Parole chiave
  • ipergrafi
  • hypergraph
  • misure di centralità
  • centrality measure
  • autovettori
  • eigenvector
  • closeness
  • betweenness
  • entropia di Von Neumann
  • Von Neumann entropy
  • funzioni multi-omogenee
  • multi-homogeneus functions
Data inizio appello
27/01/2023
Consultabilità
Non consultabile
Data di rilascio
27/01/2093
Riassunto
Graph centrality measures, for both nodes and edges, play a major role when studying the global structure of a graph since they generate a ranking on the costituents of such graph. In the following, we first recall the well known betweenness, closeness and eigenvector centrality measure for nodes and edges as well as two more recent centrality measures for edges, which
are nearest-neighbor and Von Neumann entropy centrality measure. Then, we generalize these centrality measures to the case of hypergraphs, which are a generalization of graphs whose edges can contain an arbitrary number of vertices. In particular, in order to achieve these generalizations we define the clique-expansion graph of a hypergraph and we state a Perron-Frobenius theorem for multi-homogeneus functions. Finally, by using various empirical
network models and real data set, we show how key network constituents are highlighted by the centrality models previously dened.

Le misure di centralità per nodi e archi di un grafo ordinano queste costituenti secondo varie definizioni di importanza, pertanto, svolgono un ruolo fondamentale nello studio della struttura globale di un grafo. Nel seguito, inizialmente, richiameremo le definizioni classiche sui grafi di centralità intermediaria (betweenness), di vicinanza (closeness) e tramite autovettori (eigenvector), inoltre, definiremo due recenti misure di centralità per archi: la prima che sfrutta l’entropia di Von Neumann, la seconda che misura la forza di un arco rispetto a quella dei suoi vicini. Successivamente, generalizzeremo queste misure di centralità al caso di ipergrafi, cioè un’estensione della definizione di grafo in cui ogni arco può contenere un numero arbitrario di nodi. Infine, applicheremo queste misure di centralità a network empirici al fine di studiare il loro comportamento e di identificare le costituenti più importanti in suddetti network.
File