Achieving spectral localization of network using betweenness-based edge perturbation
- PDF / 1,095,677 Bytes
- 9 Pages / 595.276 x 790.866 pts Page_size
- 66 Downloads / 179 Views
ORIGINAL ARTICLE
Achieving spectral localization of network using betweenness‑based edge perturbation Debasis Mohapatra1 · Soubhagya Ranjan Pradhan1 Received: 14 July 2019 / Revised: 13 August 2020 / Accepted: 17 August 2020 © Springer-Verlag GmbH Austria, part of Springer Nature 2020
Abstract Graph is a simple but effective way to represent a complex system, where a node represents a component of the system and edge represents connection between the components. Several insights can be inferred by analyzing such graphs. In this field, optimization of spread and localization are relatively a new research domain. The objective of the spread problem is to maximize the influence, whereas localization controls the diffusion. In this paper, our focus is on the eigenvector localization of the network adjacency matrix using inverse participation ratio (IPR). In this context, we propose betweenness centralitybased perturbation (BP) to localize the network. The results show that the BP approach achieves a better localization than the existing random perturbation (RP) approach. It shows maximum IPR than RP. The performance of the approaches is evaluated using threshold rate of diffusion (τ), number of modifications and IPR. Susceptible–infected–susceptible model is used to investigate the τ value. Keywords Perturbation · Eigenvector localization · Betweenness centrality Abbreviations IPR Inverse participation ratio SIS Susceptible–infected–susceptible SIR Susceptible–infected–recovered SI Susceptible–infected RP Random perturbation BP Betweenness centrality-based perturbation τ Rate of diffusion (threshold) NM Number of modifications PEV Principal eigenvector LEV Largest eigenvalue IPR* Optimal IPR BC Betweenness centrality
* Debasis Mohapatra [email protected] Soubhagya Ranjan Pradhan [email protected] 1
Parala Maharaja Engineering College, Berhampur 761003, India
1 Introduction Graph theory, being a proven modeling approach, is used to model different complex systems like biological system, social system, chemical system, etc. In biological system, the graph structure is used to show different types of interactions like protein–protein interaction, cell–cell interaction, etc. In social system, the graph represents the connections between the social entities. In chemical system, the connections between the molecules are represented by a graph. On analyzing such types of graphs, several hidden/unknown insights about the system’s behaviors and characteristics can be disclosed. Also, some logical reasons can be established in understanding some peculiar phenomena. Diffusion of information in the network is an interesting problem; it investigates the selection of seed set that maximizes the diffusion in the network. This is applicable for effective advertisement, where the selection of an efficient seed set maximizes the popularity of a product. Also, in biological networks, selection of seed set of proteins that maximizes the influence is important because the drug target can be fixed accordi
Data Loading...
