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

Graphs have been commonly used to model many applications. A natural problem which abstracts applications such as itinerary planning, playlist recommendation, and flow analysis in information networks is that of finding the heaviest path(s) in a graph. More precisely, we can model these applications as a graph with non-negative edge weights, along with a monotone function such as sum, which aggregates edge weights into a path weight, capturing some notion of quality. We are t...

Influence maximization aims to identify a set of influential individuals, referred to as influencers, as information sources to maximize the spread of information within networks, constituting a vital combinatorial optimization problem with extensive practical applications and sustained interdisciplinary interest. Diverse approaches have been devised to efficiently address this issue, one of which involves selecting the influencers from a given centrality ranking. In this pap...

Graph is a useful data structure to model various real life aspects like email communications, co-authorship among researchers, interactions among chemical compounds, and so on. Supporting such real life interactions produce a knowledge rich massive repository of data. However, efficiently understanding underlying trends and patterns is hard due to large size of the graph. Therefore, this paper presents a scalable compression solution to compute summary of a weighted graph. A...

An important concept in organisational behaviour is how hierarchy affects the voice of individuals, whereby members of a given organisation exhibit differing power relations based on their hierarchical position. Although there have been prior studies of the relationship between hierarchy and voice, they tend to focus on more qualitative small-scale methods and do not account for structural aspects of the organisation. This paper develops large-scale computational techniques u...

What are the relations between the edge weights and the topology in real-world graphs? Given only the topology of a graph, how can we assign realistic weights to its edges based on the relations? Several trials have been done for edge-weight prediction where some unknown edge weights are predicted with most edge weights known. There are also existing works on generating both topology and edge weights of weighted graphs. Differently, we are interested in generating edge weight...

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

We study the problem of clustering networks whose nodes have imputed or physical positions in a single dimension, for example prestige hierarchies or the similarity dimension of hyperbolic embeddings. Existing algorithms, such as the critical gap method and other greedy strategies, only offer approximate solutions to this problem. Here, we introduce a dynamic programming approach that returns provably optimal solutions in polynomial time -- O(n^2) steps -- for a broad class o...

Ranking algorithms are pervasive in our increasingly digitized societies, with important real-world applications including recommender systems, search engines, and influencer marketing practices. From a network science perspective, network-based ranking algorithms solve fundamental problems related to the identification of vital nodes for the stability and dynamics of a complex system. Despite the ubiquitous and successful applications of these algorithms, we argue that our u...

Scientific journals are the repositories of the gradually accumulating knowledge of mankind about the world surrounding us. Just as our knowledge is organised into classes ranging from major disciplines, subjects and fields to increasingly specific topics, journals can also be categorised into groups using various metrics. In addition to the set of topics characteristic for a journal, they can also be ranked regarding their relevance from the point of overall influence. One w...

In this paper, we study a number of well-known combinatorial optimization problems that fit in the following paradigm: the input is a collection of (potentially inconsistent) local relationships between the elements of a ground set (e.g., pairwise comparisons, similar/dissimilar pairs, or ancestry structure of triples of points), and the goal is to aggregate this information into a global structure (e.g., a ranking, a clustering, or a hierarchical clustering) in a way that ma...