Networks of strong ties

Social networks transmitting covert or sensitive information cannot use all ties for this purpose. Rather, they can only use a subset of ties that are strong enough to be “trusted”. This paper addresses whether it is still possible, under this restriction, for information to be transmitted widely and rapidly in social networks. We use transitivity as evidence of strong ties, requiring one or more shared contacts in order to count an edge as strong. We examine the effect of removing all non-transitive ties in two real social network data sets, imposing varying thresholds in the number of shared contacts. We observe that transitive ties occupy a large portion of the network and that removing all other ties, while causing some individuals to become disconnected, preserves the majority of the giant connected component. Furthermore, the average shortest path, important for the rapid diffusion of information, increases only slightly relative to the original network. We also evaluate the cost of forming transitive ties by modeling a random graph composed entirely of closed triads and comparing its connectivity and average shortest path with the equivalent Erdös–Renyi random graph. Both the empirical study and random model point to a robustness of strong ties with respect to the connectivity and small world property of social networks.     

Motifs in co-authorship networks and their relation to the impact of scientific publications

Co-authorship networks, where the nodes are authors and a link indicates joint publications, are very helpful representations for studying the processes that shape the scientific community. At the same time, they are social networks with a large amount of data available and can thus serve as vehicles for analyzing social phenomena in general. Previous work on co-authorship networks concentrates on statistical properties on the scale of individual authors and individual publications within the network (e.g., citation distribution, degree distribution), on properties of the network as a whole (e.g., modularity, connectedness), or on the topological function of single authors (e.g., distance, betweenness). Here we show that the success of individual authors or publications depends unexpectedly strongly on an intermediate scale in co-authorship networks. For two large-scale data sets, CiteSeerX and DBLP, we analyze the correlation of (three- and four-node) network motifs with citation frequencies. We find that the average citation frequency of a group of authors depends on the motifs these authors form. In particular, a box motif (four authors forming a closed chain) has the highest average citation frequency per link. This result is robust across the two databases, across different ways of mapping the citation frequencies of publications onto the (uni-partite) co-authorship graph, and over time. We also relate this topological observation to the underlying social and socio-scientific processes that have been shaping the networks. We argue that the box motif may be an interesting category in a broad range of social and technical networks.     

Drastic events make evolving networks

Co-authorship networks of neighbouring scientific disciplines, i.e. granular (G) media and networks (N) are studied in order to observe drastic structural changes in evolving networks. The data is taken from arXives. The system is described as coupled networks. By considering the 1995–2005 time interval and scanning the author-article network evolution with a mobile time window, we focus on the properties of the links, as well as on the time evolution of the nodes. They can be in three states, N, G or multi-disciplinary (M). This leads to drastic jumps in a so-called order parameter, i.e. the link proportion of a given type, forming the main island, that reminds of features appearing at percolation and during metastable (aggregation-desaggregation) processes. The data analysis also focuses on the way different kinds (N, G or M) of authors collaborate, and on the kind of the resulting collaboration.     

基于最大熵模型的导师-学生关系推测

导师-学生关系是科研合作网络中重要的关系类型之一, 准确识别此类关系对促进科研交流与合作、评审回避等有重要意义. 以论文合作网络为基础, 依据学生发表论文时通常与导师共同署名的现象, 抽象出能够反映导师-学生合作关系的特征, 提出了基于最大熵模型的导师-学生关系识别算法. 利用DBLP中1990-2011年的论文数据进行实例验证, 结果显示: 1)关系类型识别结果的准确率超过95%; 2)导师-学生关系终止时间的平均误差为1.39年. 该方法在识别关系时避免了特征之间相互独立的约束, 准确率优于其他同类识别算法, 且建模方法对识别社交网络中的其他关系类型也具有借鉴意义. 关键词： 社交网络 关系识别 最大熵模型 特征选择     

Disentangling the Information in Species Interaction Networks

