Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Resolution of ranking hierarchies in directed networks.

ABSTRACT: Identifying hierarchies and rankings of nodes in directed graphs is fundamental in many applications such as social network analysis, biology, economics, and finance. A recently proposed method identifies the hierarchy by finding the ordered partition of nodes which minimises a score function, termed agony. This function penalises the links violating the hierarchy in a way depending on the strength of the violation. To investigate the resolution of ranking hierarchies we introduce an ensemble of random graphs, the Ranked Stochastic Block Model. We find that agony may fail to identify hierarchies when the structure is not strong enough and the size of the classes is small with respect to the whole network. We analytically characterise the resolution threshold and we show that an iterated version of agony can partly overcome this resolution limit.

SUBMITTER: Letizia E

PROVIDER: S-EPMC5796714 | biostudies-literature | 2018

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Resolution of ranking hierarchies in directed networks.

Letizia Elisa E Barucca Paolo P Lillo Fabrizio F

PloS one 20180202 2

Identifying hierarchies and rankings of nodes in directed graphs is fundamental in many applications such as social network analysis, biology, economics, and finance. A recently proposed method identifies the hierarchy by finding the ordered partition of nodes which minimises a score function, termed agony. This function penalises the links violating the hierarchy in a way depending on the strength of the violation. To investigate the resolution of ranking hierarchies we introduce an ensemble of ...[more]

PMID: 29394278

Similar Datasets

Ranking species in mutualistic networks.

Project description:Understanding the architectural subtleties of ecological networks, believed to confer them enhanced stability and robustness, is a subject of outmost relevance. Mutualistic interactions have been profusely studied and their corresponding bipartite networks, such as plant-pollinator networks, have been reported to exhibit a characteristic "nested" structure. Assessing the importance of any given species in mutualistic networks is a key task when evaluating extinction risks and possible cascade effects. Inspired in a recently introduced algorithm--similar in spirit to Google's PageRank but with a built-in non-linearity--here we propose a method which--by exploiting their nested architecture--allows us to derive a sound ranking of species importance in mutualistic networks. This method clearly outperforms other existing ranking schemes and can become very useful for ecosystem management and biodiversity preservation, where decisions on what aspects of ecosystems to explicitly protect need to be made.

| S-EPMC4313099 | biostudies-other

Learning motifs and their hierarchies in atomic resolution microscopy.

Project description:Characterizing materials to atomic resolution and first-principles structure-property prediction are two pillars for accelerating functional materials discovery. However, we are still lacking a rapid, noise-robust framework to extract multilevel atomic structural motifs from complex materials to complement, inform, and guide our first-principles models. Here, we present a machine learning framework that rapidly extracts a hierarchy of complex structural motifs from atomically resolved images. We demonstrate how such motif hierarchies can rapidly reconstruct specimens with various defects. Abstracting complex specimens with simplified motifs enabled us to discover a previously unidentified structure in a Mo─V─Te─Nb polyoxometalate (POM) and quantify the relative disorder in a twisted bilayer MoS2. In addition, these motif hierarchies provide statistically grounded clues about the favored and frustrated pathways during self-assembly. The motifs and their hierarchies in our framework coarse-grain disorder in a manner that allows us to understand a much broader range of multiscale samples with functional imperfections and nontrivial topological phases.

| S-EPMC9007509 | biostudies-literature

Quantum navigation and ranking in complex networks.

Project description:Complex networks are formal frameworks capturing the interdependencies between the elements of large systems and databases. This formalism allows to use network navigation methods to rank the importance that each constituent has on the global organization of the system. A key example is Pagerank navigation which is at the core of the most used search engine of the World Wide Web. Inspired in this classical algorithm, we define a quantum navigation method providing a unique ranking of the elements of a network. We analyze the convergence of quantum navigation to the stationary rank of networks and show that quantumness decreases the number of navigation steps before convergence. In addition, we show that quantum navigation allows to solve degeneracies found in classical ranks. By implementing the quantum algorithm in real networks, we confirm these improvements and show that quantum coherence unveils new hierarchical features about the global organization of complex systems.

| S-EPMC3428603 | biostudies-other

Autophagy signal transduction by ATG proteins: from hierarchies to networks.

Project description:Autophagy represents an intracellular degradation process which is involved in both cellular homeostasis and disease settings. In the last two decades, the molecular machinery governing this process has been characterized in detail. To date, several key factors regulating this intracellular degradation process have been identified. The so-called autophagy-related (ATG) genes and proteins are central to this process. However, several additional molecules contribute to the outcome of an autophagic response. Several review articles describing the molecular process of autophagy have been published in the recent past. In this review article we would like to add the most recent findings to this knowledge, and to give an overview of the network character of the autophagy signaling machinery.

