A BRIEF INTRODUCTION TO SCALE‐FREE NETWORKS

ABSTRACT. This article provides a brief introduction to scale‐free networks. The notion of a scale‐free network is defined and some examples given. Properties frequently exhibited by scale‐free networks are discussed. The importance of the phenomenon of preferential attachment in generating scale‐free networks is illustrated with two examples for the spread of a persistent disease. The models are similar in that they both yield a total infected population (1) which is geometrically distributed, and growing exponentially in expectation; and (2) in which the average distance from the original source of infection grows in a similar way over time. However one model, which has preferential attachment (infection), yields a scale‐free network, while the other which has homogeneous infectivity does not. The possible application of the theory of scale‐free networks to resource management is briefly discussed.     

Comments to “Quantification of network structural dissimilarities” published by Schieber et al

Recently, we came across the paper entitled “Quantification of network structural dissimilarities” published by Nature Communications. In this paper, Schieber et al claimed to propose a novel technique for measuring the structural similarity of networks. The authors of this commentary are familiar with this special area of network analysis. After reading the paper, we doubt that the graph similarity (distance) measure due to Schieber et al is entirely novel. Instead, parts thereof are very similar to contributions we have authored. Unfortunately, they have not been cited nor acknowledged in Schieber et al.     

Synchronization of a growing chaotic network model

Synchronization in large ensembles of coupled interacting units is a fundamental phenomenon, which is helpful for the understanding of working mechanisms in neuronal networks, social network, etc. In this paper, we will investigate the synchronization phenomenon in a network model. A feedback control scheme is proposed for the synchronization of the given complex networks. The obtained result indicates that synchronization can be achieved for growing chaotic network model. Method enhance the synchronizability of the given model are given at the same time. Finally, numerical simulations are given to show the effectiveness of obtained results.     

The Share-a-Ride Problem: People and parcels sharing taxis

New city logistics approaches are needed to ensure efficient urban mobility for both people and goods. Usually, these are handled independently in dedicated networks. This paper considers conceptual and mathematical models in which people and parcels are handled in an integrated way by the same taxi network. From a city perspective, this system has a potential to alleviate urban congestion and environmental pollution. From the perspective of a taxi company, new benefits from the parcel delivery service can be obtained. We propose two multi-commodity sharing models. The Share-a-Ride Problem (SARP) is discussed and defined in detail. A reduced problem based on the SARP is proposed: the Freight Insertion Problem (FIP) starts from a given route for handling people requests and inserts parcel requests into this route. We present MILP formulations and perform a numerical study of both static and dynamic scenarios. The obtained numerical results provide valuable insights into successfully implementing a taxi sharing service.     

Triple-loop networks with arbitrarily many minimum distance diagrams

Minimum distance diagrams are a way to encode the diameter and routing information of multi-loop networks. For the widely studied case of double-loop networks, it is known that each network has at most two such diagrams and that they have a very definite form (“L-shape”).In contrast, in this paper we show that there are triple-loop networks with an arbitrarily big number of associated minimum distance diagrams. For doing this, we build-up on the relations between minimum distance diagrams and monomial ideals.     

Classification of Structural Complexity for Mine Ventilation Networks

The mine ventilation system is most important and technical measure for ensuring safety production in mines. The structural complexity of a mine ventilation network can directly affect the safety and reliability of the underground mining system. Quantitatively justifying the degree of complexity can contribute to providing a deeper understanding of the essential characteristics of a network. However, so far, there is no such a model which is able to simply, practically, reasonably, and quantitatively determine or compare the structural complexity of different ventilation networks. In this article, by analyzing some typical parameters of a mine ventilation network, we conclude that there is a linear functional relationship among five key parameters (number of ventilation network branches, number of nodes, number of independent circuits, number of independent paths, and number of diagonal branches). Correlation analyses for the main parameters of ventilation networks are conducted based on SPSS. Based on these findings, a new evaluation model for the structural complexity of ventilation network (which is represented by C) has been proposed. By combining SPSS classification analyses results with the characteristics of mine ventilation networks, standards for the complexity classification of mine ventilation systems are put forward. Using the developed model, we carried out analyses and comparisons for the structural complexity of ventilation networks for typical mines. Case demonstrations show that the classification results correspond to the actual situations. © 2014 Wiley Periodicals, Inc. Complexity 21: 21–34, 2015     

