Network decomposition into fixed points of degree peeling

James Abello (1) , François Queyroi (2)

1 DIMACS - Center for Discrete Mathematics and Theoretical Computer Science [Rutgers]
2 ComplexNetworks

Degree peeling is used to study complex networks. It is a decomposition of the network into vertex groups of increasing minimum degree. However, the peeling value of a vertex is non-local in this context since it relies on the number of connections the vertex has to groups above it. We explore a different way to decompose a network into edge layers such that the local peeling value of the vertices on each layer does not depend on their non-local connections with the other layers. This corresponds to the decomposition of a graph into subgraphs that are invariant with respect to degree peeling, i.e., they are fixed points. We introduce a general method to partition the edges of an arbitrary graph into fixed points of degree peeling called the iterative edge core decomposition. Information from this decomposition is used to formulate a novel notion of vertex diversity based on Shannon’s entropy. We illustrate the usefulness of this decomposition on a variety of social networks including weighted graphs. Our method can be used as a preprocessing step for community detection and graph visualization.

Mots clés: Influence ranking; Degree peeling; Graph decompositions; Fixed points

Domaines: Réseaux et télécommunications [cs.NI]

James Abello, François Queyroi. Network decomposition into fixed points of degree peeling. Social Network Analysis and Mining, 2014, 4 (1), pp.191. ⟨10.1007/s13278-014-0191-7⟩. ⟨hal-01103366⟩