A ubiquitous phenomenon in networks is the presence of communities within which the network connections are dense and between which they are sparser.This paper proposes a max-flow algorithm in bipartite networks to de...A ubiquitous phenomenon in networks is the presence of communities within which the network connections are dense and between which they are sparser.This paper proposes a max-flow algorithm in bipartite networks to detect communities in general networks.Firstly,we construct a bipartite network in accordance with a general network and derive a revised max-flow problem in order to uncover the community structure.Then we present a local heuristic algorithm to find the optimal solution of the revised max-flow problem.This method is applied to a variety of real-world and artificial complex networks,and the partition results confirm its effectiveness and accuracy.展开更多
Most of the existing opportunistic network routing protocols are based on some type of utility function that is directly or indirectly dependent on the past behavior of devices. The past behavior or history of a devic...Most of the existing opportunistic network routing protocols are based on some type of utility function that is directly or indirectly dependent on the past behavior of devices. The past behavior or history of a device is usually referred to as contacts that the device had in the past. Whatever may be the metric of history, most of these routing protocols work on the realistic premise that node mobility is not truly random. In contrast, there are several oracles based methods where such oracles assist these methods to gain access to information that is unrealistic in the real world. Although, such oracles are unrealistic, they can help to understand the nature and behavior of underlying networks. In this paper, we have analyzed the gap between these two extremes. We have performed max-flow computations on three different opportunistic networks and then compared the results by performing max-flow computations on history generated by the respective networks. We have found that the correctness of the history based prediction of history is dependent on the dense nature of the underlying network. Moreover, the history based prediction can deliver correct paths but cannot guarantee their absolute reliability.展开更多
The max-flow problem in planar networks with only edge capacities has been proved to be in NC (Nickle's Class). This paper considers a more general version of the problem when the nodes as well as the edges have c...The max-flow problem in planar networks with only edge capacities has been proved to be in NC (Nickle's Class). This paper considers a more general version of the problem when the nodes as well as the edges have capacities. In a general network, the node-edge-capacity problem can be easily reduced to the edge-capacity problem. But in the case of planar network this reduction may destroy the planarity, and reduces the problem to the edge-capacity problem in a general network, which is P-complete. A recent contribution presents a new reduction for planar networks, that maintains the planarity. In this paper, it is proved that this reduction is in NC and thus the node-edge-capacity problem in undirected planar networks is in NC. Keywords parallel algorithm - NC (Nickle's Class) algorithm, max-flow Supported by the National Basic Research 973 Program of China under Grant No.G1999032700.展开更多
针对在底层网络可能发生单点和单链路故障情况下的服务功能链(service function chain,SFC)映射问题,提出一种区分等级的可生存SFC映射方法,为提供重要服务的关键SFC预先分配备用资源,为提供普通服务的普通SFC快速重映射失效部分,从而...针对在底层网络可能发生单点和单链路故障情况下的服务功能链(service function chain,SFC)映射问题,提出一种区分等级的可生存SFC映射方法,为提供重要服务的关键SFC预先分配备用资源,为提供普通服务的普通SFC快速重映射失效部分,从而兼顾提高SFC可生存能力和降低底层网络资源开销的需求.首先,在考虑最小化SFC服务时延的条件下,分别为关键SFC和普通SFC的可生存映射问题建立混合整数线性规划模型.其次,提出2种启发式的模型求解算法,其中,面向关键SFC的主备服务路径构建算法采用贪心思想交替进行节点和链路映射,以减小SFC服务时延,并在主备服务路径之间建立桥接路径,以提高路径切换速度和降低路径切换过程的丢包率;面向普通SFC的失效服务路径重建算法引入最大流问题求解失效节点的最佳重映射位置,以提高成功恢复的失效普通SFC数目,并利用改进的Dijkstra最短路径算法选择时延低的重映射路径.最后,在不同网络条件下实验验证了启发式算法的性能,并且在模拟网络环境中所提可生存SFC映射方法能保证SFC的成功运行率在59.2%以上.展开更多
基金Supported by the National Natural Science Foundation of China under Grant No.11271006Shandong Provincial Natural Science Foundation under Grant No.ZR2012GQ002
文摘A ubiquitous phenomenon in networks is the presence of communities within which the network connections are dense and between which they are sparser.This paper proposes a max-flow algorithm in bipartite networks to detect communities in general networks.Firstly,we construct a bipartite network in accordance with a general network and derive a revised max-flow problem in order to uncover the community structure.Then we present a local heuristic algorithm to find the optimal solution of the revised max-flow problem.This method is applied to a variety of real-world and artificial complex networks,and the partition results confirm its effectiveness and accuracy.
文摘Most of the existing opportunistic network routing protocols are based on some type of utility function that is directly or indirectly dependent on the past behavior of devices. The past behavior or history of a device is usually referred to as contacts that the device had in the past. Whatever may be the metric of history, most of these routing protocols work on the realistic premise that node mobility is not truly random. In contrast, there are several oracles based methods where such oracles assist these methods to gain access to information that is unrealistic in the real world. Although, such oracles are unrealistic, they can help to understand the nature and behavior of underlying networks. In this paper, we have analyzed the gap between these two extremes. We have performed max-flow computations on three different opportunistic networks and then compared the results by performing max-flow computations on history generated by the respective networks. We have found that the correctness of the history based prediction of history is dependent on the dense nature of the underlying network. Moreover, the history based prediction can deliver correct paths but cannot guarantee their absolute reliability.
文摘The max-flow problem in planar networks with only edge capacities has been proved to be in NC (Nickle's Class). This paper considers a more general version of the problem when the nodes as well as the edges have capacities. In a general network, the node-edge-capacity problem can be easily reduced to the edge-capacity problem. But in the case of planar network this reduction may destroy the planarity, and reduces the problem to the edge-capacity problem in a general network, which is P-complete. A recent contribution presents a new reduction for planar networks, that maintains the planarity. In this paper, it is proved that this reduction is in NC and thus the node-edge-capacity problem in undirected planar networks is in NC. Keywords parallel algorithm - NC (Nickle's Class) algorithm, max-flow Supported by the National Basic Research 973 Program of China under Grant No.G1999032700.
文摘针对在底层网络可能发生单点和单链路故障情况下的服务功能链(service function chain,SFC)映射问题,提出一种区分等级的可生存SFC映射方法,为提供重要服务的关键SFC预先分配备用资源,为提供普通服务的普通SFC快速重映射失效部分,从而兼顾提高SFC可生存能力和降低底层网络资源开销的需求.首先,在考虑最小化SFC服务时延的条件下,分别为关键SFC和普通SFC的可生存映射问题建立混合整数线性规划模型.其次,提出2种启发式的模型求解算法,其中,面向关键SFC的主备服务路径构建算法采用贪心思想交替进行节点和链路映射,以减小SFC服务时延,并在主备服务路径之间建立桥接路径,以提高路径切换速度和降低路径切换过程的丢包率;面向普通SFC的失效服务路径重建算法引入最大流问题求解失效节点的最佳重映射位置,以提高成功恢复的失效普通SFC数目,并利用改进的Dijkstra最短路径算法选择时延低的重映射路径.最后,在不同网络条件下实验验证了启发式算法的性能,并且在模拟网络环境中所提可生存SFC映射方法能保证SFC的成功运行率在59.2%以上.