Shannon’s entropy measure is a popular means for quantifying ecological diversity. We explore how one can use information-theoretic measures (that are often called indices in ecology) on joint ensembles to study the diversity of species interaction networks. We leverage the little-known balance equation to decompose the network information into three components describing the species abundance, specificity, and redundancy. This balance reveals that there exists a fundamental trade-off between these components. The decomposition can be straightforwardly extended to analyse networks through time as well as space, leading to the corresponding notions for alpha, beta, and gamma diversity. Our work aims to provide an accessible introduction for ecologists. To this end, we illustrate the interpretation of the components on numerous real networks. The corresponding code is made available to the community in the specialised Julia package EcologicalNetworks.jl.     

Selective investment promotes cooperation in public goods game

Most previous investigations on spatial Public Goods Game assume that individuals treat neighbors equivalently, which is in sharp contrast with realistic situations, where bias is ubiquitous. We construct a model to study how a selective investment mechanism affects the evolution of cooperation. Cooperators selectively contribute to just a fraction among their neighbors. According to the interaction result, the investment network can be adapted. On selecting investees, three patterns are considered. In the random pattern, cooperators choose their investees among the neighbors equiprobably. In the social-preference pattern, cooperators tend to invest to individuals possessing large social ties. In the wealth-preference pattern, cooperators are more likely to invest to neighbors with higher payoffs. Our result shows robustness of selective investment mechanism that boosts emergence and maintenance of cooperation. Cooperation is more or less hampered under the latter two patterns, and we prove the anti-social-preference or anti-wealth-preference pattern of selecting investees can accelerate cooperation to some extent. Furthermore, the theoretical analysis of our mechanism on double-star networks coincides with simulation results. We hope our finding could shed light on better understanding of the emergence of cooperation among adaptive populations.     

Temporal percolation of a susceptible adaptive network

In the past decades, many authors have used the susceptible–infected–recovered model to study the impact of the disease spreading on the evolution of the infected individuals. However, few authors focused on the temporal unfolding of the susceptible individuals. In this paper, we study the dynamic of the susceptible–infected–recovered model in an adaptive network that mimics the transitory deactivation of permanent social contacts, such as friendship and work-ship ties. Using an edge-based compartmental model and percolation theory, we obtain the evolution equations for the fraction susceptible individuals in the susceptible biggest component. In particular, we focus on how the individual’s behavior impacts on the dilution of the susceptible network. We show that, as a consequence, the spreading of the disease slows down, protecting the biggest susceptible cluster by increasing the critical time at which the giant susceptible component is destroyed. Our theoretical results are fully supported by extensive simulations.     

Heat conduction process on community networks as a recommendation model

Using heat conduction mechanism on a social network we develop a systematic method to predict missing values as recommendations. This method can treat very large matrices that are typical of internet communities. In particular, with an innovative, exact formulation that accommodates arbitrary boundary condition, our method is easy to use in real applications. The performance is assessed by comparing with traditional recommendation methods using real data.     

What is the difference of research collaboration network under different projections: Topological measurement and analysis

Research collaboration network is a typical bipartite network that consists of papers and authors. This bipartite network could be transformed into one-mode networks by projection. In this paper, we used three different projections to construct three co-authorship networks. Topological features of three co-authorship networks are measured and analyzed in order to understand the influence of projections on network features. The measurement results show that different projections could lead to different topological features. Therefore, to reflect the existing reality more precisely, projection method is suggested to be considered when we investigate the structure of scientific collaborations and/or assess the status, impact and influence of researchers and their institutions.     

Social inertia and diversity in collaboration networks

Random graphs are useful tools to study social interactions. In particular, the use of weighted random graphs allows to handle a high level of information concerning which agents interact and in which degree the interactions take place. Taking advantage of this representation, we recently defined a magnitude, the Social Inertia, that measures the eagerness of agents to keep ties with previous partners. To study this magnitude, we used collaboration networks that are specially appropriate to obtain valid statitical results due to the large size of publically available databases. In this work, I study the Social Inertia in two of these empirical networks, IMDB movie database and condmat. More specifically, I focus on how the Inertia relates to other properties of the graphs, and show that the Inertia provides information on how the weight of neighboring edges correlates. A social interpretation of this effect is also offered.     

