java - 计算公司股东持股比例

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%。

这可以使用转换矩阵并将其乘以自身多次来计算，like this .

遗憾的是，这是一个估计值，需要大量迭代才能获得非常精确的值。我怀疑有一种方法可以获得准确的答案。我看过特征值，但我认为我的数学让我失望了。在矩阵方面，我想我正在寻找一个转移矩阵(或马尔可夫链)的稳定分布。

也许我把这个复杂化了？我觉得应该有一种方法可以在不解析矩阵和使用递归算法的情况下获得这个结果。特别是考虑到该图包含很多叶子，而且我只对一家公司的股东(图的“根”)感兴趣。

我将用 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 给我们“投资”1“单位”到公司 A 后的即时“资源分配”。在这种情况下，结果确实是 (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)。这意味着如果一个人向用户A/B“投入”1个单位的资源，对应的用户“保留一切”并且没有任何进一步传播，即已经达到平衡。由于有两个用户(叶子)，特征值会加倍退化。