Role extraction for digraphs via neighborhood pattern similarity

Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)

Authors

Date

2022-11

Department

Department of Mathematics and Systems Analysis

Major/Subject

Mcode

Degree programme

Language

en

Pages

11
1-11

Series

Physical Review E, Volume 106, issue 5

Abstract

We analyze the recovery of different roles in a network modeled by a directed graph, based on the so-called Neighborhood Pattern Similarity approach. Our analysis uses results from random matrix theory to show that, when assuming that the graph is generated as a particular stochastic block model with Bernoulli probability distributions for the different blocks, then the recovery is asymptotically correct when the graph has a sufficiently large dimension. Under these assumptions there is a sufficient gap between the dominant and dominated eigenvalues of the similarity matrix, which guarantees the asymptotic correct identification of the number of different roles. We also comment on the connections with the literature on stochastic block models, including the case of probabilities of order log(n)/n where n is the graph size. We provide numerical experiments to assess the effectiveness of the method when applied to practical networks of finite size.

Description

Funding Information: The authors thank the anonymous reviewers for useful comments. G.B. and V.N. are supported by an Academy of Finland grant (Suomen Akatemian päätös 331240). G.B. thanks the Alfred Kordelinin säätiö for the financial support under Grant No. 210122. P.V.D. is supported by an Aalto Science Institute Visitor Programme. Publisher Copyright: © 2022 American Physical Society.

Keywords

Other note

DOI

10.1103/PhysRevE.106.054301

Citation

Barbarino, G, Noferini, V & Van Dooren, P 2022, ' Role extraction for digraphs via neighborhood pattern similarity ', Physical Review E, vol. 106, no. 5, 054301, pp. 1-11 . https://doi.org/10.1103/PhysRevE.106.054301

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202212146913

Collections

[article-cris] Perustieteiden korkeakoulu / SCI