🍠Python鲁汶意外莱顿复杂图拓扑分解算法

LogoPython鲁汶意外莱顿复杂图拓扑分解算法 | 亚图跨际viadean on Notion
🏈指点迷津 | Brief

🎯要点

🎯算法池化和最佳分区搜索：🖊网格搜索 | 🖊发现算法池 | 🖊返回指定图的最佳划分 | 🖊返回指定图的最佳分区 | 🎯适应度和聚类比较功能：🖊图的划分 | 🖊节点度 | 🖊给定算法检测到社群总数 | 🖊图密度 | 🖊社群顶点的度数之和 | 🖊解之间的预期一致 | 🖊联合熵 | 🖊平均内部度、所有可能的节点对的平均路径长度 | 🖊节点指向社群外的边平均比例 | 🖊现有边距离社群比例 | 社群内部密度 | 🖊切割比率的标准化变体 | 🖊边超几何分布随机出现的统计方法 | 🖊兰德指数预测聚类之间的相似性度量 | 分区之间最佳匹配的平均 F1 分数 | 归一化互信息

📜图算法用例

📜Python群体趋向性潜关联有向无向多图层算法

📜Python和MATLAB网络尺度结构和幂律度大型图生成式模型算法

📜MATLAB和Python零模型社会生物生成式结构化图

📜Python莫兰生死抑制放大进化图

📜Python种群邻接矩阵彗星风筝进化图算法

​📜Python和C++骨髓细胞进化解析数学模型

🍪语言内容分比

🍇Python和MATLAB异构网络算法

异构信息网络是一种网络结构，其对象可以假设不同的对象类型，对象之间的链接可以表示对象之间的不同类型的关系。此网无处不在，用于对许多不同类型的现实世界数据进行建模。例如，社交软件开放图将用户、帖子、事件和页面建模为四种不同类型的对象。用户可以发布帖子、参加活动或喜欢页面，这说明了将用户对象与帖子相关联的三种不同类型的连接。

此网络数据分析一直是一个活跃的研究领域。作为机器学习和数据挖掘的一项基本任务，聚类分析在此网络中找到了有趣的应用。例如，根据社交软件用户的兴趣对其进行聚类，可以实现有效的目标营销和病毒式营销。

谱聚类将聚类转化为图分割问题，该问题优化衡量分割质量的某个标准，例如正则化切割。通常，给定一组对象 X={x1,x2,…,xn}X=\left\{x_1, x_2, \ldots, x_n\right\}，标准谱聚类方法首先构造一个无向图 G=(X,S)G=(X, S)，其中 XX 表示顶点集，SS 是一个矩阵，SijS_{i j} 度量对象xi x_i 和xj x_j 之间的相似性。然后，计算拉普拉斯矩阵LS L_S，在此基础上执行特征分解以获得与 k 个最小特征值相对应的 k 个特征向量，其中 kk 是所需的聚类数量。这些特征向量被用作对象的新特征空间。最后，应用后处理步骤，例如 kk 均值和光谱旋转将对象划分为k k 个聚类。

异构信息网络：

令 T={T1,…,Tm}T =\left\{T_1, \ldots, T_m\right\} 为一组 mm 对象类型。对于每种类型 TiT_i，令XiX _i 为类型 TiT_i 的对象集。 异构信息网络是一个图G=(V,E) G =( V , E )，其中 V=⋃i=1mXiV =\bigcup_{i=1}^m X _i 是一组节点，EE 是一组链接，每个链接代表一个二进制VV 中两个对象之间的关系。

它的网络模式：

网络模式是异构信息网络G=(V,E)G =( V , E ) 的元模板。令 (1) ϕ:V→T\phi: V \rightarrow T 为对象类型映射，将V V 中的对象映射为其类型，(2) ψ:E→R\psi: E \rightarrow R 为链接关系映射将E E 中的链接映射到一组关系 RR 中的关系。异构信息网络 GG 的网络模式用 TG=(T,R)T_{ G }=( T , R ) 表示，显示了不同类型的对象如何通过R R 中的关系进行关联。使用示意图来表示TGT_{G}，其中T和R分别为节点集和边集。具体来说，示意图中存在一条边 (Ti,Tj)\left(T_i, T_j\right) ，前提是 R 中存在将 TiT_i 类型的对象与 TjT_j 类型的对象相关联的关系。

算法

