cutnorm 0.1.9

此包利用Alon和Noar [ALON2004]和Win和Yu^ {A2}的快速优化算法中的一些技术来计算矩阵的CuthFoad逼近。

阅读documentation。

安装

使用pip安装包。 从终端安装，如下所示：

$ pip install cutnorm

示例用法

给定两个简单图A和B的邻接矩阵，我们希望计算两个图之间的差分矩阵（A-B）的范数。与l1范数相比，使用割范数的一个明显优点是考虑Erdos-Renyi random graphs上范数的值。

给定两个常数n和p=0.5的erdos-renyi随机图，其差（归一化后）的编辑距离（l1范数）为0.5，概率较大。l1范数为1表示两个矩阵完全不同，0表示恒等式，0.5介于两者之间。然而，这两个图具有相同的全局结构。当n接近无穷大时，a和b收敛到同一个graphon对象，该对象在任何地方都是0.5。从lovasz[LOVASZ2009]所讨论的全局结构相似性的角度来看，编辑距离不能作为两个图之间的“距离”的概念。割范数是反映全局结构相似性的距离度量。事实上，这个例子中的差分割范数随着n的增长接近于0。

下面是使用cutnorm包和工具的示例。

importnumpyasnpfromcutnormimportcompute_cutnorm,tools# Generate Erdos Renyi Random Graph (Simple/Undirected)n=100p=0.5erdos_renyi_a=tools.sbm.erdos_renyi(n,p,symmetric=True)erdos_renyi_b=tools.sbm.erdos_renyi(n,p,symmetric=True)# Compute l1 normnormalized_diff=(erdos_renyi_a-erdos_renyi_b)/n**2l1=np.linalg.norm(normalized_diff.flatten(),ord=1)# Compute cutnormcutn_round,cutn_sdp,info=compute_cutnorm(erdos_renyi_a,erdos_renyi_b)print("l1 norm: ",l1)# prints l1 norm value near ~0.5print("cutnorm rounded: ",cutn_round)# prints cutnorm rounded solution near ~0print("cutnorm sdp: ",cutn_sdp)# prints cutnorm sdp solution near ~0