计算公司的股东所有权百分比

Question

我有一个包含两种类型节点的图表:公司和人员.

公司节点具有代表股东的边缘列表.股东拥有一定比例的股份,是公司或个人.Person节点始终是叶子.

这是一个例子:

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

箭头可以颠倒,这取决于它们是代表股票还是所有者

谁真的拥有CompanyA和百分比.在这个例子中,我们应该得到UserA拥有CompanyA的66.66%而UserB拥有CompanyB的33.33%.

这可以使用转换矩阵计算,并将其自身乘以多次,如下所示.

遗憾的是,这是一个估计,需要相当多的迭代才能获得非常精确的迭代.我怀疑有办法得到一个确切的答案.我看过特征值,但我认为我的数学失败了.就矩阵而言,我认为我正在寻找转移矩阵(或马尔可夫链)的稳定分布.

也许我过于复杂了？我觉得应该有一种方法来获得这个结果而不用解析矩阵和递归算法.特别是考虑到图表包含大量的叶子,我只对单个公司的股东感兴趣(图的"根").

我将用Java实现最终的解决方案.可以使用第三方库.

谢谢!

Answer 1

我假设你的矩阵的标签或多或少是这样的

   cA  cB  uA  uB
cA 0    0.5 0.5 0
cB 0.5  0   0   0.5
uA 0    0   1   0
uB 0    0   0   1

其中，cA/B 表示公司 A/B，uA/B 表示用户 A/B。

我们将该矩阵表示为A。那么这个表达式(1, 0, 0, 0).A就给出了A公司“投资”1“单位”后立即的“资源分配”。在这种情况下，结果确实是(0, 0.5, 0.5, 0)，即B公司获得50%，用户A也获得50%。然而，归属于B公司的资源会进一步“传播”，因此为了找到“均衡”分布，我们需要计算

(1, 0, 0, 0).A^n

n在趋于无穷大的极限中。就左特征向量而言，原始矩阵A可以重写（假设它可对角化）为A=Inverse[P].w.P，其中w是包含特征值的对角矩阵。然后一个有

A^n = (Inverse[P].w.P)^n = Inverse[P].w^n.P

1, 1, 0.5, -0.5在这种特殊情况下，当特征值n趋于无穷大时，只有特征值1保留下来。因此 的极限w^n是DiagonalMatrix[{1,1,0,0}]。因此最终结果可以写为

Inverse[P].DiagonalMatrix[{1,1,0,0}].P

这产生

0.  0.  0.666667    0.333333
0.  0.  0.333333    0.666667
0.  0.  1.  0.
0.  0.  0.  1.

最后，特征值1对应的特征向量为(0, 0, 1, 0)和(0, 0, 0, 1)。其含义是，如果一个人“投资”1单位资源给用户A/B，则相应的用户“保留一切”并且没有任何东西进一步传播，即已经达到均衡。由于有两个用户（叶子），因此特征值会双重退化。