运筹学在复杂网络社团结构分析中的应用

社团结构研究是复杂网络这一前沿领域中的重要问题,同运筹学有着密切的关联。本文介绍了传统社团结构问题的基本定义,以及最近十年通过应用运筹学理论对该问题的研究进展。这些进展包括启发式模型,到随后的概率优化模型,以及组合优化模型。通过这些介绍,说明了运筹学方法论和基本工具在复杂系统研究中所起到的重要作用。     

A weight’s agglomerative method for detecting communities in weighted networks based on weight’s similarity

This paper proposes the new definition of the community structure of the weighted networks that groups of nodes in which the edge's weights distribute uniformly but at random between them. It can describe the steady connections between nodes or some similarity between nodes' functions effectively. In order to detect the community structure efficiently, a threshold coefficient κ to evaluate the equivalence of edges' weights and a new weighted modularity based on the weight's similarity are proposed. Then, constructing the weighted matrix and using the agglomerative mechanism, it presents a weight's agglomerative method based on optimizing the modularity to detect communities. For a network with n nodes, the algorithm can detect the community structure in time O(n²log₂ⁿ). Simulations on networks show that the algorithm has higher accuracy and precision than the existing techniques. Furthermore, with the change of κ the algorithm discovers a special hierarchical organization which can describe the various steady connections between nodes in groups.     

Community detection in signed networks based on discrete-time model

Community detection in signed networks has been studied widely in recent years. In this paper, a discrete difference equation is proposed to imitate the consistently changing phases of the nodes. During the interaction, each node will update its phase based on the difference equation. Each node has many different nodes connected with it, and these neighbors have different influences on it. The similarity between two nodes is applied to describe the influences between them. Nodes with high positive similarities will get together and nodes with negative similarities will be far away from each other.Communities are detected ultimately when the phases of the nodes are stable. Experiments on real world and synthetic signed networks show the efficiency of detection performance. Moreover, the presented method gains better detection performance than two existing good algorithms.     

民族旅游社区妇女的时间利用方式——以四川省桃坪羌寨为例

西部民族社区在旅游开发中由传统封闭的生活空间迅速转变为开放的旅游接待场所.在该转变过程中,当地妇女的时间利用方式受到旅游开发的深远影响,而现有旅游研究并未给予过多关注.以四川桃坪羌寨为例,利用时间日志和半结构访谈法获取当地妇女的时间利用数据,在与未参与旅游妇女的对比中,研究参与旅游妇女的时间利用行为.结果表明,参与旅游妇女劳动时间的增长挤压了其生活和休闲时间;旅游开发使得参与旅游妇女扮演“双重角色”,进而承担“双重劳动”;社区旅游为参与旅游妇女协调家庭传统角色和新角色提供了有效途径.     

Detecting community structure using label propagation with consensus weight in complex network

Community detection is a fundamental work to analyse the structural and functional properties of complex networks.The label propagation algorithm(LPA) is a near linear time algorithm to find a good community structure. Despite various ubsequent advances, an important issue of this algorithm has not yet been properly addressed. Random update orders within the algorithm severely hamper the stability of the identified community structure. In this paper, we executed the asic label propagation algorithm on networks multiple times, to obtain a set of consensus partitions. Based on these onsensus partitions, we created a consensus weighted graph. In this consensus weighted graph, the weight value of the dge was the proportion value that the number of node pairs allocated in the same cluster was divided by the total number f partitions. Then, we introduced consensus weight to indicate the direction of label propagation. In label update steps,y computing the mixing value of consensus weight and label frequency, a node adopted the label which has the maximum mixing value instead of the most frequent one. For extending to different networks, we introduced a proportion parameter o adjust the proportion of consensus weight and label frequency in computing mixing value. Finally, we proposed an pproach named the label propagation algorithm with consensus weight(LPAcw), and the experimental results showed that he LPAcw could enhance considerably both the stability and the accuracy of community partitions.     

A preliminary investigation on the topology of Chinese and climate networks