Modeling networked systems using the topologically distributed bounded rationality framework

In networked systems research, game theory is increasingly used to model a number of scenarios where distributed decision making takes place in a competitive environment. These scenarios include peer‐to‐peer network formation and routing, computer security level allocation, and TCP congestion control. It has been shown, however, that such modeling has met with limited success in capturing the real‐world behavior of computing systems. One of the main reasons for this drawback is that, whereas classical game theory assumes perfect rationality of players, real world entities in such settings have limited information, and cognitive ability which hinders their decision making. Meanwhile, new bounded rationality models have been proposed in networked game theory which take into account the topology of the network. In this article, we demonstrate that game‐theoretic modeling of computing systems would be much more accurate if a topologically distributed bounded rationality model is used. In particular, we consider (a) link formation on peer‐to‐peer overlay networks (b) assigning security levels to computers in computer networks (c) routing in peer‐to‐peer overlay networks, and show that in each of these scenarios, the accuracy of the modeling improves very significantly when topological models of bounded rationality are applied in the modeling process. Our results indicate that it is possible to use game theory to model competitive scenarios in networked systems in a way that closely reflects real world behavior, topology, and dynamics of such systems. © 2016 Wiley Periodicals, Inc. Complexity 21: 123–137, 2016     

A curved exponential family model for complex networks

Networks are being increasingly used to represent relational data. As the patterns of relations tends to be complex, many probabilistic models have been proposed to capture the structural properties of the process that generated the networks. Two features of network phenomena not captured by the simplest models is the variation in the number of relations individual entities have and the clustering of their relations. In this paper we present a statistical model within the curved exponential family class that can represent both arbitrary degree distributions and an average clustering coefficient. We present two tunable parameterizations of the model and give their interpretation. We also present a Markov Chain Monte Carlo (MCMC) algorithm that can be used to generate networks from this model.     

A genetic algorithm with local search strategy for improved detection of community structure

On the basis of modularity optimization, a genetic algorithm is proposed to detect community structure in networks by defining a local search operator. The local search operator emphasizes two features: one is that the connected nodes in a network should be located in the same community, while the other is “local selection” inspired by the mechanisms of efficient message delivery underlying the small‐world phenomenon. The results of community detection for some classic networks, such as Ucinet and Pajek networks, indicate that our algorithm achieves better community structure than other methodologies based on modularity optimization, such as the algorithms based on betweenness analysis, simulated annealing, or Tasgin and Bingol's genetic algorithm. © 2009 Wiley Periodicals, Inc. Complexity, 2010     

产学研合作创新网络规模、连接机制与创新绩效的关系研究——基于多主体仿真和动态系统论视角

为揭示产学研合作创新网络规模与连接机制对创新绩效的影响机理,运用Agent建模理论和Netlogo仿真平台构建产学研合作创新网络的仿真模型,对不同特性(小世界、无标度)偏好下的产学研合作创新网络进行仿真实验,并运用动态系统理论解释仿真的涌现现象。研究发现:①网络平均节点度(度数中心势)与网络平均创新绩效(节点加权平均收益的对数)之间存在鞍结分叉和跨临界分叉的组合现象;②网络平均距离(关系强度)与网络平均绩效之间呈指数增长分布轨道;③连接机制与网络平均绩效呈对数增长分布轨道;④实力择优连接机制提升网络平均节点度正向作用的效率较低;⑤随机组合择优连接机制更有利于提升小世界偏好网络平均距离的正向作用;⑥度择优连接机制更有利于提升无标度偏好网络平均创新绩效。     

The Role of Metanetworks in Network Evolution

The question of what structures of relations between actors emerge in the evolution of social networks is of fundamental sociological interest. The present research proposes that processes of network evolution can be usefully conceptualized in terms of a network of networks, or “metanetwork,” wherein networks that are one link manipulation away from one another are connected. Moreover, the geography of metanetworks has real effects on the course of network evolution. Specifically, both equilibrium and non-equilibrium networks located in more desirable regions of the metanetwork are found to be more probable. These effects of metanetwork geography are illustrated by two dynamic network models: one in which actors pursue access to unique information through “structural holes,” and the other in which actors pursue access to valid information by minimizing path length. Finally, I discuss future directions for modeling network dynamics in terms of metanetworks.     

