ID: 1902.01477

Faster way to agony: Discovering hierarchies in directed graphs

February 4, 2019

View on ArXiv

Similar papers 3

The Mont Blanc of Twitter: Identifying Hierarchies of Outstanding Peaks in Social Networks

October 26, 2021

84% Match
Maximilian Stubbemann, Gerd Stumme
Social and Information Netwo...

The investigation of social networks is often hindered by their size as such networks often consist of at least thousands of vertices and edges. Hence, it is of major interest to derive compact structures that represent important connections of the original network. In this work, we derive such structures with orometric methods that are originally designed to identify outstanding mountain peaks and relationships between them. By adapting these methods to social networks, it i...

Find SimilarView on arXiv

Feedback arcs and node hierarchy in directed networks

December 16, 2016

83% Match
Jin-Hua Zhao, Hai-Jun Zhou
Physics and Society
Disordered Systems and Neura...
Social and Information Netwo...

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...

Find SimilarView on arXiv

Experiments and a User Study for Hierarchical Drawings of Graphs

September 9, 2022

83% Match
Panagiotis Lionakis, Giorgos Kritikakis, Ioannis G. Tollis
Human-Computer Interaction
Data Structures and Algorith...

We present experimental results and a user study for hierarchical drawings of graphs. A detailed hierarchical graph drawing technique that is based on the Path Based Framework (PBF) is presented. Extensive edge bundling is applied to draw all edges of the graph and the height of the drawing is minimized using compaction. The drawings produced by this framework are compared to drawings produced by the well known Sugiyama framework in terms of area, number of bends, number of c...

Find SimilarView on arXiv

Extracting hierarchical backbones from bipartite networks

February 17, 2020

83% Match
Woo Seong Jo, Jaehyuk Park, Arthur Luhur, ... , Ahn Yong-Yeol
Social and Information Netwo...
Data Analysis, Statistics an...

We propose a method for extracting hierarchical backbones from a bipartite network. Our method leverages the observation that a hierarchical relationship between two nodes in a bipartite network is often manifested as an asymmetry in the conditional probability of observing the connections to them from the other node set. Our method estimates both the importance and direction of the hierarchical relationship between a pair of nodes, thereby providing a flexible way to identif...

Find SimilarView on arXiv

Algorithms and Experiments Comparing Two Hierarchical Drawing Frameworks

November 24, 2020

83% Match
Panagiotis Lionakis, Giorgos Kritikakis, Ioannis G. Tollis
Data Structures and Algorith...

We present algorithms that extend the path-based hierarchical drawing framework and give experimental results. Our algorithms run in $O(km)$ time, where $k$ is the number of paths and $m$ is the number of edges of the graph, and provide better upper bounds than the original path based framework: e.g., the height of the resulting drawings is equal to the length of the longest path of $G$, instead of $n-1$, where $n$ is the number of nodes. Additionally, we extend this framewor...

Find SimilarView on arXiv

Communities and Hierarchical Structures in Dynamic Social Networks: Analysis and Visualization

September 17, 2014

83% Match
Frédéric Gilbert, Paolo Simonetto, Faraz Zaidi, ... , Bourqui Romain
Social and Information Netwo...
Physics and Society

Detection of community structures in social networks has attracted lots of attention in the domain of sociology and behavioral sciences. Social networks also exhibit dynamic nature as these networks change continuously with the passage of time. Social networks might also present a hierarchical structure led by individuals that play important roles in a society such as Managers and Decision Makers. Detection and Visualization of these networks changing over time is a challengi...

Find SimilarView on arXiv

Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs

June 16, 2023

83% Match
Steinar Laenen, Bogdan-Adrian Manghiuc, He Sun
Data Structures and Algorith...
Machine Learning

This paper presents two efficient hierarchical clustering (HC) algorithms with respect to Dasgupta's cost function. For any input graph $G$ with a clear cluster-structure, our designed algorithms run in nearly-linear time in the input size of $G$, and return an $O(1)$-approximate HC tree with respect to Dasgupta's cost function. We compare the performance of our algorithm against the previous state-of-the-art on synthetic and real-world datasets and show that our designed alg...

Find SimilarView on arXiv

On Finding Optimal (Dynamic) Arborescences

November 6, 2023

83% Match
Joaquim Espada, Alexandre P. Francisco, Tatiana Rocher, ... , Vaz Cátia
Data Structures and Algorith...

Let G = (V, E) be a directed and weighted graph with vertex set V of size n and edge set E of size m, such that each edge (u, v) \in E has a real-valued weight w(u, c). An arborescence in G is a subgraph T = (V, E') such that for a vertex u \in V, the root, there is a unique path in T from u to any other vertex v \in V. The weight of T is the sum of the weights of its edges. In this paper, given G, we are interested in finding an arborescence in G with minimum weight, i.e., a...

Find SimilarView on arXiv

Partitioning Complex Networks via Size-constrained Clustering

February 13, 2014

83% Match
Henning Meyerhenke, Peter Sanders, Christian Schulz
Distributed, Parallel, and C...
Data Structures and Algorith...
Social and Information Netwo...

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...

Find SimilarView on arXiv

Hierarchy in directed random networks

August 30, 2012

83% Match
Enys Mones
Physics and Society
Statistical Mechanics
Social and Information Netwo...
Data Analysis, Statistics an...

In recent years, the theory and application of complex networks have been quickly developing in a markable way due to the increasing amount of data from real systems and to the fruitful application of powerful methods used in statistical physics. Many important characteristics of social or biological systems can be described by the study of their underlying structure of interactions. Hierarchy is one of these features that can be formulated in the language of networks. In thi...

Find SimilarView on arXiv