## Persistent hubs in weighted graphs

### Who we are

Massimo Ferri1

Antonella Tavaglione1

Pietro Vertechi2

Lorenzo Zuffi1

### Outline

#### Persistence on weighted graphs

• (Classic) topological persistence
• Combinatorial persistence: Coherent sampling and property-based filters

#### Applications

• Hubs detection
• Dynamical hubs detection

### (Classic) topological persistence

#### Framework

$\mathbb{X}$ triangulable manifold, $f$ continuous. $\mathbb{X}_{i} = f^{-1}\left(\left(-\infty, a_i\right]\right)$ $$\mathbb{X}_{1} \subseteq \cdots \subseteq \mathbb{X}_{n} = \mathbb{X}$$

### (Classic) topological persistence

#### Weighted graphs ...

$$G = \left(V, E \right), \ \ f: E\rightarrow\mathbb{R}$$

### Combinatorial persistence

#### Questions:

How general can such a framework be?

### Combinatorial persistence

#### Natural pseudodistance

Let $(G, f), (G^\prime, f^\prime)$ be weighted graphs and $H$ the set of isomorphisms from $G$ to $G^\prime$.

The natural pseudodistance of $(G, f)$ and $(G^\prime, f^\prime)$ is

$$\delta\left(\left(G, f\right), \left(G', f'\right)\right) = \left\{ \begin{array}{l l} \infty & \mbox{if} \ \ \ H=\emptyset \\ \inf_{\phi\in H}\sup_{e\in E} \left|f\left(e\right) - f'\left(\phi\left(e\right)\right)\right| \ \ & \mbox{otherwise} \end{array} \right.$$

### Combinatorial persistence

#### Persistence functions

All functions $\lambda_{(G, f)}: \Delta^+ \to \mathbb{Z}$ are said to be persistence functions if

• $\lambda_{(G, f)}(u, v)$ is nondecreasing in $u$ and nonincreasing in $v$ ;
• for all $u_1, u_2, v_1, v_2 \in\mathbb{R}$ such that $u_1 \le u_2 < v_1 \le v_2$ the following inequality holds: $$\lambda_{(G, f)}(u_2, v_1) - \lambda_{(G, f)}(u_1, v_1) \ge \lambda_{(G, f)}(u_2, v_2) - \lambda_{(G, f)}(u_1, v_2)$$

### Combinatorial persistence

#### Stability

$\lambda_{(G, f)}$ is said to be stable if given an analogous pair $(G^\prime, f^\prime)$, an isomorphism $\psi:G\to G^\prime$ exists such that $$\sup_{e\in E} \left| f\left(e \right)-f^\prime\left(\psi\left(e\right)\right)\right|\le h$$ where $h>0$, then for all $(u, v)\in \Delta^+$ the inequality $$\lambda_{(G, f)}(u-h, v+h)\le \lambda_{\left(G^\prime, f^\prime\right)}(u, v)$$ holds.

### Combinatorial persistence

#### A note on stability...

For weighted graphs $\left(G, f\right), \left(G^\prime, f^\prime\right)$ as above, if $\lambda_{(G, f)}$ and $\lambda_{\left(G^\prime, f^\prime\right)}$ are stable then

$$d\left(D\left( f \right), D\left(f^\prime\right)\right) \le \delta\left(\left(G, f\right), \left(G^\prime, f^\prime\right)\right),$$ where $d$ is the bottleneck distance.

#### ... and a remark on universality

Is the inequality described above the best one that we can obtain from persistence diagrams?

### Combinatorial persistence

#### Coherent samplings

A coherent sampling $\mathcal{V}$ is the assignment to each graph $G$, where $G=\left(V, E\right)$ of a set $\mathcal{V}(G)$ of subsets of $V \cup E$, such that

• each $\mathcal{V}(G)$ is a finite (possibly empty) set of elements of $V\cup E$;
• if $G$ is a subgraph of $H$, then each element of $\mathcal{V}(G)$ is contained in exactly one element of $\mathcal{V}\left(H\right)$;

A coherent sampling is stable if $\psi:G\to G^\prime$ is an isomorphism, then $\mathcal{V}\left(G^\prime\right)=\psi\left(\mathcal{V}\left(G\right)\right)$.

For each inclusion $\iota: G \to H$ let $\Lambda(\iota)$ be the number of elements of $\mathcal{V}\left(H\right)$ containing at least one element of $\mathcal{V}\left(G\right)$.
For all filtering functions $f:E \to \mathbb{R}$, let $\lambda_{(G, f)}:\Delta^+ \to \mathbb{Z}$ be defined by $\lambda_{(G, f)}(u, v) = \Lambda(\iota_{(u, v)})$ where $\iota_{(u, v)}: G_u \to G_v$ is the inclusion homomorphism. Then the functions $\lambda_{(G, f)}$ are persistence functions. If the coherent sampling is stable, so are the persistence functions.

### Combinatorial persistence

#### Coherent samplings - Clique communities

The assignment $\mathcal{C}^k$, which maps each graph $G$ to the set of its $k$-clique communities, is a stable coherent sampling.

### Combinatorial persistence

#### Property-based filters

Let $\left(G,f\right)$ be a weighted graph, with $G=(V, E)$

$F: 2^{V\cup E} \to \{true, false\}$ a property.

We call $F$-set any set $A\subseteq V\cup E$ such that $F(A) = true$.

$A\subseteq V\cup E$ is an $F$-set at level $w$ if it is an $F$-set of the subgraph $G_w$.

### Combinatorial persistence

#### Property-based filters

We call $A\subseteq V\cup E$ a steady $F$-set $(u, v) \in \Delta^+$ if it is an $F$-set at all levels $w$ with $u\le w \le v$.

We call $A$ a ranging $F$-set at $(u, v)$ if there exist levels $w\le u$ and $w'\ge v$ at which it is an $F$-set.

Let $SF_{(G, f)}(u,v)$ be the set of s-$F$-sets at $(u, v)$ and let $RF_{(G, f)}(u,v)$ be the set of r-$F$-sets at $(u, v)$.

### Combinatorial persistence

#### Property-based filters

The functions $$\begin{array}{l l} \sigma:\Delta^+\rightarrow \mathbb{R}\\ (u,v)\mapsto \left|SF_{(G, f)}(u,v)\right| \end{array}$$ and $$\begin{array}{l l} \rho:\Delta^+\rightarrow \mathbb{R}\\ (u,v)\mapsto \left|RF_{(G, f)}(u,v)\right| \end{array}$$ are persistence functions.

### Combinatorial persistence

#### Hubs

A temporary hub (t-hub) at level $u$ is a vertex of $G_u\subseteq G$ whose degree is greater than the degree of its neighbors.

A steady hub (s-hub) at $(u, v)\in \Delta^+$ is a vertex which is a t-hub at all levels $w$ with $u\le w \le v$.

A ranging hub (r-hub) at $(u, v)\in \Delta^+$ is a vertex such that there exist levels $w \le u$ and $w^\prime\ge v$ at which it is a t-hub.

### Les Miserables

#### Characters co-occurence

Don't you see an interactive graph? Please reload the page (Ctrl+R or command+R on mac).

Ranging hubs

Ranging hubs

Ranging hubs

### Hubs in Game of Throne (books I-V)

#### Characters co-occurence

Don't you see an interactive graph? Please reload the page (Ctrl+R or command+R on mac).

### Time-varying hubs in Game of Thrones (books I-V)

#### Characters co-occurence

Don't you see an interactive graph? Please reload the page (Ctrl+R or command+R on mac).

### Conclusions

Persistence-based signatures of data can be generated without auxiliary topological constructions.

Coeherent samplings and property-based filters are general recipes to create persistence functions.

We are working on a categorical extension of the theory presented here for weighted graphs.


graph = pc.WeightedGraph(graph_structure)
graph.build_graph()
graph.build_filtered_subgraphs(weight_transform=opp,
sublevel=True)
graph.get_temporary_hubs_along_filtration()
graph.ranging_hubs_persistence()
graph.plot_ranging_persistence_diagram()

###### lorenzo.zuffi@studio.unibo.it

gitlab.com/mattia.bergomi/perscomb