基于在线社交网络的JPS跳跃并行顶点采样方法

针对现有在线社交网络（OSNs）采样方法无法有效地应用于低连通性的社交网络，且采集的样本顶点平均度严重偏离原始社交网络、顶点过度采样等问题，本文基于蒙特卡罗随机游走（MHRW）采样方法，引入双重跳跃策略、并行机制和顶点缓存区，提出一种跳跃无偏并行顶点（JPS）采样方法。将在线社交网络数据集建模为包含顶点和边的社交图进行模拟采样，利用Python/Matplotlib绘图库绘制采集的样本顶点属性图。实验结果表明,该采样方法更有效地应用于不同连通强度的社交图，提高了采样过程中的顶点更新率，降低了样本顶点的平均度偏差且能够更快速地收敛。     

图聚类的算法及其在社会关系网络中的应用

研究图聚类的算法问题。在基于划分的图聚类中,重点比较点与点之间距离的计算方法及其对聚类结果的影响。由于社会关系网络图中点没有坐标值,所以不能使用欧几里得距离和曼哈坦距离。使用k-medoids聚类算法时,分别采用最短距离和随机漫步距离算法,将DBLP数据集构成的社会关系网络图分类成各个子图,通过实验数据验证两种算法的优劣。实验证明最短距离算法获得聚类效果更为理想,达到了较好的分类效果。     

增量网络监测点的增量选取算法

针对网络拓扑结构扩充后,原有网络中布置的监测点不易变动的问题,提出一种增量网络监测点的增量选取算法。该算法优化了以网络中顶点的度数作为贪心选择策略求解图的弱顶点覆盖的贪心算法,从而得到更少顶点的近似解。在计算增量网络监测点集时,该算法只利用新增网络拓扑得出新增网络的监测点集,求得的增量监测点可直接加入到原网监测点集合中得到新的全网监测点集,降低重新布置全网监测点的成本。实验结果表明,增量算法得到的全网监测点集与在全新的网络中重新计算得到的全网监测点集的顶点数基本相同,可有效应用于实际的网络监测点部署。     

Protecting shared information in networks: A network security game with strategic attacks

A digital security breach, by which confidential information is leaked, does not only affect the agent whose system is infiltrated but is also detrimental to other agents socially connected to the infiltrated system. Although it has been argued that these externalities create incentives to underinvest in security, this presumption is challenged by the possibility of strategic adversaries that attack the least protected agents. In this paper we study a new model of security games in which agents share tokens of sensitive information in a network of contacts. The agents have the opportunity to invest in security to protect against an attack that can be either strategically or randomly targeted. We show that, in the presence of random attack, underinvestments always prevail at the Nash equilibrium in comparison with the social optimum. Instead, when the attack is strategic, either underinvestments or overinvestments are possible, depending on the network topology and on the characteristics of the process of the spreading of information. Actually, agents invest more in security than socially optimal when dependencies among agents are low (which can happen because the information network is sparsely connected or because the probability that information tokens are shared is small). These overinvestments pass on to underinvestments when information sharing is more likely (and therefore, when the risk brought by the attack is higher). In order to keep our analysis tractable, some of our results on strategic attacks make an assumption of homogeneity in the network, namely, that the network is vertex‐transitive. We complement these results with an analysis on star graphs (which are nonhomogeneous), which confirms that the essential lines of our findings can remain valid on general networks.     

二进制递归网络的连通性

二进制递归网络是超立方体的一类特殊变体,它具有很多良好的网络特性。网络的连通性是衡量网络结构通信能力的一个重要性能,虽然到目前为止已知的一些二进制递归网 络的连通性都已被研究过,但这些研究只是针对个体进行的,并不能代表所有二进制递归网络的连通特性。本文通过证明任何一个二进制递归网络中的每对顶点之间只能存在在”条顶点不交路,得到了整个二进制递归网络的点和边连通度皆为”的重要结论。     

Global stabilization of complex networks with digraph topologies via a local pinning algorithm

This paper concerns the global stability of controlling a complex network with digraph topology to a homogeneous trajectory of the uncoupled system by the local pinning control algorithm. The derived stability condition indicates that the smallest real part of eigenvalues of the Laplacian sub-matrix corresponding to the unpinned vertices can be used to measure the stabilizability of a digraph with a given pinned vertex set. A pinned vertex set can stabilize a directed network to some unstable trajectories, for instance, to a chaotic trajectory of the uncoupled systems, if and only if the pinned vertex set can access all other vertices in the digraph. Furthermore, in the bigraph case, the analytical estimation of the stabilizability’s lower bound suggests that an optimal pinning strategy should take not only the vertex degree, but also the shortest path between pairs of vertices into considerations.     