A new formulation and an exact approach for the many-to-many hub location-routing problem

An important problem of the freight industry is the parcel delivery network design, where several facilities are responsible for assembling flows from several origins, re-routing them to other facilities where the flows are disassembled and the packages delivered to their final destinations. In order to provide this service, local tours are established for the vehicles assigned to each of the processing facilities, which are then responsible for the pickup and delivery tasks. This application gives rise to the many-to-many hub location routing problem that is the combination of two well known problems: the vehicle routing problem and the single assignment hub location problem. In this work, a new formulation for this important problem is proposed and solved by a specially tailored Benders decomposition algorithm. The proposed method is robust enough to solve instances up to 100 nodes having 4 million integer variables.     

On the economics of GPRS networks with Wi-Fi integration

Wi-Fi provides an appealing opportunity for GSM/GPRS operators to enhance their data capability. By integrating both networks, operators are able to provide 3G-like services. However, both networks have different data rates and capacity, which makes economics of the network integration and pricing of services a challenging issue. In this paper we introduce a novel pricing model for GPRS networks integrated with Wi-Fi networks. The model identifies how the integration can play a significant role in increasing operators’ overall revenue and potentially improve the performance of GPRS networks. We identify the optimal GPRS charging rate and Wi-Fi connection fee that yields maximum network revenue. In addition, we conduct a case study of a wireless operator that considers network integration, adopting our pricing model. The investment analysis provides the insightful information for profitable business cases of GPRS networks with Wi-Fi integration.     

尾部风险网络视角下的金融机构系统性风险贡献研究

金融机构的尾部风险关联模式及结构在金融系统性风险的形成演化中发挥重要作用。利用CoVaR指标及分位数回归方法,衡量金融机构之间的尾部风险传染强度,进而建立金融机构尾部风险动态网络。分析全连接网络及阈值法下过滤网络的全局和局部拓扑结构特征及其动态演化规律。建立面板数据回归模型,研究网络拓扑结构特征对金融机构系统性风险贡献的影响。实证研究发现,全连接网络的节点强度,能有效地衡量金融机构尾部风险传染强度及承受强度,并揭示其动态变化规律;各机构的尾部风险传染强度及承受强度排序匹配性存在差异;随着时间推进,各金融机构间的平均尾部风险传染路径缩短、系统性风险更易迅速累积和爆发;滞后一期的节点出度、节点入度及聚集系数越大,相应金融机构的系统性风险贡献越小;滞后一期的节点介数和节点接近中心度越大,相应金融机构的系统性风险贡献越大。研究结果对于金融机构的宏观审慎监管及系统性风险管理,提供了一个全新的基于金融机构尾部风险网络的视角。     

复杂疾病的分子网络模型研究

复杂疾病是危害人类健康的主要杀手.不同于单基因缺陷性遗传病,复杂疾病的发生发展与多个基因之间、基因与环境之间的相互作用有关,致病机理复杂,其早期诊断及治疗困难是21世纪生物医学研究的重大挑战之一.随着生物知识的不断积累和多层次"组学"数据的井喷式涌现,复杂疾病研究迎来了新的"组学革命",研究模式从以往的只关注某个分子扩展到对分子之间相互形成的生物分子网络的系统分析.作为系统生物学核心概念,生物分子网络系统整合大量生物知识和高通量生物数据,是研究复杂疾病的强有力工具.本文以分子网络为主线,以数学建模为工具来研究复杂疾病,针对复杂疾病关系和复杂疾病的发生发展机制等复杂疾病研究的关键热点问题,分析和集成高通量多层次组学数据,构建并求解生物分子网络的数学模型,在若干复杂疾病相关系统生物学问题中取得有生物学意义的结果.本文提出若干生物网络建模、分析及应用的方法并提供若干应用软件,为从系统层面理解复杂疾病提供重要参考;同时,网络模型在若干实例中的应用得到若干有生物学意义的结论,为揭示复杂疾病机理、推动疾病治疗与预防起到了一定的作用.     

快递企业航空货运网络的构建