Complex networks have been studied across many fields of science in recent years. In this paper, we give a brief introduction of networks, then follow the original works by Tsonis et al (2004, 2006) starting with data of the surface temperature from 160 Chinese weather observations to investigate the topology of Chinese climate networks. Results show that the Chinese climate network exhibits a characteristic of regular, almost fully connected networks, which means that most nodes in this case have the same number of links, and so-called super nodes with a very large number of links do not exist there. In other words, though former results show that nodes in the extratropical region provide a property of scale-free networks, they still have other different local fine structures inside. We also detect the community of the Chinese climate network by using a Bayesian technique; the effective number of communities of the Chinese climate network is about four in this network. More importantly, this technique approaches results in divisions which have connections with physics and dynamics; the division into communities may highlight the aspects of the dynamics of climate variability.     

Properties of asymmetrically evolved community networks

This paper studies a simple asymmetrically evolved community network with a combination of preferential attachment and random properties. An important issue about community networks is to discover the different utility increments of two nodes, where the utility is introduced to investigate the asymmetrical effect of connecting two nodes. On the other hand, the connection of two nodes in community networks can be classified as two nodes belonging to the same or to different communities. The simulation results show that the model can reproduce a power-law utility distribution P(u)～u^-σ, σ = 2 + 1/p, which can be obtained by using mean-field approximation methods. Furthermore, the model exhibits exponential behaviour with respect to small values of a parameter denoting the random effect in our model at the low-utility region and a power-law feature with respect to big values of this parameter at the high-utility region, which is in good agreement with theoretical analysis. This kind of community network can reproduce a unique utility distribution by theoretical and numerical analysis.     

浙江天台山华顶杜鹃的群落学研究

以浙江天台山特有种华顶杜鹃为研究对象,分析了它所在群落的结构、物种组成及数量特征.在该群落中,华顶杜鹃不占优势,优势种群为阔叶箬竹、黄山松、山和金钱松等,它们的年龄结构都属于稳定型或增长型.群落垂直结构完整,可分为乔木层、灌木层、草本层,亦有一定数量的层间植物.乔木层的物种多样性偏低,灌木层和草本层的物种多样性较高.各样地间的植物种类相似性较高.华顶杜鹃处于濒危状态,必须采取措施加以保护.     

Joint Detection of Community and Structural Hole Spanner of Networks in Hyperbolic Space

Community detection and structural hole spanner (the node bridging different communities) identification, revealing the mesoscopic and microscopic structural properties of complex networks, have drawn much attention in recent years. As the determinant of mesoscopic structure, communities and structural hole spanners discover the clustering and hierarchy of networks, which has a key impact on transmission phenomena such as epidemic transmission, information diffusion, etc. However, most existing studies address the two tasks independently, which ignores the structural correlation between mesoscale and microscale and suffers from high computational costs. In this article, we propose an algorithm for simultaneously detecting communities and structural hole spanners via hyperbolic embedding (SDHE). Specifically, we first embed networks into a hyperbolic plane, in which, the angular distribution of the nodes reveals community structures of the embedded network. Then, we analyze the critical gap to detect communities and the angular region where structural hole spanners may exist. Finally, we identify structural hole spanners via two-step connectivity. Experimental results on synthetic networks and real networks demonstrate the effectiveness of our proposed algorithm compared with several state-of-the-art methods.     

A Useful Criterion on Studying Consistent Estimation in Community Detection

In network analysis, developing a unified theoretical framework that can compare methods under different models is an interesting problem. This paper proposes a partial solution to this problem. We summarize the idea of using a separation condition for a standard network and sharp threshold of the Erdös–Rényi random graph to study consistent estimation, and compare theoretical error rates and requirements on the network sparsity of spectral methods under models that can degenerate to a stochastic block model as a four-step criterion SCSTC. Using SCSTC, we find some inconsistent phenomena on separation condition and sharp threshold in community detection. In particular, we find that the original theoretical results of the SPACL algorithm introduced to estimate network memberships under the mixed membership stochastic blockmodel are sub-optimal. To find the formation mechanism of inconsistencies, we re-establish the theoretical convergence rate of this algorithm by applying recent techniques on row-wise eigenvector deviation. The results are further extended to the degree-corrected mixed membership model. By comparison, our results enjoy smaller error rates, lesser dependence on the number of communities, weaker requirements on network sparsity, and so forth. The separation condition and sharp threshold obtained from our theoretical results match the classical results, so the usefulness of this criterion on studying consistent estimation is guaranteed. Numerical results for computer-generated networks support our finding that spectral methods considered in this paper achieve the threshold of separation condition.