Groupies in random graphs

A groupie in a graph G is a vertex whose valency is not less than the average of the valencies of its neighbours. We show that in a random graph, the proportion of the vertices which are groupies is almost always very near to 1/2.     

一种随机游走中心性的快速算法

自然网络都具有一定的聚簇结构, 聚簇之间的节点称之为桥节点, 桥节点对网络的流通性有着重要的作用。发现桥节点, 能够找到网络最为脆弱的部分。在随机游走中心性的基础上, 提出一种计算网络桥节点的快速算法。通过人工合成以及在自然网络上进行实验, 结果表明算法能够很好地发现各种网络的桥节点。     

基于模块度增量的二分网络社区挖掘算法

针对二分网络的社区挖掘问题,提出了一种基于模块度增量的二分网络社区挖掘算法。该算法假设每个顶点独自构成一个社区,并具有自己的标号。其中,一部分顶点将自己的标号复制并传递到另一部分中的某个顶点上,使之与其位于同一个社区;另一部分的顶点实施同样的操作。如此反复迭代,直至收敛。标号传播时,选择模块度增量最大的边进行传送,使整体模块度不断提高。在真实数据集上进行的测试表明,所提算法能对二分网络进行高质量的社区划分。     

Finding Minimum Vertex Covering in Stochastic Graphs: A Learning Automata Approach

Structural and behavioral parameters of many real networks such as social networks are unpredictable, uncertain, and have time-varying parameters, and for these reasons, deterministic graphs for modeling such networks are too restrictive to solve most of the real-network problems. It seems that stochastic graphs, in which weights associated to the vertices are random variables, might be better graph models for real-world networks. Once we use a stochastic graph as the model for a network, every feature of the graph such as path, spanning tree, clique, dominating set, and cover set should be treated as a stochastic feature. For example, choosing a stochastic graph as a graph model of an online social network and defining community structure in terms of clique, the concept of a stochastic clique may be used to study community structures’ properties or define spreading of influence according to the coverage of influential users; the concept of stochastic vertex covering may be used to study spread of influence. In this article, minimum vertex covering in stochastic graphs is first defined, and then four learning, automata-based algorithms are proposed for solving a minimum vertex-covering problem in stochastic graphs where the probability distribution functions of the weights associated with the vertices of the graph are unknown. It is shown that through a proper choice of the parameters of the proposed algorithms, one can make the probability of finding minimum vertex cover in a stochastic graph as close to unity as possible. Experimental results on synthetic stochastic graphs reveal that at a certain confidence level the proposed algorithms significantly outperform the standard sampling method in terms of the number of samples needed to be taken from the vertices of the stochastic graph.     

An Efficient Algorithm for Finding All Hinge Vertices on Trapezoid Graphs

The distance between at least two vertices becomes longer after the removal of a hinge vertex. Thus a faulty hinge vertex will increase the overall communication cost in a network. Therefore, finding the set of all hinge vertices in a graph can be used to identify critical nodes in a real network. An O(n log n) time algorithm has been proposed here to find all hinge vertices of a trapezoid graph with n vertices.     

一种P2P环境下点割集的被动分布式发现算法

P2P系统的可靠性主要取决于覆盖网节点问的连通性,而割点和小规模点割集对网络连通性的危害很大,它们的失效或离开能使覆盖网变得四分五裂。本文提出一种P2P环境下点割集的被动分布式发现算法,在无法获得网络全局信息的情况下,节点仅依靠对收到消息的统计和分析就能够自主判断自己是否为割点或属于2点割,并采取相应措施消除其为系统带来的不稳定因素。该算法准确性高、开销低,割集消除对提高覆盖网可靠性的效果显著。     

一种基于邻居信息的最大派系过滤算法

最大派系问题(Maximal Clique Problem, MCP)是组合优化中经典而重要的问题之一,在信息抽取、信号传输、计算机视觉、社会网络及生物信息学等众多领域有着重要的应用。学者们根据不同的思想策略,提出了许多方法求解最大派系问题,如分支定界、遗传算法、模拟退火、交又嫡及DNA方法等。现根据派系的部居信息提出一种基于派系邻接顶点和邻接边的派系过滤算法。算法从一个已知派系(初始为一个单独顶点)出发,每次考察派系的部接顶点,并以派系的邻接边为基础,扩展已有派系而得到更大的派系。用两个大规模的科学家合作网络对提出的算法进行了分析,并讨论了大规模社会网络中的派系分布情况。实验表明,提出的算法可有效地抽取网络中的最大派系。     

