自动机与社区检测相关研究

### 自动机与社区检测相关研究 #### 1. 自动机相关问题 在自动机领域，有一些重要的问题和结论。 - **Ext DFA - SW - |问题**：Theorem 27将Ext Hitting Set的一个实例转换为Ext DFA - SW - |的一个实例，结合相关研究证明了Ext DFA - SW - |是W[3] - 困难的，这使其超出了另一个很少被提及的复杂度类。并且这种构造也可适用于TTSPL自动机图。 - **DFA - MSS问题**： - **问题定义**：输入为带有输入字母表Σ的DFA A和k ∈ N，问题是是否存在一个子字母表ˆΣ ⊆ Σ，|ˆΣ| ≤ k，使得A在ˆΣ上的限制是可同步的，即是否存在一个关于ˆΣ的同步字。 - **复杂度结论**：DFA - MSS是W[2] - 困难的。同时，虽然没有给出证明，但有结论表明DFA - MSS包含在WNL ∩ W[P]中。不过，它是否属于A[2]以及是否是WNL - 困难的还未可知，也有可能是W[Sync] - 困难的。 #### 2. 社区检测相关概念与算法 社区检测问题在多个领域广泛存在，从社交网络分析到生物蛋白质 - 蛋白质相互作用等。传统的社区检测算法基于同一社区内节点更易相互连接的假设。然而，现实世界中的社区存在更复杂的重叠情况。 - **多层随机块模型**： - **单层随机块模型**：如G(n, n1, p, q) (p > q)，可看作带社区的Erd˝os - R´enyi模型，同一社区内节点对形成边的概率为p，不同社区节点对形成边的概率为q。 - **多层随机块模型**：提出的G(n, n1, p1, ..., nL, pL)模型，每层l由nl个不相交的社区组成，不同层的社区相互独立，每层l有一个边概率pl，决定该层社区内节点对形成边的概率。 - **两层随机块模型示例**：以G(200, 4, 5, p1, p2)为例，层1有四个社区，层2有五个社区，且各社区按Erd˝os - R´enyi图建模，不同层社区存在重叠。 - **隐藏社区与HICODE算法**： - **隐藏社区**：是一个新的图论概念，指大部分节点也属于其他更强社区（通过模块化等指标衡量）的社区。 - **HICODE算法**：用于检测包含强弱层社区的网络中的隐藏社区。该算法通过交替使用单一层网络的社区检测算法A检测剩余图中的最强层，并对已发现的层进行缩减。缩减方法有三种： - **RemoveEdge**：移除层l的所有内部边。 - **R