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

🕗 发布于 2024-07-25 07:47 算法池化网格搜索适应度和聚类比较节点度图密度

🎯要点

📜图算法用例

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

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

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

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

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

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

🍪语言内容分比

在这里插入图片描述

🍇Python和MATLAB异构网络算法

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

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

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

异构信息网络：

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

它的网络模式：

在这里插入图片描述

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

算法

谱聚类的关键步骤是构建高质量的相似度矩阵 $S$ 。对于异构信息网络，元路径已被有效地用于测量对象相似性。例如，给定元路径 $P$ ，PathSim测量两个对象 $x_u$ 和 $x_v$ 之间的相似度。 $P$ 通过计算连接两个对象的 $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|} .$
给定一组元路径 $PS$ ，每个元路径 $_i \in P S$ 根据上式导出相似性矩阵 $S_{ P _i}$ 。我们构造一个矩阵 $W$ 作为以下各项的加权和：矩阵：
$W=\sum_{i=1}^{| P S |} \lambda_i S_{ P _i} .$

优化

由于约束 $\operatorname{rank}\left(L_S\right)=n-k$ ，优化问题是非凸的。因此很难直接优化问题。我们将原问题转化为：
$\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}$
其中 $\sigma_i\left(L_S\right)$ 表示 $L_S$ 的第 $i$ 个最小特征值。由于 $L_S$ 是半定的， $\sigma_i\left(L_S\right)\geq 0$ 。通过设置较大的 $\gamma$ 值，我们将 $\sum_{i=1}^k \sigma_i\left(L_S\right)$ 强制为零，以保证 $\operatorname{rank}\left(L_S\right) )=n-k$ 。根据凯-范定理，我们有，
$\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)$
其中 $\operatorname{tr}(\cdot)$ 是跟踪运算符。因此优化问题等价于：
$\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伪代码实现算法：

from sklearn.cluster import KMeans
import numpy as np
from scipy.optimize import minimize

