<figure><img src="image_1.png" /></figure>

HAL
open science

# Nodal statistics-based structural pattern detection for graph collections characterization

Lucrezia Carboni, Michel Dojat, Sophie Achard

<figure><img src="image_2.png" /></figure>

## To cite this version:

Lucrezia Carboni, Michel Dojat, Sophie Achard. Nodal statistics-based structural pattern detection for graph collections characterization. Conference of Complex System, Oct 2022, Palma de Mallorca, Spain. . [hal-03866319](https://hal.science/hal-03866319)

HAL Id: hal-03866319

https://hal.science/hal-03866319

Submitted on 22 Nov 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Nodal statistics-based structural pattern detection for graph collections characterization

Lucrezia Carboni¹,²
lucrezia.carboni@inria.fr
Michel Dojat¹, Sophie Achard²

¹ Univ. Grenoble Alpes, Inserm, U1216, Grenoble Institut Neurosciences, 38000, FR

² Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, FR

This work has been partially supported by MIAI@Grenoble Alpes (ANR 19-P3IA-003)

UGA
Université Grenoble Alpes

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

http://arxiv.org/abs/2210.01053

## Motivations

* Human consciousness states can be differentiated by nodal organization in brain functional connectivity networks [1]

* structural pattern definition

* extend node role discovery to graph collections [2, 3]

* graph collections comparison based on structural pattern

## Nodal statistics-based structural pattern on single graph

### Def. Nodal statistics based equivalence relation.

We consider undirected unweighted graph $G = (V, E)$ and refer to a nodal statistics $s: V \to s(V)$ any function of the adjacency matrix.

The equivalence relation $\sim_S$ associated with a nodal statistics $s$, on the nodes set $V$ of a graph is:

$$v \sim_S u \iff s(u) = s(v).$$

The equivalence relation associated with any collection of statistics $S = \{s_i\}_{i=1,...,n}$, is defined as:

$$a \sim_S b \iff a \sim_{S_1} b, a \sim_{S_2} b, \dots, a \sim_{S_n} b. \quad (1)$$

### Def. Structural Pattern. Its induced partition $P$ on $V$,

$$P_S = \frac{V}{\sim_S} = \{[a], \forall a \in V\} \quad (2)$$

defines the structural pattern of $G$ associated with the statistics collection $S$.

### Def. Node role. The class of equivalence

$[a] = \{b \in V | a \sim_S b \iff s(a) = s(b)\}$ corresponds to node role.

## Structural patterns for graph collections characterization

### Def. Correspondence structural pattern score.
Let $G, G'$ be two graphs having same vertices $V$ and let $S$ be a statistics collection whose associated partitions are $P_S, P'_{S}$ on $G, G'$ respectively. Given bijective mapping from $P_S, P'_{S}$ to an initial segment of the natural numbers as enumerations, let $c(v_i), c'(v_i)$ be the enumeration of the classes of $v_i$, the correspondence structural pattern score between $G, G'$ is defined as:

$$C(G, G') = \max_{\pi \in \Pi} \frac{1}{|V|} \sum_{i=1}^{|V|} \chi(\pi(c(v_i)) = c'(v_i)) \quad (3)$$

where $\Pi$ is the set of all coupling between the elements in $P_S$ and the elements in $P'_{S}$ and $\chi$ is the indicator function.

### Def. Nodal-percentage of participation.

Given a graphs collection $G = \{G_k = (V_k, E_k) \text{ s.t. } V_k = V\}$, and a statistics collection $S$ we count the percentage of participation of each node of $V$ in non-trivial classes:

$$\forall v \in V \quad PP_G^S(v) = PP_G(v) = \frac{|\{G_k \in G \text{ s.t. } \#[v]_{\sim_S}^G \neq 1\}|}{|G|} \quad (4)$$

with $[v]_{\sim_S}^G$ the class of $v$ in $G_k$ in the partition induced by $S$.

## References

[1] Sophie Achard et al. "Hubs of brain functional networks are radically reorganized in comatose patients". In: Proceedings of the National Academy of Sciences 109.50 (2012).

[2] Stephen P Borgatti and Martin G Everett. "Notions of position in social network analysis". In: Sociological methodology (1992).

[3] Guilherme Ferraz De Arruda et al. "Role of centrality for the identification of influential spreaders in complex networks". In: Physical Review E 90.3 (2014).

[4] David C Van Essen et al. "The Human Connectome Project: a data acquisition perspective". In: Neuroimage 62.4 (2012).

[5] Petra E Vértes et al. "Simple models of human brain functional networks". In: Proceedings of the National Academy of Sciences 109.15 (2012).

<figure><img src="image_7.png" /><figcaption>(b) COMPARISON AT GLOBAL LEVEL BASED ON GRAPH STRUCTURAL PATTERNS</figcaption></figure>

<figure><img src="image_8.png" /></figure>

$$\begin{gathered} C(G, G') = \frac{(1 + 2 + 6)}{11} = 0.81 \\ \text{the structural pattern is similar in the two graphs} \end{gathered}$$

<figure><img src="image_9.png" /><figcaption>(c) GRAPH CHARACTERIZATION AT NODAL LEVEL BASED ON NODE PARTICIPATION</figcaption></figure>

- nodes A-I share their roles with other nodes in both graphs
- node L has a specific role in the two graphs
- role of node M depends on graph instance

## Correspondence structural pattern score differentiates models

<figure><img src="image_10.png" /></figure>

(Left) WS: Watt-Strogatz model, ER: Erdős-Rényi model, HCP: Human Connectome Project real networks [4]; (Right) Brain inspired models.[5] DSP: Degree sequence preserving model; EPA: Economical preferential attachment model; EC: Economical clustering model.

## Nodal-percentage of participation captures brain homotopy

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

The symmetry in real data and brain models reveals the expected hemisphere similarity in the participation of analogue regions.

## Conclusion

New mathematical method for exploration and characterization of **network collections**.

New way to **combine** many graph **nodal** statistics and to associated relative **structural patterns**.

Correspondence structural pattern score to **compare graphs at global level** based on their structural pattern similarity.

Nodal-percentage of participation for nodal level characterization.

Validation on generative models and real clinical data.