Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks

Hierarchy is one of the most conspicuous features of numerous natural, technological and social systems. The underlying structures are typically complex and their most relevant organizational principle is the ordering of the ties among the units they are made of according to a network displaying hierarchical features. In spite of the abundant presence of hierarchy no quantitative theoretical interpretation of the origins of a multi-level, knowledge-based social network exists...

We present algorithms and experiments for the visualization of directed graphs that focus on displaying their reachability information. Our algorithms are based on the concepts of the path and channel decomposition as proposed in the framework presented in GD 2018 (pp. 579-592) and focus on showing the existence of paths clearly. In this paper we customize these concepts and present experimental results that clearly show the interplay between bends, crossings and clarity. Add...

A number of recent works have concentrated on a few statistical properties of complex networks, such as the clustering, the right-skewed degree distribution and the community, which are common to many real world networks. In this paper, we address the hierarchy property sharing among a large amount of networks. Based upon the eigenvector centrality (EC) measure, a method is proposed to reconstruct the hierarchical structure of a complex network. It is tested on the Santa Fe I...

Many applications produce massive complex networks whose analysis would benefit from parallel processing. Parallel algorithms, in turn, often require a suitable network partition. For solving optimization tasks such as graph partitioning on large networks, multilevel methods are preferred in practice. Yet, complex networks pose challenges to established multilevel algorithms, in particular to their coarsening phase. One way to specify a (recursive) coarsening of a graph is ...

We present a physics-inspired method for inferring dynamic rankings in directed temporal networks - networks in which each directed and timestamped edge reflects the outcome and timing of a pairwise interaction. The inferred ranking of each node is real-valued and varies in time as each new edge, encoding an outcome like a win or loss, raises or lowers the node's estimated strength or prestige, as is often observed in real scenarios including sequences of games, tournaments, ...

Directed networks such as gene regulation networks and neural networks are connected by arcs (directed links). The nodes in a directed network are often strongly interwound by a huge number of directed cycles, which lead to complex information-processing dynamics in the network and make it highly challenging to infer the intrinsic direction of information flow. In this theoretical paper, based on the principle of minimum-feedback, we explore the node hierarchy of directed net...

Community detection and hierarchy extraction are usually thought of as separate inference tasks on networks. Considering only one of the two when studying real-world data can be an oversimplification. In this work, we present a generative model based on an interplay between community and hierarchical structures. It assumes that each node has a preference in the interaction mechanism and nodes with the same preference are more likely to interact, while heterogeneous interactio...

The trophic levels of nodes in directed networks can reveal their functional properties. Moreover, the trophic coherence of a network, defined in terms of trophic levels, is related to properties such as cycle structure, stability and percolation. The standard definition of trophic levels, however, borrowed from ecology, suffers from drawbacks such as requiring source nodes, which limit its applicability. Here we propose a simple new definition of trophic level that can be co...

The most commonly used method to tackle the graph partitioning problem in practice is the multilevel approach. During a coarsening phase, a multilevel graph partitioning algorithm reduces the graph size by iteratively contracting nodes and edges until the graph is small enough to be partitioned by some other algorithm. A partition of the input graph is then constructed by successively transferring the solution to the next finer graph and applying a local search algorithm to i...

Complex real-world networks commonly reveal characteristic groups of nodes like communities and modules. These are of value in various applications, especially in the case of large social and information networks. However, while numerous community detection techniques have been presented in the literature, approaches for other groups of nodes are relatively rare and often limited in some way. We present a simple propagation-based algorithm for general group detection that req...