Evolving model of weighted networks inspired by scientific collaboration networks

Inspired by scientific collaboration networks (SCN), especially our empirical analysis of econophysicists network, an evolutionary model for weighted networks is proposed. Besides a new vertex added in at every time step, old vertices can also attempt to build up new links, or to reconnect the existing links. The number of connections repeated between two nodes is converted into the weight of the link. This provides a natural way for the evolution of link weight. The path-dependent preferential attachment mechanism with local information is also introduced. It increases the clustering coefficient of the network significantly. The model shows the scale-free phenomena in degree and vertex weight distribution. It also gives well qualitatively consistent behavior with the empirical results.     

Empirical analysis of the evolution of a scientific collaboration network

We present an analysis of the temporal evolution of a scientific coauthorship network, the genetic programming network. We find evidence that the network grows according to preferential attachment, with a slightly sublinear rate. We empirically find how a giant component forms and develops, and we characterize the network by several other time-varying quantities: the mean degree, the clustering coefficient, the average path length, and the degree distribution. We find that the first three statistics increase over time in the growing network; the degree distribution tends to stabilize toward an exponentially truncated power-law. We finally suggest an effective network interpretation that takes into account the aging of collaboration relationships.     

A study of the spreading scheme for viral marketing based on a complex network model

Buzzword-based viral marketing, known also as digital word-of-mouth marketing, is a marketing mode attached to some carriers on the Internet, which can rapidly copy marketing information at a low cost. Viral marketing actually uses a pre-existing social network where, however, the scale of the pre-existing network is believed to be so large and so random, so that its theoretical analysis is intractable and unmanageable. There are very few reports in the literature on how to design a spreading scheme for viral marketing on real social networks according to the traditional marketing theory or the relatively new network marketing theory. Complex network theory provides a new model for the study of large-scale complex systems, using the latest developments of graph theory and computing techniques. From this perspective, the present paper extends the complex network theory and modeling into the research of general viral marketing and develops a specific spreading scheme for viral marking and an approach to design the scheme based on a real complex network on the QQ instant messaging system. This approach is shown to be rather universal and can be further extended to the design of various spreading schemes for viral marketing based on different instant messaging systems.     

Modeling complex networks with accelerating growth and aging effect

Numerous empirical studies have revealed that a large number of real networks exhibit the property of accelerating growth, i.e. network size (nodes) increases superlinearly with time. Examples include the size of social networks, the output of scientists, the population of cities, and so on. In the literature, these real systems are widely represented by complex networks for analysis, and many network models have been proposed to explain the observed properties in these systems such as power-law degree distribution. However, most of these models (e.g. the well-known BA model) are based on linear growth of these systems. In this paper, we propose a network model with accelerating growth and aging effect, resulting in an emergence of super hubs which is consistent with the empirical observation in citation networks.     

Assortative mixing in networks

A network is said to show assortative mixing if the nodes in the network that have many connections tend to be connected to other nodes with many connections. Here we measure mixing patterns in a variety of networks and find that social networks are mostly assortatively mixed, but that technological and biological networks tend to be disassortative. We propose a model of an assortatively mixed network, which we study both analytically and numerically. Within this model we find that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.     

Dynamic Robustness of Open-Source Project Knowledge Collaborative Network Based on Opinion Leader Identification

A large amount of semantic content is generated during designer collaboration in open-source projects (OSPs). Based on the characteristics of knowledge collaboration behavior in OSPs, we constructed a directed, weighted, semantic-based knowledge collaborative network. Four social network analysis indexes were created to identify the key opinion leader nodes in the network using the entropy weight and TOPSIS method. Further, three degradation modes were designed for (1) the collaborative behavior of opinion leaders, (2) main knowledge dissemination behavior, and (3) main knowledge contribution behavior. Regarding the degradation model of the collaborative behavior of opinion leaders, we considered the propagation characteristics of opinion leaders to other nodes, and we created a susceptible–infected–removed (SIR) propagation model of the influence of opinion leaders’ behaviors. Finally, based on empirical data from the Local Motors open-source vehicle design community, a dynamic robustness analysis experiment was carried out. The results showed that the robustness of our constructed network varied for different degradation modes: the degradation of the opinion leaders’ collaborative behavior had the lowest robustness; this was followed by the main knowledge dissemination behavior and the main knowledge contribution behavior; the degradation of random behavior had the highest robustness. Our method revealed the influence of the degradation of collaborative behavior of different types of nodes on the robustness of the network. This could be used to formulate the management strategy of the open-source design community, thus promoting the stable development of OSPs.     

From calls to communities: a model for time-varying social networks

Social interactions vary in time and appear to be driven by intrinsic mechanisms thatshape the emergent structure of social networks. Large-scale empirical observations ofsocial interaction structure have become possible only recently, and modelling theirdynamics is an actual challenge. Here we propose a temporal network model which builds onthe framework of activity-driven time-varying networks with memory. Themodel integrates key mechanisms that drive the formation of social ties – socialreinforcement, focal closure and cyclicclosure, which have been shown to give rise to community structure andsmall-world connectedness in social networks. We compare the proposed model with areal-world time-varying network of mobile phone communication, and show that they shareseveral characteristics from heterogeneous degrees and weights to rich communitystructure. Further, the strong and weak ties that emerge from the model follow similarweight-topology correlations as real-world social networks, including the role of weakties.     

一种新的复杂网络影响力最大化发现方法

复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一, 其研究在理论和现实应用中都有重大的意义. 在给定s值的前提下, 如何寻找发现s个最大影响范围的节点集, 这是个组合优化问题, Kempe等已经证明该问题是NP-hard问题. 目前已有的随机算法时间复杂度低, 但是结果最差; 其他贪心算法时间复杂度很高, 不能适用于大型社会网络中, 并且这些典型贪心算法必须以了解网络的全局信息为前提, 而获取整个庞大复杂且不断发展变化的社会网络结构是很难以做到的. 我们提出了一种新的影响力最大化算法模型RMDN, 及改进的模型算法RMDN++, 模型只需要知道随机选择的节点以及其邻居节点信息, 从而巧妙地回避了其他典型贪心算法中必须事先掌握整个网络全局信息的问题, 算法的时间复杂度仅为O(s log(n)); 然后, 我们利用IC模型和LT模型在4种不同的真实复杂网络数据集的实验显示, RMDN, RMDN++算法有着和现有典型算法相近的影响力传播效果, 且有时还略优, 同时在运行时间上则有显著的提高; 我们从理论上推导证明了方法的可行性. 本文所提出的模型算法适用性更广, 可操作性更强, 为这项具有挑战性研究提供了新的思路和方法.     

Emergence of Influential Spreaders in Modified Rumor Models

The burst in the use of online social networks over the last decade has provided evidence that current rumor spreading models miss some fundamental ingredients in order to reproduce how information is disseminated. In particular, recent literature has revealed that these models fail to reproduce the fact that some nodes in a network have an influential role when it comes to spread a piece of information. In this work, we introduce two mechanisms with the aim of filling the gap between theoretical and experimental results. The first model introduces the assumption that spreaders are not always active whereas the second model considers the possibility that an ignorant is not interested in spreading the rumor. In both cases, results from numerical simulations show a higher adhesion to real data than classical rumor spreading models. Our results shed some light on the mechanisms underlying the spreading of information and ideas in large social systems and pave the way for more realistic diffusion models.     

一种基于最大流的网络结构熵

熵是可用来反映网络结构异质性的指标.针对传统熵指标不能很好反映网络全局异构性的不足,本文引入网络流的概念,综合考虑径向测度和中间测度,提出一种新的网络结构熵.特殊网络(如公用数据集Dolphins网络)的分析结果表明,本文提出的熵指标在一定程度上克服了其他网络熵指标的不足,更能够反映网络的真实拓扑结构;对随机网络、最近邻耦合网络、星型网络、无标度网络、Benchmark网络和小世界网络等典型网络的理论分析和仿真实验,进一步证明本文提出的熵指标在刻画一般复杂网络结构特征上的有效性和适用性.