Estimating Graph Robustness Through the Randic Index.

08:00 EDT 31st October 2017 | BioPortfolio

Summary of "Estimating Graph Robustness Through the Randic Index."

Graph robustness--the ability of a graph to preserve its connectivity after the loss of nodes and edges--has been extensively studied to quantify how social, biological, physical, and technical systems withstand to external damages. In this paper, we prove that graph robustness can be quickly estimated through the Randic index, a parameter introduced in chemistry to study organic compounds. We prove that Erdos-Renyj (ER) graphs are a good specimen of robust graphs because they lack of a clear modular structure; we derive an analytical expression for the Randic index of ER graphs and use ER graphs as an effective term of comparison to decide about graph robustness. Experiments on real datasets from different domains (scientific collaboration networks, content-sharing systems, co-purchase networks from an e-commerce platform, and a road network) show that real-life large graphs are more robust than ER ones with the same number of nodes and edges. We also observe that if node degree distribution closely follows a power law, then few edges contribute for more than half of the Randic index, thus indicating that the selective removal of those edges has devastating impact on graph robustness. Finally, we describe sampling-based algorithms to efficiently but accurately approximate the Randic index.


Journal Details

This article was published in the following journal.

Name: IEEE transactions on cybernetics
ISSN: 2168-2275


DeepDyve research library

PubMed Articles [5209 Associated PubMed Articles listed on BioPortfolio]

The minimal-ABC trees with B1-branches.

The atom-bond connectivity index (or, for short, ABC index) is a molecular structure descriptor bridging chemistry to graph theory. It is probably the most studied topological index among all numerica...

Intraoperative Renal Resistive Index as an Acute Kidney Injury Biomarker: Development and Validation of an Automated Analysis Algorithm.

Intraoperative Doppler-determined renal resistive index (RRI) is a promising early acute kidney injury (AKI) biomarker. As RRI continues to be studied, its clinical usefulness and robustness in resear...

The robustness of T value as a trabecular structural index at multiple spatial resolutions of 7 Tesla MRI.

To evaluate the robustness of MR transverse relaxation times of trabecular bone from spin-echo and gradient-echo acquisitions at multiple spatial resolutions of 7 T.

A Flow Procedure for Linearization of Genome Sequence Graphs.

Efforts to incorporate human genetic variation into the reference human genome have converged on the idea of a graph representation of genetic variation within a species, a genome sequence graph. A se...

Iterative Graph Seeking for Object Tracking.

To effectively solve the challenges in object tracking, such as large deformation and severe occlusion, many existing methods use graph-based models to capture target part relations, and adopt a seque...

Clinical Trials [1757 Associated Clinical Trials listed on BioPortfolio]

An Open Study to Assess the Robustness of the CRC749 Inhaler

To confirm the robustness of the CRC749 inhaler.

Fetal and Maternal Head Circumference During Pregnancy in Israeli Population

In this study, measurements of fetal and maternal head circumference will be collected. This data will be presented in table or graph form. The effect of maternal head circumference on fet...

Novel Equation for Estimating Resting Energy Expenditure

The energy and nutrition states are closely associated with CKD patients complications and outcomes.To reach the energy balance target, we need the accurate resting energy expenditure leve...

Monitoring ANS Activity by Utilization of the Combined Physiological Activity Index (CPAI)

A clinical trial to validate the MCPM (Multi-parameter Combined Physiological Signal-based Monitoring), in estimating autonomic nervous system activity level, at rest and while exposed to ...

Evaluation of the Accuracy, Safety and Robustness of a Single-Input-Single-Output (SISO) Model-Based Predictive Closed-Loop System to Guide Patient-Individualized ICU Sedation

The aim of this study is to investigate the accuracy, safety and robustness of a single-input-single output (SISO) model-based predictive closed-loop system to guide patient-individualized...

Medical and Biotech [MESH] Definitions

A combination of the debris index and the dental calculus index to determine the status of oral hygiene.

An index which scores the degree of dental plaque accumulation.

Statistical models which describe the relationship between a qualitative dependent variable (that is, one which can take only certain discrete values, such as the presence or absence of a disease) and an independent variable. A common application is in epidemiology for estimating an individual's risk (probability of a disease) as a function of a given risk factor.

Work consisting of a subject approach to the contents of a periodical issuing an annual, biennial, quinquennial, decennial, etc., index. The heading is used for the overall body of articles published by a periodical in the same sense that BIBLIOGRAPHY is useful when published as a single article.

The number of RETICULOCYTES per unit volume of BLOOD. The values are expressed as a percentage of the ERYTHROCYTE COUNT or in the form of an index ("corrected reticulocyte index"), which attempts to account for the number of circulating erythrocytes.

Quick Search


DeepDyve research library

Relevant Topics

Biological Therapy
Biological therapy involves the use of living organisms, substances derived from living organisms, or laboratory-produced versions of such substances to treat disease. Some biological therapies for cancer use vaccines or bacteria to stimulate the body&rs...

Biotechnology Business
Alliances Astrazeneca Bioethics Boehringer Clinical Research Organization Collaborations GSK Johnson & Johnson Lilly Merck Mergers and Acquisitions Nexium Novartis Pfizer Roche Sanofi ...

Searches Linking to this Article