Twin subgraphs and core-semiperiphery-periphery structures

Riaza Rodríguez, Ricardo (2018). Twin subgraphs and core-semiperiphery-periphery structures. "Complexity", v. 2018 ; pp. 1-17. ISSN 1076-2787.


Title: Twin subgraphs and core-semiperiphery-periphery structures
  • Riaza Rodríguez, Ricardo
Item Type: Article
Título de Revista/Publicación: Complexity
Date: 2018
ISSN: 1076-2787
Volume: 2018
Freetext Keywords: graph; network; twin; structural equivalence; core-periphery; core-semiperipheryperiphery
Faculty: E.T.S.I. Telecomunicación (UPM)
Department: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[thumbnail of INVE_MEM_2018_296598.pdf]
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (302kB) | Preview


A standard approach to reduce the complexity of very large networks is to group together sets of nodes into clusters according to some criterion which reflects certain structural properties of the network. Beyond the well-known modularity measures defining communities, there are criteria based on the existence of similar or identical connection patterns of a node or sets of nodes to the remainder of the network; this approach supports so-called positional analyses and the definition of certain structures in social, commercial and economic networks. A key notion in this context is that of structurally equivalent or twin nodes, displaying exactly the same connection pattern to the remainder of the network. The first goal of this paper is to extend this idea to subgraphs of arbitrary order of a given network, by means of the notions of T-twin and F-twin subgraphs. This research, which leads to graph-theoretic results of independent interest, is motivated by the need to provide a systematic approach to the analysis of core-semiperiphery-periphery (CSP) structures, a notion which is widely used in network theory but that somehow lacks a formal treatment in the literature. The goal is to provide an analytical framework accommodating and extending the idea that the unique (ideal) core-periphery (CP) structure is a 2-partitioned K2, a fact which is here understood to rely on the truetwin and false-twin notions for vertices already known in network theory. We provide a formal definition of such CSP structures in terms of core eccentricities and periphery degrees, with semiperiphery vertices acting as intermediaries between both. The Ttwin and F-twin notions then make it possible to reduce the large number of resulting structures by identifying isomorphic substructures which share the connection pattern to the remainder of the graph, paving the way for the decomposition and enumeration of CSP structures. We compute explicitly the resulting CSP structures up to order six. We illustrate the scope of our results by analyzing a subnetwork of the well-known network of metal manufactures trade arising from 1994 world trade statistics. As this example suggests, our approach can be naturally applied in complex network theory and seem to have many potential extensions, since the analytical properties of twin subgraphs and the structure of CSP and other partitioned graphs admit further study.

Funding Projects

Government of Spain

More information

Item ID: 54807
DC Identifier:
OAI Identifier:
DOI: 10.1155/2018/2547270
Official URL:
Deposited by: Memoria Investigacion
Deposited on: 29 Apr 2019 16:29
Last Modified: 29 Apr 2019 16:29
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM