Finding multiple core-periphery pairs in networks

Detectability constraints on meso-scale structure in complex networks

Community, core-periphery, disassortative and other node partitions allow us to understand the organisation and function of large networks. In this work we study common meso-scale structures using the idea of block modularity. We find that the configuration model imposes strong restrictions on core-periphery and related structures in directed and undirected networks. We derive inequalities expressing when such structures can be detected under the configuration model which are closely related to the resolution limit. Nestedness is closely related to core-periphery and is similarly restricted to only be detectable under certain conditions. We then derive a general equivalence between optimising block modularity and maximum likelihood estimation of the parameters of the degree corrected Stochastic Block Model. This allows us to contrast the two approaches, how they formalise the structure detection problem and understand these constraints in inferential versus descriptive approaches to meso-scale structure detection.

Conceptual structure and the growth of scientific knowledge

How does scientific knowledge grow? This question has occupied a central place in the philosophy of science, stimulating heated debates but yielding no clear consensus. Many explanations can be understood in terms of whether and how they view the expansion of knowledge as proceeding through the accretion of scientific concepts into larger conceptual structures. Here we examine these views empirically by analysing 2,605,224 papers spanning five decades from both the social sciences (Web of Science) and the physical sciences (American Physical Society). Using natural language processing techniques, we create semantic networks of concepts, wherein noun phrases become linked when used in the same paper abstract. We then detect the core/periphery structures of these networks, wherein core concepts are densely connected sets of highly central nodes and periphery concepts are sparsely connected nodes that are highly connected to the core. For both the social and physical sciences, we observe increasingly rigid conceptual cores accompanied by the proliferation of periphery concepts. Subsequently, we examine the relationship between conceptual structure and the growth of scientific knowledge, finding that scientific works are more innovative in fields with cores that have higher conceptual churn and with larger cores. Furthermore, scientific consensus is associated with reduced conceptual churn and fewer conceptual cores. Overall, our findings suggest that while the organization of scientific concepts is important for the growth of knowledge, the mechanisms vary across time.

Structural dynamics of plant-pollinator mutualistic networks

The discourse surrounding the structural organization of mutualistic interactions mostly revolves around modularity and nestedness. The former is known to enhance the stability of communities, while the latter is related to their feasibility, albeit compromising the stability. However, it has recently been shown that the joint emergence of these structures poses challenges that can eventually lead to limitations in the dynamic properties of mutualistic communities. We hypothesize that considering compound arrangements-modules with internal nested organization-can offer valuable insights in this debate. We analyze the temporal structural dynamics of 20 plant-pollinator interaction networks and observe large structural variability throughout the year. Compound structures are particularly prevalent during the peak of the pollination season, often coexisting with nested and modular arrangements in varying degrees. Motivated by these empirical findings, we synthetically investigate the dynamics of the structural patterns across two control parameters-community size and connectance levels-mimicking the progression of the pollination season. Our analysis reveals contrasting impacts on the stability and feasibility of these mutualistic communities. We characterize the consistent relationship between network structure and stability, which follows a monotonic pattern. But, in terms of feasibility, we observe nonlinear relationships. Compound structures exhibit a favorable balance between stability and feasibility, particularly in mid-sized ecological communities, suggesting they may effectively navigate the simultaneous requirements of stability and feasibility. These findings may indicate that the assembly process of mutualistic communities is driven by a delicate balance among multiple properties, rather than the dominance of a single one.

Nonassortative relationships between groups of nodes are typical in complex networks