class alg:
    def __init__(self, similarity_matrices, num_clusters, random_seed=0):
        
        self.num_clusters = num_clusters
        self.random_seed = random_seed
        self.num_nodes = None
        self.similarity_matrices = []
        self.metapath_index = {}
        self.alpha = None
        self.beta = None
        self.gamma = None

        for index, (metapath, matrix) in enumerate(similarity_matrices.items()):
            if self.num_nodes is None:
                self.num_nodes = matrix.shape[0]
            
            if matrix.shape != (self.num_nodes, self.num_nodes):
                raise ValueError('Invalid shape of similarity matrix.')

            row_normalized_matrix = matrix/matrix.sum(axis=1, keepdims=True)
            
            self.similarity_matrices.append(row_normalized_matrix)
            self.metapath_index[metapath] = index

        self.similarity_matrices = np.array(self.similarity_matrices)
        self.num_metapaths = len(similarity_matrices)
        

    def run(self, verbose=False, cluster_using='similarity'):
        
        if cluster_using not in ['similarity', 'laplacian']:
            raise ValueError('Invalid option for parameter \'cluster_using\'.')

        similarity_matrix, metapath_weights = self.optimize(verbose=verbose)

        if cluster_using == 'similarity':
            labels = self.cluster(similarity_matrix)

        elif cluster_using == 'laplacian':
            laplacian = normalized_laplacian(similarity_matrix)
            labels = self.cluster(eigenvectors(laplacian, num=self.num_clusters))

        metapath_weights_dict = {metapath: metapath_weights[index] for metapath, index in self.metapath_index.items()}
        
        return labels, similarity_matrix, metapath_weights_dict
    
    
    def cluster(self, feature_matrix):
        return KMeans(self.num_clusters, n_init=10, random_state=self.random_seed).fit_predict(feature_matrix)


    def optimize(self, num_iterations=20, alpha=0.5, beta=10, gamma=0.01, verbose=False):
        self.alpha = alpha
        self.beta = beta
        self.gamma = gamma
        lambdas = np.ones(self.num_metapaths)/self.num_metapaths
        W = np.tensordot(lambdas, self.similarity_matrices, axes=[[0], [0]])
        S = W

        for iteration in range(num_iterations):
            
            if verbose:
                loss = np.trace(np.matmul((S - W).T, (S - W))) 
                loss += self.alpha * np.trace(np.matmul(S.T, S))
                loss += self.beta * np.dot(lambdas, lambdas)
                loss += self.gamma * np.sum(eigenvalues(normalized_laplacian(S), num=self.num_clusters))

                print('Iteration %d: Loss = %0.3f' % (iteration, loss))

            F = self.optimize_F(S)
            S = self.optimize_S(W, F)
            lambdas = self.optimize_lambdas(S, lambdas)
            W = np.tensordot(lambdas, self.similarity_matrices, axes=[[0], [0]])

        return S, lambdas

    def optimize_F(self, S):
        LS = normalized_laplacian(S)    
        return eigenvectors(LS, num=self.num_clusters)

    def optimize_S(self, W, F):
        Q = distance_matrix(F, metric='euclidean')
        P = (2*W - self.gamma*Q)/(2 + 2*self.alpha)

        S = np.zeros((self.num_nodes, self.num_nodes)) 
        for index in range(S.shape[0]):
            S[index] = best_simplex_projection(P[index])
        
        return S

    def optimize_lambdas(self, S, init_lambdas):
        def objective(lambdas):
            W = np.tensordot(lambdas, self.similarity_matrices, axes=[[0], [0]])
            value = np.trace(np.matmul(W.T, W))
            value -= 2 * np.trace(np.matmul(S.T, W))
            value += self.beta * np.dot(lambdas, lambdas)
            return value
    
        def constraints():
            def sum_one(lambdas):
                return np.sum(lambdas) - 1

            return  {
                'type': 'eq',
                'fun': sum_one,
            }

        def bounds(init_lambdas):
            return [(0, 1) for init_lambda in init_lambdas]

        return minimize(objective, init_lambdas, method='SLSQP', constraints=constraints(), bounds=bounds(init_lambdas)).x

MATLAB伪代码算法实现：

function [y, S, evs, A] = alg(mp_matrix, c, true_cluster)

NITER = 20;
zr = 10e-11;

alpha = 0.5; 
beta = 10; 
gamma = 0.01; 

P = size(mp_matrix,1);
n = size(mp_matrix,2);
lambda = ones(P,1)./P;

eps = 1e-10;
A0 = zeros(n,n);
for p = 1:P
    A0 = A0 + lambda(p) * squeeze(mp_matrix(p,:,:));
end;

