View abstract

Session III.1 - Numerical Linear Algebra

Wednesday, June 21, 16:30 ~ 17:00

Role extraction for digraphs via neighbourhood pattern similarity

Giovanni Barbarino

aalto university, Finland   -   This email address is being protected from spambots. You need JavaScript enabled to view it. document.getElementById('cloak7d63c498cb97506f37e24770c8573f92').innerHTML = ''; var prefix = '&#109;a' + 'i&#108;' + '&#116;o'; var path = 'hr' + 'ef' + '='; var addy7d63c498cb97506f37e24770c8573f92 = 'g&#105;&#111;v&#97;nn&#105;.b&#97;rb&#97;r&#105;n&#111;' + '&#64;'; addy7d63c498cb97506f37e24770c8573f92 = addy7d63c498cb97506f37e24770c8573f92 + '&#97;&#97;lt&#111;' + '&#46;' + 'f&#105;'; var addy_text7d63c498cb97506f37e24770c8573f92 = 'g&#105;&#111;v&#97;nn&#105;.b&#97;rb&#97;r&#105;n&#111;' + '&#64;' + '&#97;&#97;lt&#111;' + '&#46;' + 'f&#105;';document.getElementById('cloak7d63c498cb97506f37e24770c8573f92').innerHTML += '<a ' + path + '\'' + prefix + ':' + addy7d63c498cb97506f37e24770c8573f92 + '\'>'+addy_text7d63c498cb97506f37e24770c8573f92+'<\/a>';

The analysis of large graphs frequently assumes that there is an underlying structure in the graph that allows us to represent it in a simpler manner. A typical example of this is the detection of communities, which groups together nodes with similar connectivity properties. Yet, many graph structures cannot be modelled using communities: for example, arrowhead and tree graph structures, which appear in overlapping communities, human protein-protein interaction networks, and food and web networks. These more general types of network structures can be modelled as role structures, and the process of finding them is called the role extraction problem or block modelling. In this presentation, we show that a particular spectral method, using the so-called Neighbourhood Pattern Similarity matrices, allows us to recover asymptotically the block structure of a general directed graph with a stochastic block model (SBM) structure. In fact, the increasing gap between the dominant and dominated eigenvalues of the similarity matrix guarantees the asymptotic correct identification of the number of different roles and enables us to compute an asymptotic estimation of the total misclassification error. This is in particular one of the few existing results of correctness for the spectral clustering algorithm applied to directed graph with a SBM structure.

Joint work with Vanni Noferini (Aalto University, Finland) and Paul Van Dooren (Université catholique de Louvain, Belgium).