Decomposing a graph into groups of nodes that share similar connectivity properties is essential to understand the organization and function of complex networks. Previous works have focused on groups with specific relationships between group members, such as assortative communities or core-periphery structures, developing computational methods to find these mesoscale structures within a network. Here, we go beyond these two traditional cases and introduce a methodology that is able to identify and systematically classify all possible community types in directed multi graphs, based on the pairwise relationship between groups. We apply our approach to 53 different networks and find that assortative communities are the most common structures, but that previously unexplored types appear in almost every network. A particularly prevalent new type of relationship, which we call a source-basin structure, has information flowing from a sparsely connected group of nodes (source) to a densely connected group (basin). We look in detail at two online social networks-a new network of Twitter users and a well-studied network of political blogs-and find that source-basin structures play an important role in both of them. This confirms not only the widespread appearance of nonassortative structures but also the potential of hitherto unidentified relationships to explain the organization of complex networks.

Generative models for two-ground-truth partitions in networks

A myriad of approaches have been proposed to characterize the mesoscale structure of networks most often as a partition based on patterns variously called communities, blocks, or clusters. Clearly, distinct methods designed to detect different types of patterns may provide a variety of answers' to the networks mesoscale structure. Yet even multiple runs of a given method can sometimes yield diverse and conflicting results, producing entire landscapes of partitions which potentially include multiple (locally optimal) mesoscale explanations of the network. Such ambiguity motivates a closer look at the ability of these methods to find multiple qualitatively different "ground truth" partitions in a network. Here we propose the stochastic cross-block model (SCBM), a generative model which allows for two distinct partitions to be built into the mesoscale structure of a single benchmark network. We demonstrate a use case of the benchmark model by appraising the power of stochastic block models (SBMs) to detect implicitly planted coexisting bicommunity and core-periphery structures of different strengths. Given our model design and experimental setup, we find that the ability to detect the two partitions individually varies by SBM variant and that coexistence of both partitions is recovered only in a very limited number of cases. Our findings suggest that in most instances only one-in some way dominating-structure can be detected, even in the presence of other partitions. They underline the need for considering entire landscapes of partitions when different competing explanations exist and motivate future research to advance partition coexistence detection methods. Our model also contributes to the field of benchmark networks more generally by enabling further exploration of the ability of new and existing methods to detect ambiguity in the mesoscale structure of networks.

Hierarchical core-periphery structure in networks

We study core-periphery structure in networks using inference methods based on a flexible network model that allows for traditional onionlike cores within cores, but also for hierarchical treelike structures and more general non-nested types of structures. We propose an efficient Monte Carlo scheme for fitting the model to observed networks and report results for a selection of real-world data sets. Among other things, we observe an empirical distinction between networks showing traditional core-periphery structure with a dense core weakly connected to a sparse periphery, and an alternative structure in which the core is strongly connected both within itself and to the periphery. Networks vary in whether they are better represented by one type of structure or the other. We also observe structures that are a hybrid between core-periphery structure and community structure, in which networks have a set of nonoverlapping cores that roughly correspond to communities, surrounded by a single undifferentiated periphery. Computer code implementing our methods is available.

Opinion manipulation on Farsi Twitter

For Iranians and the Iranian diaspora, the Farsi Twittersphere provides an important alternative to state media and an outlet for political discourse. But this understudied online space has become an opinion manipulation battleground, with diverse actors using inauthentic accounts to advance their goals and shape online narratives. Examining trending discussions crossing social cleavages in Iran, we explore how the dynamics of opinion manipulation differ across diverse issue areas. Our analysis suggests that opinion manipulation by inauthentic accounts is more prevalent in divisive political discussions than non-divisive or apolitical discussions. We show how Twitter's network structures help to reinforce the content propagated by clusters of inauthentic accounts in divisive political discussions. Analyzing both the content and structure of online discussions in the Iranian Twittersphere, this work contributes to a growing body of literature exploring the dynamics of online opinion manipulation, while improving our understanding of how information is controlled in the digital age.

Software Components and Product Variety in a Platform Ecosystem: A Dynamic Network Analysis of WordPress

Software components such as application programming interfaces (APIs) provided by external developers are vital to online digital platforms. Although APIs generally increase the variety of products according to anecdote, the precise relationship between the categories of APIs and product variety is not yet known. We find that APIs, regarding their use frequency, are categorized into three groups. The core is a group of frequently used APIs, whereas the periphery is a group of sparsely used APIs. In a large and mature platform ecosystem, an additional group of APIs, the regular core, mainly provided by third-party developers, emerges. APIs in the regular core are the main driver of product variety. However, we also find that the strength of this effect diminishes in a newly created product category when most of the new products are built by duplicating the usage of APIs from other products. A platform owner can stimulate developers’ creativity by acting as a bridge between digital product providers and third-party developers. It can collect functional needs from third-party developers and then share them with product providers. Therefore, the latter can build APIs that developers need.

A clarified typology of core-periphery structure in networks

Core-periphery structure, the arrangement of a network into a dense core and sparse periphery, is a versatile descriptor of various social, biological, and technological networks. In practice, different core-periphery algorithms are often applied interchangeably despite the fact that they can yield inconsistent descriptions of core-periphery structure. For example, two of the most widely used algorithms, the k-cores decomposition and the classic two-block model of Borgatti and Everett, extract fundamentally different structures: The latter partitions a network into a binary hub-and-spoke layout, while the former divides it into a layered hierarchy. We introduce a core-periphery typology to clarify these differences, along with Bayesian stochastic block modeling techniques to classify networks in accordance with this typology. Empirically, we find a rich diversity of core-periphery structure among networks. Through a detailed case study, we demonstrate the importance of acknowledging this diversity and situating networks within the core-periphery typology when conducting domain-specific analyses.

Core-periphery structure in directed networks

Empirical networks often exhibit different meso-scale structures, such as community and core-periphery structures. Core-periphery structure typically consists of a well-connected core and a periphery that is well connected to the core but sparsely connected internally. Most core-periphery studies focus on undirected networks. We propose a generalization of core-periphery structure to directed networks. Our approach yields a family of core-periphery block model formulations in which, contrary to many existing approaches, core and periphery sets are edge-direction dependent. We focus on a particular structure consisting of two core sets and two periphery sets, which we motivate empirically. We propose two measures to assess the statistical significance and quality of our novel structure in empirical data, where one often has no ground truth. To detect core-periphery structure in directed networks, we propose three methods adapted from two approaches in the literature, each with a different trade-off between computational complexity and accuracy. We assess the methods on benchmark networks where our methods match or outperform standard methods from the literature, with a likelihood approach achieving the highest accuracy. Applying our methods to three empirical networks-faculty hiring, a world trade dataset and political blogs-illustrates that our proposed structure provides novel insights in empirical networks.

An improved belief propagation algorithm for detecting mesoscale structure in complex networks

The framework of statistical inference has been successfully used to detect the mesoscale structures in complex networks such as community structure and core-periphery (CP) structure. The main principle is that the stochastic block model is used to fit the observed network and the learned parameters indicating the group assignment, in which the parameters of model are often calculated via an expectation-maximization algorithm and a belief propagation (BP) algorithm, is implemented to calculate the decomposition itself. In the derivation process of the BP algorithm, some approximations were made by omitting the effects of node's neighbors, the approximations do not hold if the degrees of some nodes are extremely large. As a result, for example, the BP algorithm cannot detect the CP structure in networks and even yields a wrong detection because the nodal degrees in the core group are very large. In doing so, we propose an improved BP algorithm to solve the problem in the original BP algorithm without increasing any computational complexity. We find that the original and the improved BP algorithms yield a similar performance regarding the community detection; however, our improved BP algorithm is much better and more stable when the CP structure becomes more dominant. The improved BP algorithm may help us correctly partition different types of mesoscale structures in networks.

A Fast and Exact Greedy Algorithm for the Core–Periphery Problem

The core–periphery structure is one of the key concepts in the structural analysis of complex networks. It consists of a partitioning of the node set of a given graph or network into two groups, called core and periphery, where the core nodes induce a well-connected subgraph and share connections with peripheral nodes, while the peripheral nodes are loosely connected to the core nodes and other peripheral nodes. We propose a polynomial-time algorithm to detect core–periphery structures in networks having a symmetric adjacency matrix. The core set is defined as the solution of a combinatorial optimization problem, which has a pleasant symmetry with respect to graph complementation. We provide a complete description of the optimal solutions to that problem and an exact and efficient algorithm to compute them. The proposed approach is extended to networks with loops and oriented edges. Numerical simulations are carried out on both synthetic and real-world networks to demonstrate the effectiveness and practicability of the proposed algorithm.

Multiscale core-periphery structure in a global liner shipping network

Maritime transport accounts for a majority of trades in volume, of which 70% in value is carried by container ships that transit regular routes on fixed schedules in the ocean. In the present paper, we analyse a data set of global liner shipping as a network of ports. In particular, we construct the network of the ports as the one-mode projection of a bipartite network composed of ports and ship routes. Like other transportation networks, global liner shipping networks may have core-periphery structure, where a core and a periphery are groups of densely and sparsely interconnected nodes, respectively. Core-periphery structure may have practical implications for understanding the robustness, efficiency and uneven development of international transportation systems. We develop an algorithm to detect core-periphery pairs in a network, which allows one to find core and peripheral nodes on different scales and uses a configuration model that accounts for the fact that the network is obtained by the one-mode projection of a bipartite network. We also found that most ports are core (as opposed to peripheral) ports and that ports in some countries in Europe, America and Asia belong to a global core-periphery pair across different scales, whereas ports in other countries do not.

Revealing in-block nestedness: Detection and benchmarking

As new instances of nested organization-beyond ecological networks-are discovered, scholars are debating the coexistence of two apparently incompatible macroscale architectures: nestedness and modularity. The discussion is far from being solved, mainly for two reasons. First, nestedness and modularity appear to emerge from two contradictory dynamics, cooperation and competition. Second, existing methods to assess the presence of nestedness and modularity are flawed when it comes to the evaluation of concurrently nested and modular structures. In this work, we tackle the latter problem, presenting the concept of in-block nestedness, a structural property determining to what extent a network is composed of blocks whose internal connectivity exhibits nestedness. We then put forward a set of optimization methods that allow us to identify such organization successfully, in synthetic and in a large number of real networks. These findings challenge our understanding of the topology of ecological and social systems, calling for new models to explain how such patterns emerge.

Detection of core-periphery structure in networks based on 3-tuple motifs

Detecting mesoscale structure, such as community structure, is of vital importance for analyzing complex networks. Recently, a new mesoscale structure, core-periphery (CP) structure, has been identified in many real-world systems. In this paper, we propose an effective algorithm for detecting CP structure based on a 3-tuple motif. In this algorithm, we first define a 3-tuple motif in terms of the patterns of edges as well as the property of nodes, and then a motif adjacency matrix is constructed based on the 3-tuple motif. Finally, the problem is converted to find a cluster that minimizes the smallest motif conductance. Our algorithm works well in different CP structures: including single or multiple CP structure, and local or global CP structures. Results on the synthetic and the empirical networks validate the high performance of our method.

A unified method of detecting core-periphery structure and community structure in networks

The core-periphery structure and the community structure are two typical meso-scale structures in complex networks. Although community detection has been extensively investigated from different perspectives, the definition and the detection of the core-periphery structure have not received much attention. Furthermore, the detection problems of the core-periphery and community structure were separately investigated. In this paper, we develop a unified framework to simultaneously detect the core-periphery structure and community structure in complex networks. Moreover, there are several extra advantages of our algorithm: our method can detect not only single but also multiple pairs of core-periphery structures; the overlapping nodes belonging to different communities can be identified; different scales of core-periphery structures can be detected by adjusting the size of the core. The good performance of the method has been validated on synthetic and real complex networks. So, we provide a basic framework to detect the two typical meso-scale structures: the core-periphery structure and the community structure.