ID: 1902.01477

Faster way to agony: Discovering hierarchies in directed graphs

February 4, 2019

View on ArXiv

Similar papers 2

Fast Hierarchy Construction for Dense Subgraphs

October 6, 2016

85% Match
A. Erdem Sariyuce, Ali Pinar
Social and Information Netwo...

Discovering dense subgraphs and understanding the relations among them is a fundamental problem in graph mining. We want to not only identify dense subgraphs, but also build a hierarchy among them (e.g., larger but sparser subgraphs formed by two smaller dense subgraphs). Peeling algorithms (k-core, k-truss, and nucleus decomposition) have been effective to locate many dense subgraphs. However, constructing a hierarchical representation of density structure, even correctly co...

Find SimilarView on arXiv

Structural Inference of Hierarchies in Networks

October 9, 2006

85% Match
Aaron Clauset, Cristopher Moore, M. E. J. Newman
Physics and Society
Machine Learning
Data Analysis, Statistics an...

One property of networks that has received comparatively little attention is hierarchy, i.e., the property of having vertices that cluster together in groups, which then join to form groups of groups, and so forth, up through all levels of organization in the network. Here, we give a precise definition of hierarchical structure, give a generic model for generating arbitrary hierarchical structure in a random graph, and describe a statistically principled way to learn the set ...

Find SimilarView on arXiv

Hierarchical structure and the prediction of missing links in networks

November 4, 2008

84% Match
Aaron Clauset, Cristopher Moore, M. E. J. Newman
Machine Learning
Physics and Society
Molecular Networks

Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science. Recent studies suggest that networks often exhibit hierarchical organization, where vertices divide into groups that further subdivide into groups of groups, and so forth over multiple scales. In many cases these groups are found to correspond to known functional units, such as ecological niches in food webs, modules in biochemical networks (...

Find SimilarView on arXiv

Weighted hierarchical alignment of directed acyclic graph

June 29, 2006

84% Match
Sean M. Falconer, Dmitri Maslov
Data Structures and Algorith...

In some applications of matching, the structural or hierarchical properties of the two graphs being aligned must be maintained. The hierarchical properties are induced by the direction of the edges in the two directed graphs. These structural relationships defined by the hierarchy in the graphs act as a constraint on the alignment. In this paper, we formalize the above problem as the weighted alignment between two directed acyclic graphs. We prove that this problem is NP-comp...

Find SimilarView on arXiv

A Survey of Hierarchy Identification in Social Networks

December 20, 2018

84% Match
Denys Katerenchuk
Computation and Language
Artificial Intelligence
Social and Information Netwo...

Humans are social by nature. Throughout history, people have formed communities and built relationships. Most relationships with coworkers, friends, and family are developed during face-to-face interactions. These relationships are established through explicit means of communications such as words and implicit such as intonation, body language, etc. By analyzing human interactions we can derive information about the relationships and influence among conversation participants....

Find SimilarView on arXiv

Geometric detection of hierarchical backbones in real networks

June 5, 2020

84% Match
Elisenda Ortiz, Guillermo García-Pérez, M. Ángeles Serrano
Physics and Society
Social and Information Netwo...

Hierarchies permeate the structure of real networks, whose nodes can be ranked according to different features. However, networks are far from tree-like structures and the detection of hierarchical ordering remains a challenge, hindered by the small-world property and the presence of a large number of cycles, in particular clustering. Here, we use geometric representations of undirected networks to achieve an enriched interpretation of hierarchy that integrates features defin...

Find SimilarView on arXiv

SLUGGER: Lossless Hierarchical Summarization of Massive Graphs

December 10, 2021

84% Match
Kyuhan Lee, Jihoon Ko, Kijung Shin
Databases
Social and Information Netwo...

Given a massive graph, how can we exploit its hierarchical structure for concisely but exactly summarizing the graph? By exploiting the structure, can we achieve better compression rates than state-of-the-art graph summarization methods? The explosive proliferation of the Web has accelerated the emergence of large graphs, such as online social networks and hyperlink networks. Consequently, graph compression has become increasingly important to process such large graphs with...

Find SimilarView on arXiv

Detecting Hierarchical Ties Using Link-Analysis Ranking at Different Levels of Time Granularity

January 24, 2017

84% Match
Hend Kareem, Lars Asker, Panagiotis Papapetrou
Social and Information Netwo...
Physics and Society

Social networks contain implicit knowledge that can be used to infer hierarchical relations that are not explicitly present in the available data. Interaction patterns are typically affected by users' social relations. We present an approach to inferring such information that applies a link-analysis ranking algorithm at different levels of time granularity. In addition, a voting scheme is employed for obtaining the hierarchical relations. The approach is evaluated on two data...

Find SimilarView on arXiv

Shortest Path Discovery in the Multi-layered Social Network

October 18, 2012

84% Match
Piotr Bródka, Paweł Stawiak, Przemysław Kazienko
Social and Information Netwo...
Physics and Society

Multi-layered social networks consist of the fixed set of nodes linked by multiple connections. These connections may be derived from different types of user activities logged in the IT system. To calculate any structural measures for multi-layered networks this multitude of relations should be coped with in the parameterized way. Two separate algorithms for evaluation of shortest paths in the multi-layered social network are proposed in the paper. The first one is based on p...

Find SimilarView on arXiv

Expander Hierarchies for Normalized Cuts on Graphs

June 20, 2024

84% Match
Kathrin Hanauer, Monika Henzinger, Robin Münk, ... , Vötsch Maximilian
Data Structures and Algorith...
Machine Learning

Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility...

Find SimilarView on arXiv