摘要
现实生活中许多系统都可以建模为复杂网络，以网络中的节点代表系统中的个体，网络中的连边代表个体之间的关系。近年来，复杂网络中的相关研究取得了较大进展，但对于部分特殊网络的研究仍有空缺。符号网络，作为一种特殊的复杂网络，其连边具有正负两种属性，可以额外描述网络中个体间的积极与消极关系，具有重要的研究意义与应用价值。论文以符号网络作为研究对象，先后研究了符号网络的结构平衡与鲁棒性两个问题，主要目的与研究内容如下: 结构平衡问题作为符号网络中最基本的问题之一而受到了广泛关注，该问题旨在寻找符号网络的一个划分，以使得划分中子集内的正属性边尽可能多，子集间的负属性边尽可能少。许多研究以数学规划为基础采用精确算法对结构平衡问题进行求解，这些算法运行速度较慢，面对大型网络难以在可接受的时间内给出问题的解。同时，也有一些适用于较大规模网络的智能优化算法被提出，但这些算法仍存在参数繁多、效率较低等问题。针对这一现状，论文设计了一种高效的迭代贪心算法用于快速求解结构平衡问题。该算法以一个两阶段的局部搜索策略为核心，使用构造性的启发式过程生成问题的初始解，借助破坏与重构算子增加解的多样性，并给出一些加速措施以提高算法的运行效率。与已有智能优化算法的对比实验结果表明，对于中小规模网络而言，论文提出的迭代贪心算法在执行效率上具有明显优势;对于大规模网络而言，该算法在计算时间与解的质量方面均优于已有的智能优化算法。 在快速求解结构平衡问题的基础上，论文进一步研究了符号网络的鲁棒性问题。网络鲁棒性问题在一般的复杂网络中得到了较为深入的研究，但推广至符号网络时存在一些困难，如经典的鲁棒性度量标准不适用于符号网络、基于度的攻击模型忽略了边的属性等，因而有关符号网络鲁棒性的研究较少。论文以求解结构平衡问题时得到的符号网络Fmstration指数为基准构建了衡量鲁棒性的指标，从节点的中心性度量标准出发建立了四种符号网络中的恶意攻击模型，并给出了符号网络中恶意攻击的流程。接下来，论文还以节点保护策略为例，分别设计了基于中心性度量标准和基于网络Frustration指数的两种贪心算法来选取部分节点进行保护以提高符号网络的鲁棒性。最后，论文通过真实网络数据集上的实验总结了符号网络中不同攻击模型的特点，验证了文中设计的贪心算法在提高网络鲁棒性方面的有效性。
NETL