An Exact Algorithm for Computing Beneficial Ownership Shares in Directed Graphs Based on Markov Chains and Strongly Connected Components
Abstract
The problem of accurately computing beneficial ownership shares in large-scale directed graphs with cycles is a relevant challenge in corporate network analysis. Existing approaches either fail to account for cyclic ownership structures or have high computational complexity, which makes them inapplicable to real-world data. This paper proposes a new algorithm that reduces the problem to the sequential computation of personalized PageRank within strongly connected components of a graph, followed by aggregation of the results along an acyclic condensation graph. The correctness of the algorithm is proved, as well as its linear computational complexity of O(m) with respect to the number of edges at the preprocessing stage, which makes it possible to analyze graphs containing tens of millions of vertices and ownership links. Experimental validation was carried out on real-world data: the global ORBIS database with 40 million records, the United Kingdom People with Significant Control register with 4 million records, and data from the Federal Tax Service of Russia with 2 million records. The results confirm the high accuracy and scalability of the proposed method. In addition, the structural characteristics of corporate graphs, including the distribution of strongly connected component sizes and the length of ownership chains, are examined, as these characteristics affect the performance of the algorithm.
References
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
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