谱聚类的关键步骤是构建高质量的相似度矩阵S。对于异构信息网络，元路径已被有效地用于测量对象相似性。例如，给定元路径 PP，PathSim测量两个对象xu x_u 和 xvx_v 之间的相似度。P P 通过计算连接两个对象的 P 的路径实例的数量。具体来说，我们有，

SP(xu,xv)=2×∣{pxu⇝xv:pxu⇝xv⊢P}∣∣{pxu⇝xu:pxu→xu⊢P}∣+∣{pxv⇝xv:pxv⇝xv⊢P}∣S_{ P }\left(x_u, x_v\right)=\frac{2 \times\left|\left\{p_{x_u \rightsquigarrow x_v}: p_{x_u \rightsquigarrow x_v} \vdash P \right\}\right|}{\left|\left\{p_{x_u \rightsquigarrow x_u}: p_{x_u \rightarrow x_u} \vdash P \right\}\right|+\left|\left\{p_{x_v \rightsquigarrow x_v}: p_{x_v \rightsquigarrow x_v} \vdash P \right\}\right|}

给定一组元路径 PSP S，每个元路径 Pi∈PSP _i \in P S 根据上式导出相似性矩阵 SPiS_{ P _i}。我们构造一个矩阵 WW 作为以下各项的加权和：矩阵：

W=∑i=1∣PS∣λiSPiW=\sum_{i=1}^{| P S |} \lambda_i S_{ P _i}

优化

由于约束rank⁡(LS)=n−k\operatorname{rank}\left(L_S\right)=n-k，优化问题是非凸的。因此很难直接优化问题。我们将原问题转化为：

min⁡∥S−∑i=1∣PS∣λiSPi∥F2+α∥S∥F2+β∥λ∥22+2γ∑i=1kσi(LS), s.t. ∑j=1nSij=1,Sij≥0,∑i=1∣PS∣λi=1,λi≥0,\begin{aligned} & \min \left\|S-\sum_{i=1}^{| P S |} \lambda_i S_{ P _i}\right\|_F^2+\alpha\|S\|_F^2+\beta\| \lambda \|_2^2+2 \gamma \sum_{i=1}^k \sigma_i\left(L_S\right), \\ & \text { s.t. } \sum_{j=1}^n S_{i j}=1, S_{i j} \geq 0, \sum_{i=1}^{| P S |} \lambda_i=1, \lambda_i \geq 0, \end{aligned}

其中σi(LS)\sigma_i\left(L_S\right)表示LSL_S的第ii个最小特征值。由于LSL_S是半定的，σi(LS)≥0\sigma_i\left(L_S\right)\geq 0。通过设置较大的γ \gamma 值，我们将 ∑i=1kσi(LS)\sum_{i=1}^k \sigma_i\left(L_S\right) 强制为零，以保证 rank⁡(LS))=n−k\operatorname{rank}\left(L_S\right) )=n-k。根据凯-范定理，我们有，

∑i=1kσi(LS)=min⁡F∈Rn×k,FTF=Itr⁡(FTLSF)\sum_{i=1}^k \sigma_i\left(L_S\right)=\min _{F \in R ^{n \times k}, F^T F=I} \operatorname{tr}\left(F^T L_S F\right)

其中 tr⁡(⋅)\operatorname{tr}(\cdot) 是跟踪运算符。因此优化问题等价于：

min⁡∥S−∑i=1∣PS∣λiSPi∥F2+α∥S∥F2+β∥λ∥22+2γtr⁡(FTLSF), s.t. ∑j=1nSij=1,Sij≥0,∑i=1∣PS∣λi=1,λi≥0,F∈Rn×k,FTF=I,\begin{aligned} & \min \left\|S-\sum_{i=1}^{| P S |} \lambda_i S_{ P _i}\right\|_F^2+\alpha\|S\|_F^2+\beta\| \lambda \|_2^2+2 \gamma \operatorname{tr}\left(F^T L_S F\right), \\ & \text { s.t. } \sum_{j=1}^n S_{i j}=1, S_{i j} \geq 0, \sum_{i=1}^{| P S |} \lambda_i=1, \lambda_i \geq 0, F \in R ^{n \times k}, F^T F=I, \end{aligned}

Python伪代码实现算法：

MATLAB伪代码算法实现：

PreviousPython药物副作用生物图分析算法和矩阵降维算法NextPython群体趋向性潜关联有向无向多图层算法

Last updated

Was this helpful?