Точный алгоритм вычисления долей бенефициарного владения в ориентированных графах на основе марковских цепей и сильно связных компонент
Аннотация
Задача точного вычисления долей бенефициарного владения в крупномасштабных ориентированных графах с циклами является актуальной проблемой анализа корпоративных сетей. Существующие подходы либо не учитывают циклические структуры владения, либо имеют высокую вычислительную сложность, что делает их неприменимыми к реальным данным. В работе предложен новый алгоритм, сводящий задачу к последовательному вычислению персонализированного PageRank внутри сильно связных компонент графа с последующей агрегацией результатов вдоль ациклической конденсации. Доказана корректность алгоритма и его линейная вычислительная сложность O(m) по числу рёбер на этапе предобработки, что позволяет анализировать графы с десятками миллионов вершин и связей. Экспериментальная валидация проведена на реальных данных: глобальной базе ORBIS (40 млн записей), реестре лиц со значительным контролем Великобритании (PSC, 4 млн) и данных ФНС России (2 млн). Результаты подтверждают высокую точность и масштабируемость метода. Дополнительно исследованы структурные характеристики корпоративных графов (распределение размеров сильно связных компонент, длина цепочек владения), влияющие на производительность алгоритма.
Литература
2. Karpoff J.M. The future of financial fraud. Journal of Corporate Finance. 2021;66:101694. https://doi.org/10.1016/j.jcorpfin.2020.101694
3. Garcia-Bernardo J., Fichtner J., Takes F.W., Heemskerk E.M. Uncovering Offshore Financial Centers: Conduits and Sinks in the Global Corporate Ownership Network. Scientific Reports. 2017;7:6246. https://doi.org/10.1038/s41598-017-06322-9
4. Brin S., Page L. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems. 1998;30(1-7):107-117. https://doi.org/10.1016/S0169-7552(98)00110-X
5. Vitali S., Glattfelder J.B., Battiston S. The Network of Global Corporate Control. PLoS ONE. 2011;6(10):e25995. https://doi.org/10.1371/journal.pone.0025995
6. Mizuno T., Doi S., Kurizaki S. The power of corporate control in the global ownership network. PLoS ONE. 2020;15(8):e0237862. https://doi.org/10.1371/journal.pone.0237862
7. Lukashevich A., Bulkin A., Maximov Y. A-priori reduction of scenario approximation for automated generation control in high-voltage power grids with renewable energy. IEEE Control Systems Letters. 2024;8:1613-1618. https://doi.org/10.1109/LCSYS.2024.3413367
8. Gambarelli G., Owen G. Indirect control of corporations. International Journal of Game Theory. 1994;23(4):287-302. https://doi.org/10.1007/BF01242945
9. Langville A.N., Meyer C.D. Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press; 2006. 224 p.
10. Garas A., Schweitzer F., Havlin S. A k-shell decomposition method for weighted networks. New Journal of Physics. 2012;14:083030. https://doi.org/10.1088/1367-2630/14/8/083030
11. Jeh G., Widom J. Scaling personalized web search. In: Proceedings of the 12th international conference on World Wide Web (WWW '03). New York, NY, USA: Association for Computing Machinery; 2003. p. 271-279. https://doi.org/10.1145/775152.775191
12. Tarjan R. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing. 1972;1(2):146-160. https://doi.org/10.1137/0201010
13. McLendon W., Hendrickson B., Plassmann P. Finding strongly connected components in parallel. In: Proceedings of the 1998 International Conference on Parallel and Distributed Processing Techniques and Applications. 1998;2:822-829.
14. Stach I., Mercik J. Measurement of control power in corporate networks. Operations Research and Decisions. 2021;31(1):97-121. https://doi.org/10.37190/ord210106
15. Anikin A., Gasnikov A., Gornov A., Kamzolov D., Maximov Y., Nesterov Y. Efficient Numerical Methods to Solve Sparse Linear Equations with Application to PageRank. Optimization Methods and Software. 2022;37(3):907-935. https://doi.org/10.1080/10556788.2020.1858297
16. Chapelle O., Mehrotra R. Robust PageRank and its applications. In: Proceedings of the 9th ACM International Conference on Web Search and Data Mining, 2016. p. 339-348.
17. Gleich D.F. PageRank Beyond the Web. SIAM Review. 2015;57(3):321-363. https://doi.org/10.1137/140976649
18. Cohen M.B., Kelner J., Peebles J., Peng R., Rao A.B., Sidford A., Vladu A. Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017). New York, NY, USA: Association for Computing Machinery; 2017. p. 410-419. https://doi.org/10.1145/3055399.3055463
19. Bahmani B., Chowdhury A., Goel A. Fast incremental and personalized PageRank. Proceedings of the VLDB Endowment. 2010;4(3):173-184. https://doi.org/10.14778/1929861.19298
20. Shamolin M.V. Foundations of Differential and Topological Diagnostics. Journal of Mathematical Sciences. 2003;114(1):976-1024. https://doi.org/10.1023/A:1021807110899
21. Polovnikov K., Pospelov N., Skougarevskiy D. α-Indirect Control in Onionlike Networks. arXiv:2109.07181, 2021. https://doi.org/10.48550/arXiv.2109.07181
22. Meyer C.D. Matrix Analysis and Applied Linear Algebra. SIAM; 2000. 730 p.
23. Garlaschelli D., Battiston S., Castri M., Servedio V.D.P., Caldarelli G. The scale-free topology of market investments. Physica A: Statistical Mechanics and its Applications. 2005;350(2-4):491-499. https://doi.org/10.1016/j.physa.2004.11.040
24. Heemskerk E.M., Takes F.W. The corporate elite community structure of global capitalism. New Political Economy. 2016;21(1):90-118. https://doi.org/10.1080/13563467.2015.1041483
25. Song D.-M., Jiang Z.-Q., Zhou W.-X. Statistical properties of world investment networks. Physica A: Statistical Mechanics and its Applications. 2009;388(12):2450-2460. https://doi.org/10.1016/j.physa.2009.03.004
26. Romei A., Ruggieri S., Turini F. The layered structure of company share networks. In: 2015 IEEE International Conference on Data Science and Advanced Analytics (DSAA). Paris, France: IEEE Press; 2015. p. 1-10. https://doi.org/10.1109/DSAA.2015.7344809
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