快递业竞争激烈,构建高效合理的航空货运网络是快递企业提高竞争力的重要手段。“枢纽—辐射”式航空货运网络是整合航空快递资源、提高航空快递资源利用效率、提高快递企业竞争力的有效模式。本文以降低航空快递网络成本、加快航空快递处理时间为目标,从航空快递网络枢纽的选取、指派关系的确定、枢纽个数的选择三个方面研究了航空快递网络模型建立问题,选用遗传算法求解不同枢纽个数下航空快递网络的运输成本,并据此进行枢纽的选取,运用重力模型法进行指派关系的确定,在此基础上运用超效率DEA模型确定枢纽个数。接着,以包含17个节点的顺丰航空快递网络的规划为例,对本文所提出的模型和算法进行了验证,验证结果证实了模型的合理性。本文的研究为快递企业构建航空货运网络提供了科学实用的方法,该方法的使用可以降低航空货运成本,提高效率,从而提高快递企业的竞争力。     

Heuristics for vehicle routing on tree-like networks

This paper presents two new heuristics for the vehicle routing problem on tree-like road networks. These networks occur, for example, in rural road systems where the supply (or delivery) nodes are located on rural roads leading off from a few highways which form the ‘trunks’ of a tree-like network. The heuristics have the conventional objective of minimising the total distance travelled by the vehicles. The development of the heuristics takes advantage of the tree-like structure of the network. These two new heuristics and two other heuristics from the published literature are applied to some test problems and computational results are presented. The computational experience indicates that one of the new heuristics provides superior solutions to the existing heuristics and in reasonable computing time. It therefore appears suitable for large-scale practical routing problems.     

Option contracts: a solution for overloading problems in the delivery service supply chain

Owing to the limited service capacity of express delivery providers, most online retailers have to reject many orders during hot selling seasons. In this paper, we consider an express delivery service supply chain consisting of an express delivery provider and an online retailer whereby the selling season includes both regular periods and online sales periods. Utilizing a modified newsvendor model, we derive the express delivery provider’s optimal capacity decision and find that the overloading problem cannot be avoided because delivery service cannot be inventoried. To solve such a problem, we introduce an option contract to coordinate the supply chain. By allowing the online retailer to book the capacity, the express delivery provider can rent capacity from a third party in advance. Results show this approach can mitigate the problem significantly. We also extend our model to a supply chain consisting of a delivery provider and two retailers.     

The freight consolidation and containerization problem

In today’s global free market, third-party logistics providers (3PLs) are becoming increasingly important. This paper studies a problem faced by a 3PL operating a warehouse in Shanghai, China, under contract with a major manufacturer of children’s clothing based in the United States. At the warehouse, the 3PL receives textile parcel shipments from the suppliers located in China; each shipment is destined for different retail stores located across the United Sates. These shipments must be consolidated and loaded into containers of varying sizes and costs, and then sent along shipping routes to different destination ports. An express company, such as UPS and FedEx, unloads the shipments from the containers at the destination ports and distributes them to their corresponding stores or retailers by parcel delivery. The objective is to find an allocation that minimizes the total container transportation and parcel delivery costs. We formulate the problem into an integer programming model, and also propose a memetic algorithm approach to solve the problem practically. A demonstration of a good solution to this problem was a decisive factor in the awarding of the contract to the 3PL in question.     

A scale‐free network model for HIV transmission among men who have sex with men in China

Objective: The study aimed to analyze sexual networks and sex role preference as factors of HIV transmission among men who have sex with men (MSM) in China. Methods: We have developed a new scale‐free network model with a sex role preference framework to study HIV transmission among MSM. We have studied the influence of different sexual networks and the effect of different proportion of sex role preference upon HIV transmission. The results are that the average ones drawn from the scenarios have been simulated for more than 30 times. Results: Compared with the traditional mathematical model, the sexual networks provide a different prediction of the HIV transmission in the next 30 years. Without any intervention, the proportion of HIV carriers will descend after some time. Conclusions: There is significant associations among network characteristics, sex role preference, and HIV infection. Although network‐based intervention is efficient in reducing HIV transmission among MSM, there are only few studies of the characteristics of sexual network, and such gaps deserve more attention and exploration. Copyright © 2016 John Wiley & Sons, Ltd.