Computational Complexity of SRIC and LRIC Indices

P. 49–70.

Швыдун С. В.

Over the past years, there is a deep interest in the analysis of different communities and complex networks. Identification of the most important elements in such networks is one of the main areas of research. However, the heterogeneity of real networks makes the problem both important and problematic. The application of SRIC and LRIC indices can be used to solve the problem since they take into account the individual properties of nodes, the possibility of their group influence, and topological structure of the whole network. However, the computational complexity of such indices needs further consideration. Our main focus is on the performance of SRIC and LRIC indices. We propose several modes on how to decrease the computational complexity of these indices. The runtime comparison of the sequential and parallel computation of the proposed models is also given.

Ключевые слова: Computational Complexity, group influence, Influence in networks, Short-range interaction centrality, Long-range interaction centrality, Simple paths

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Принятие решений и анализ данных в социально-экономических и политических системах (2020)

В книге

Network Algorithms, Data Mining, and Applications. Springer Proceedings in Mathematics & Statistics

Vol. 315. , Springer, 2020.