Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Sensitivity of complex networks measurements

Full text
Boas, P. R. Villas [1] ; Rodrigues, F. A. [2] ; Travieso, G. [1] ; Costa, L. da F. [1]
Total Authors: 4
[1] Univ Sao Paulo, Inst Phys Sao Carlos, BR-13560970 Sao Carlos, SP - Brazil
[2] Univ Sao Paulo, Inst Ciencias Matemat & Computacao, Dept Matemat Aplicada & Estatist, BR-13560970 Sao Paulo - Brazil
Total Affiliations: 2
Document type: Journal article
Web of Science Citations: 4

Complex networks obtained from real-world networks are often characterized by incompleteness and noise, consequences of imperfect sampling as well as artifacts in the acquisition process. Because the characterization, analysis and modeling of complex systems underlain by complex networks are critically affected by the quality and completeness of the respective initial structures, it becomes imperative to devise methodologies for identifying and quantifying the effects of the sampling on the network structure. One way to evaluate these effects is through an analysis of the sensitivity of complex network measurements to perturbations in the topology of the network. In this paper, measurement sensibility is quantified in terms of the relative entropy of the respective distributions. Three particularly important kinds of progressive perturbations to the network are considered, namely, edge suppression, addition and rewiring. The measurements allowing the best balance of stability (smaller sensitivity to perturbations) and discriminability (separation between different network topologies) are identified with respect to each type of perturbation. Such an analysis includes eight different measurements applied on six different complex networks models and three real-world networks. This approach allows one to choose the appropriate measurements in order to obtain accurate results for networks where sampling bias cannot be avoided-a very frequent situation in research on complex networks. (AU)

FAPESP's process: 05/00587-5 - Mesh (graph) modeling and techniques of pattern recognition: structure, dynamics and applications
Grantee:Roberto Marcondes Cesar Junior
Support type: Research Projects - Thematic Grants