分布式概率可逆过程建模自动机与社交网络中影响节点的寻找

# 分布式概率可逆过程建模自动机与社交网络中影响节点的寻找 ## 1. 分布式概率可逆过程建模自动机 ### 1.1 CPRA 概述 CPRA 能够在概率环境中对并发和可逆性进行建模，还具备对非确定性进行建模的能力。其实现的非确定性水平与 Pnueli - Zuck 概率自动机类似，但 Pnueli - Zuck 概率自动机没有合适的并行组合运算符。不同的并行组合运算符已被提出，虽并非主要针对 Pnueli - Zuck 概率自动机，但能与之兼容，不过这些运算符要么是同步的，要么在异步实现时依赖偏置因子。而 CPRA 消除了这些限制，提供了无需引入偏置因子的并行联合运算符。 ### 1.2 CPRA 的优势 - **并行组合**：CPRA 提供了并行联合运算符，且不引入偏置因子，解决了 Pnueli - Zuck 概率自动机在并行组合方面的不足。 - **概率分析**：和 Segla 概率自动机一样，CPRA 可以利用测度论的概念进行概率分析。 - **与其他类的区别**：CPRA 包含了内存，这使其与上述自动机所在的 PA 类有所不同。 - **形式化验证**：CPRA 可作为正式指定系统的一种手段，能在状态和输入符号上构建测试用例进行验证，一定程度上排除了使用如 LTL 或 CTL 等第三方逻辑来构建测试用例的需求。 ### 1.3 相关对比表格 | 自动机类型 | 并行组合运算符 | 概率分析 | 内存情况 | 测试用例构建 | | --- | --- | --- | --- | --- | | Pnueli - Zuck 概率自动机 | 无合适的 | - | - | - | | CPRA | 提供并行联合运算符，无偏置因子 | 可利用测度论 | 包含内存 | 可基于状态和输入符号，减少第三方逻辑使用 | | Segla 概率自动机 | - | 可利用测度论 | - | - | ## 2. 社交网络中寻找有影响力的节点 ### 2.1 社交网络与问题背景 社交互动网络可看作社交实体间的通信网络，是信息传播和影响力扩散的基础。在线社交网络在社会中愈发重要。在网络中传播影响力有诸多应用，比如在友谊网络中快速传播信息，目标是找到最小的初始种子集，使影响力在最短时间内传遍整个网络。这涉及到种子集大小和传播时间的权衡，就像病毒营销中，预算和传播时间相互制约。 ### 2.2 相关图论定义 - **支配集**：给定无向图 $G = (V, E)$，支配集是其顶点集 $V$ 的子集 $S$，使得任意节点 $v \in V$ 要么是 $S$ 中节点 $s$ 的邻居，要么 $v \in S$。寻找最小支配集是 NP 难问题，实际中常用近似算法或启发式方法求解。 - **k - 支配集**：给定无向图 $G = (V, E)$，k - 支配集是顶点集 $V$ 的子集 $S$，使得任意节点 $v \in V \setminus S$ 至少在 $S$ 中 $k$ 个节点的邻域内。 - **k - 跳支配集**：给定无向图 $G = (V, E)$，k - 跳支配集是顶点集 $V$ 的子集 $S$，使得任意节点 $v \in V \setminus S$ 至少在 $S$ 中一个节点 $s$ 的 $k$ 跳邻域 $N_k(s)$ 内。若图