A0 = A0-diag(diag(A0));
A10 = (A0+A0')/2;
D10 = diag(sum(A10));
L0 = D10 - A10;

[F0, ~, evs]=eig1(L0, n, 0);
F = F0(:,1:c);
[pred] = postprocess(F,c,true_cluster);

for iter = 1:NITER
    dist = L2_distance_1(F',F');
    S = zeros(n);
    for i=1:n
        a0 = A0(i,:);
        idxa0 = 1:n;
        ai = a0(idxa0);
        di = dist(i,idxa0);
        ad = (ai-0.5*gamma*di)/(1+alpha); S(i,idxa0) = EProjSimplex_new(ad);
    end;
    A = S;
    A = (A+A')/2;
    D = diag(sum(A));
    L = D-A;
    F_old = F;
    [F, ~, ev]=eig1(L, c, 0);
    [pred] = postprocess(F,c,true_cluster);
    evs(:,iter+1) = ev;

    fn1 = sum(ev(1:c));
    fn2 = sum(ev(1:c+1));
    
    lambda_old = lambda;
    
    if fn1 > zr
        gamma = 2*gamma;
        lambda =  optimizeLambda(mp_matrix, S, beta); % optimize lambda
    elseif fn2 < zr
        gamma = gamma/2;  F = F_old; lambda = lambda_old;
    else
        break;
    end;
    
    A0 = zeros(n,n);
    for p = 1:P
        A0 = A0 + lambda(p) * squeeze(mp_matrix(p,:,:));
    end;

end;

[clusternum, y]=graphconncomp(sparse(A)); y = y';
nmi = calculateNMI(y,true_cluster);
purity = eval_acc_purity(true_cluster,y);
ri = eval_rand(true_cluster,y);

fprintf('Final NMI is %f\n',nmi);
fprintf('Final purity is %f\n',purity);
fprintf('Final rand is %f\n',ri);

if clusternum ~= c
    sprintf('Can not find the correct cluster number: %d', c)
end;

👉参阅、更新：计算思维 | 亚图跨际

原文地址：https://blog.csdn.net/jiyotin/article/details/140667659

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：C#使用csvhelper实现csv的操作
下一篇：如果提升服务器安全性，使用快卫士给服务器上“锁”

百度搜索AI探索版多线程批量生成TXT原创文章软件-可生成3种类型文章
8、有8种标题模式可自由设置：1、关键词 2、百度搜索AI原创标题(以原创标题写文章) 3、关键词 + 百度搜索AI原创标题 4、关键词 + 下拉副标题 5、关键词 + 下拉副标题
阅读更多2024-11-16
批量更改表格数据不更新、不实时渲染、或则watch监听不到表格修改数据
第一种方法是监听的watch中添加deep:true，但是这种方法对我来说不管用，我需要监听某一列的数据，在批量更改后，统计数量，这时候，手动更改数据，他的监听并不能实时抓捕到。我这里的功能是，批量更
阅读更多2024-11-16
【大语言模型】ACL2024论文-10 CSCD-IME: 纠正拼音输入法产生的拼写错误
本文研究了中文拼写校正（CSC）任务，特别是针对拼音输入法（IME）产生的错误。作者首先介绍了一个包含40,000个标注句子的中文拼写校正数据集（CSCD-IME），这些句子来自新浪微博上的官方媒体帖
阅读更多2024-11-16
react 中 memo 模块作用
memo`是一个用于优化组件性能的高阶组件。
阅读更多2024-11-16
随笔content1
如果组件的具体类型无法获得，或者你并不关心组件的具体类型，那么可以使用 ComponentPublicInstance。当你将一个响应式对象的属性赋值或解构到一个本地变量时，访问或赋值该变量是非响应式
阅读更多2024-11-16
Java多线程底层设计思路
Java 的多线程设计比较全面和灵活，提供了多种方式来定义任务和管理线程，特别是通过Runnable和Callable接口，可以实现任务和线程的解耦，适应不同的应用场景。与 Python 和 C# 相
阅读更多2024-11-16
第七章利用CSS和多媒体美化页面
当设置为show时，就意味着当表格中某个单元格没有内容时，依然会显示该单元格的边框，这样可以保持表格的完整性和视觉上的连贯性，让用户在浏览表格时，能清晰地看到每个单元格的范围。而当参数为hide时，则
阅读更多2024-11-16
Cyberchef配合Wireshark提取并解析TCP/FTP流量数据包中的文件
通过cyberchef还原pcap数据包中TCP上层的文件内容，提升wireshark分析数据包的效率
阅读更多2024-11-16
redis
Redis 本质上是一个 Key-Value 类型的内存数据库，整个数据库加载在内存当中进行操作，定期通过异步操作把数据库数据 flush 到硬盘上进行保存。因为是纯内存操作， Redis 的性能
阅读更多2024-11-16
C++学习笔记之string容器、vector容器
vector可以动态扩展，动态扩展并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间。我们读过的书，说过的话，见过的山水，见到的人和事，最终都会变成我们脚下的的路。
阅读更多2024-11-16

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

🎯要点

📜图算法用例

🍪语言内容分比

🍇Python和MATLAB异构网络算法

算法

优化

👉参阅、更新：计算思维 | 亚图跨际

相关文章