| S-EPMC4648967 | biostudies-literature

A physical model for efficient ranking in networks.

Project description:We present a physically inspired model and an efficient algorithm to infer hierarchical rankings of nodes in directed networks. It assigns real-valued ranks to nodes rather than simply ordinal ranks, and it formalizes the assumption that interactions are more likely to occur between individuals with similar ranks. It provides a natural statistical significance test for the inferred hierarchy, and it can be used to perform inference tasks such as predicting the existence or direction of edges. The ranking is obtained by solving a linear system of equations, which is sparse if the network is; thus, the resulting algorithm is extremely efficient and scalable. We illustrate these findings by analyzing real and synthetic data, including data sets from animal behavior, faculty hiring, social support networks, and sports tournaments. We show that our method often outperforms a variety of others, in both speed and accuracy, in recovering the underlying ranks and predicting edge directions.

| S-EPMC6054508 | biostudies-literature

Ranking nodes in growing networks: When PageRank fails.

Project description:PageRank is arguably the most popular ranking algorithm which is being applied in real systems ranging from information to biological and infrastructure networks. Despite its outstanding popularity and broad use in different areas of science, the relation between the algorithm's efficacy and properties of the network on which it acts has not yet been fully understood. We study here PageRank's performance on a network model supported by real data, and show that realistic temporal effects make PageRank fail in individuating the most valuable nodes for a broad range of model parameters. Results on real data are in qualitative agreement with our model-based findings. This failure of PageRank reveals that the static approach to information filtering is inappropriate for a broad class of growing systems, and suggest that time-dependent algorithms that are based on the temporal linking patterns of these systems are needed to better rank the nodes.

| S-EPMC4639772 | biostudies-literature

Homophily influences ranking of minorities in social networks.

Project description:Homophily can put minority groups at a disadvantage by restricting their ability to establish links with a majority group or to access novel information. Here, we show how this phenomenon can influence the ranking of minorities in examples of real-world networks with various levels of heterophily and homophily ranging from sexual contacts, dating contacts, scientific collaborations, and scientific citations. We devise a social network model with tunable homophily and group sizes, and demonstrate how the degree ranking of nodes from the minority group in a network is a function of (i) relative group sizes and (ii) the presence or absence of homophilic behaviour. We provide analytical insights on how the ranking of the minority can be improved to ensure the representativeness of the group and correct for potential biases. Our work presents a foundation for assessing the impact of homophilic and heterophilic behaviour on minorities in social networks.

| S-EPMC6056555 | biostudies-literature

The interplay between ranking and communities in networks.

Project description: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 interactions are still allowed. The sparsity of the network is exploited for implementing a more efficient algorithm. We demonstrate our method on synthetic and real-world data and compare performance with two standard approaches for community detection and ranking extraction. We find that the algorithm accurately retrieves the overall node's preference in different scenarios, and we show that it can distinguish small subsets of nodes that behave differently than the majority. As a consequence, the model can recognize whether a network has an overall preferred interaction mechanism. This is relevant in situations where there is no clear "a priori" information about what structure explains the observed network datasets well. Our model allows practitioners to learn this automatically from the data.

| S-EPMC9151911 | biostudies-literature

Neural tracking of social hierarchies in adolescents’ real-world social networks

Project description: Not available

| S-EPMC10656574 | biostudies-literature

RANKING RELATIONS USING ANALOGIES IN BIOLOGICAL AND INFORMATION NETWORKS.

Project description:Analogical reasoning depends fundamentally on the ability to learn and generalize about relations between objects. We develop an approach to relational learning which, given a set of pairs of objects S = {A(1) : B(1), A(2) : B(2), …, A(N) : B(N)}, measures how well other pairs A : B fit in with the set S. Our work addresses the following question: is the relation between objects A and B analogous to those relations found in S? Such questions are particularly relevant in information retrieval, where an investigator might want to search for analogous pairs of objects that match the query set of interest. There are many ways in which objects can be related, making the task of measuring analogies very challenging. Our approach combines a similarity measure on function spaces with Bayesian analysis to produce a ranking. It requires data containing features of the objects of interest and a link matrix specifying which relationships exist; no further attributes of such relationships are necessary. We illustrate the potential of our method on text analysis and information networks. An application on discovering functional interactions between pairs of proteins is discussed in detail, where we show that our approach can work in practice even if a small set of protein pairs is provided.

| S-EPMC3935415 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data