I have a graph that contains two types of nodes: Companies and Persons.
A Company node has a list of edges that represent Shareholders. A Shareholder has a percentage of shares and is either a Company or a Person. A Person node is always a leaf.
Here's an example:
CompanyA has 50% of CompanyB's shares UserA has 50% of CompanyA's shares UserB has 50% of CompanyB's shares CompanyB has 50% of CompanyA's shares
The arrows could be reversed, depending on whether they represent shares or owners
Who in truth owns CompanyA and with what percentage. In this example, we should get that UserA owns 66.66% of CompanyA and UserB owns 33.33% of CompanyB.
This can be computed using a Transition Matrix and multiplying it by itself multiple times, like this.
Sadly, this is an estimate and requires quite a lot of iterations to get a very precise one. I suspect that there's a way to get a exact answer. I've looked at eigenvalues but I think my maths are failing me. In terms of matrices, I think I'm looking for the stable distribution of a transition matrix (or Markov Chain).
Perhaps I'm overcomplicating this? I feel like there should be a way to get this result without resolving to matrices and with a recursive algorithm. Especially considering that the graph contains a lot of leaves and that I am only interested in the shareholders of a single company (the "root" of the graph).
I will implement the final solution in Java. Third party libraries can be used.