On Dissemination Thresholds in Regular and Irregular Graph Classes

We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if p < \frac12p<\frac{1}{2} . We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p.     

A new DSATUR-based algorithm for exact vertex coloring

This paper describes a new exact algorithm PASS for the vertex coloring problem based on the well known DSATUR algorithm. At each step DSATUR maximizes saturation degree to select a new candidate vertex to color, breaking ties by maximum degree w.r.t. uncolored vertices. Later Sewell introduced a new tiebreaking strategy, which evaluated available colors for each vertex explicitly. PASS differs from Sewell in that it restricts its application to a particular set of vertices. Overall performance is improved when the new strategy is applied selectively instead of at every step. The paper also reports systematic experiments over 1500 random graphs and a subset of the DIMACS color benchmark.     

Ranking weighted clustering coefficient in large dynamic graphs

Efficiently searching top-k representative vertices is crucial for understanding the structure of large dynamic graphs. Recent studies show that communities formed by a vertex with high local clustering coefficient and its neighbours can achieve enhanced information propagation speed as well as disease transmission speed. However, local clustering coefficient, which measures the cliquishness of a vertex in its local neighbourhood, prefers vertices with small degrees. To remedy this issue, in this paper we propose a new ranking measure, weighted clustering coefficient (WCC) of vertices, by integrating both local clustering coefficient and degree. WCC not only inherits the properties of local clustering coefficient but also approximately measures the density (i.e., average degree) of its neighbourhood subgraph. Thus, vertices with higher WCC are more likely to be representative. We study efficiently computing and monitoring top-k representative vertices based on WCC over large dynamic graphs. To reduce the search space, we propose a series of heuristic upper bounds for WCC to prune a large portion of disqualifying vertices from the search space. We also develop an approximation algorithm by utilizing Flajolet-Martin sketch to trade acceptable accuracy for enhanced efficiency. An efficient incremental algorithm dealing with frequent updates in dynamic graphs is explored as well. Extensive experimental results on a variety of real-life graph datasets demonstrate the efficiency and effectiveness of our approaches.     

A dynamic fault-tolerant message routing algorithm for double-loop networks

Message routing is a fundamental function of a network, and fault-tolerance is an important tool to ensure the quality of service of a network. Assume that the network contains at most one faulty element and the algorithm does not know the faulty element in advance. We present an optimal fault-tolerant message routing algorithm for double-loop networks. We show that sending at most two messages with different routing strategies can ensure that one of the messages will be sent through a shortest path that avoids the faulty element. At each vertex, for any destination, the algorithm needs only constant time and space to determine the next vertex to which the message is to be sent.     

Delivery reliability of computer networks for data transmission within the permitted packet error rate and latency

From the viewpoint of quality of service, packet error rate (PER) and latency are both critical performance indicators to assess internet quality for supervisor and customers. A computer system is usually modeled as a network topology with arcs and vertices where each arc denotes a delivery medium and each vertex denotes an Internet data center. Each component (arc and vertex) of a network should be considered as multi-state owing to the failure, partial failure, maintenance, etc., of the components. Evaluating the delivery reliability of a network with imperfect vertices is a complicated process. This type of network, called a multi-state imperfect vertex computer network, is addressed in this paper. We study how data can be delivered through multiple minimal paths simultaneously within the permitted PER and latency. An algorithm is proposed to assess delivery reliability. To show the efficiency and effectiveness of the proposed solution, we implemented the proposed solution on practical computer networks.     

Predicting unobserved links in incompletely observed networks

In this paper we consider networks in which the links (edges) are imperfectly observed. This may be a result of sampling, or it may be caused by actors (vertices) who are actively attempting to hide their links (edges). Thus the network is incompletely observed, and we wish to predict which of the possible unobserved links are actually present in the network. To this end, we apply a constrained random dot product graph (CRDPG) to rank the potential edges according to the probability (under the model) that they are in fact present. This model is then extended to utilize covariates measured on the actors, to improve the link prediction. The method is illustrated on a data set of alliances between nations, in which a subset of the links (alliances) is assumed unobserved for the purposes of illustration.