Centrality prediction in dynamic human contact networks

Real technological, social and biological networks evolve over time. Predicting their future topology has applications to epidemiology, targeted marketing, network reliability and routing in ad hoc and peer-to-peer networks. The key problem for such applications is usually to identify the nodes that will be in more important positions in the future. Previous researchers had used ad hoc prediction functions. In this paper, we evaluate ways of predicting a node’s future importance under three important metrics, namely degree, closeness centrality, and betweenness centrality, using empirical data on human contact networks collected using mobile devices. We find that node importance is highly predictable due to both periodic and legacy effects of human social behaviour, and we design reasonable prediction functions. However human behaviour is not the same in all circumstances: the centrality of students at Cambridge is best correlated both daily and hourly, no doubt due to hourly lecture schedules, while academics at conferences exhibit rather flat closeness centrality, no doubt because conference attendees are generally trying to speak to new people at each break. This highlights the utility of having a number of different metrics for centrality in dynamic networks, so as to identify typical patterns and predict behaviour. We show that the best-performing prediction functions are 25% more accurate on average than simply using the previous centrality value. These prediction functions can be efficiently computed in linear time, and are thus practical for processing dynamic networks in real-time.     

基于社区的动态网络节点介数中心度更新算法

随着互联网技术的迅猛发展,社会网络呈现出爆炸增长的趋势,传统的静态网络分析方法越来越难以达到令人满意的效果,于是对网络进行动态分析就成为社会网数据管理领域的一个研究热点。节点介数中心度衡量的是一个节点对图中其他点对最短路径的控制能力,有利于挖掘社会网络中的重要节点。在图结构频繁变化的场合,若每次变化后都重新计算整个图中所有节点的介数中心度,则效率将会很低。针对动态网络中节点介数中心度计算困难的问题,本文提出一种基于社区的节点介数中心度更新算法。通过维护社区与社区、社区与节点的最短距离集合,快速过滤掉那些在网络动态更新中不受影响的点对,从而大大提高节点介数中心度的更新效率。真实数据集和合成数据集上的实验结果表明了论文所提算法的有效性。     

大数据环境下精准客户定位的社交网络分析

大数据为企业进行精准营销提供了重要支撑,精准营销能提升营销效果,提高客户满意度,精准营销的前提是客户识别与选择。通过分析网络个体与群体特征,社交网络分析能够定位核心价值客户。首先对社交网络的中心性进行分析,探讨社交网络节点地位与营销效果的关系,运用社群识别方法,对社交网络进行分群,提出并用MapReduce实现了针对大规模社交网络的社群划分RMCL方法。在此基础上,构建了客户影响度与客户影响因子等指标,并结合中心度指标,定位社群的核心节点,并采用分类回归树方法,研究了社交网络结构与客户消费响应关系,并确定了变量重要性,为企业采取客户差异化营销组合策略提供指导。     

Organization Mining Using Online Social Networks

Complementing the formal organizational structure of a business are the informal connections among employees. These relationships help identify knowledge hubs, working groups, and shortcuts through the organizational structure. They carry valuable information on how a company functions de facto. In the past, eliciting the informal social networks within an organization was challenging; today they are reflected by friendship relationships in online social networks. In this paper we analyze several commercial organizations by mining data which their employees have exposed on Facebook, LinkedIn, and other publicly available sources. Using a web crawler designed for this purpose, we extract a network of informal social relationships among employees of targeted organizations. Our results show that it is possible to identify leadership roles within the organization solely by using centrality analysis and machine learning techniques applied to the informal relationship network structure. Valuable non-trivial insights can also be gained by clustering an organization’s social network and gathering publicly available information on the employees within each cluster. Knowledge of the network of informal relationships may be a major asset or might be a significant threat to the underlying organization.     

Heuristical top-k: fast estimation of centralities in complex networks

Centrality metrics have proven to be of a major interest when analyzing the structure of networks. Given modern-day network sizes, fast algorithms for estimating these metrics are needed. This paper proposes a computation framework (named Filter-Compute-Extract) that returns an estimate of the top-k most important nodes in a given network. We show that considerable savings in computation time can be achieved by first filtering the input network based on correlations between cheap and more costly centrality metrics. Running the costly metric on the smaller resulting filtered network yields significant gains in computation time. We examine the complexity improvement due to this heuristic for classic centrality measures, as well as experimental results on well-studied public networks.     

Eine kritische Analyse von Vernetzungsmaßen in sozialen Netzwerken

Social networks are currently gaining increasing impact in the light of the ongoing growth of web-based services like facebook.com. One major challenge for the economically successful implementation of selected management activities such as viral marketing is the identification of key persons with an outstanding structural position within the network. For this purpose, social network analysis provides a lot of measures for quantifying a member’s interconnectedness within social networks. In this context, our paper shows the state of the art with regard to centrality measures for social networks. Due to strongly differing results with respect to the quality of different centrality measures, this paper also aims at illustrating the tremendous importance of a reflected utilization of existing centrality measures. For this purpose, the paper analyzes five centrality measures commonly discussed in literature on the basis of three simple requirements for the behavior of centrality measures.     

Introducing a procedure for developing a novel centrality measure (Sociability Centrality) for social networks using TOPSIS method and genetic algorithm

Centrality is one of the most important fields of social network research. To date, some centrality measures based on topological features of nodes in social networks have been proposed in which the importance of nodes is investigated from a certain point of view. Such measures are one dimensional and thus not feasible for measuring sociological features of nodes. Given that the main basis of Social Network Analysis (SNA) is related to social issues and interactions, a novel procedure is hereby proposed for developing a new centrality measure, named Sociability Centrality, based on the TOPSIS method and Genetic Algorithm (GA). This new centrality is not only based on topological features of nodes, but also a representation of their psychological and sociological features that is calculable for large size networks (e.g. online social networks) and has high correlation with the nodes' social skill questionnaire scores. Finally, efficiency of the proposed procedure for developing sociability centrality was tested via implementation on the Abrar Dataset. Our results show that this centrality measure outperforms its existing counterparts in terms of representing the social skills of nodes in a social network.     

Second order centrality: Distributed assessment of nodes criticity in complex networks

A complex network can be modeled as a graph representing the “who knows who” relationship. In the context of graph theory for social networks, the notion of centrality is used to assess the relative importance of nodes in a given network topology. For example, in a network composed of large dense clusters connected through only a few links, the nodes involved in those links are particularly critical as far as the network survivability is concerned. This may also impact any application running on top of it. Such information can be exploited for various topological maintenance issues to prevent congestion and disruption. This can also be used offline to identify the most important actors in large social interaction graphs. Several forms of centrality have been proposed so far. Yet, they suffer from imperfections: initially designed for small social graphs, they are either of limited use (degree centrality), either incompatible in a distributed setting (e.g. random walk betweenness centrality).In this paper we introduce a novel form of centrality: the second order centrality which can be computed in a distributed manner. This provides locally each node with a value reflecting its relative criticity and relies on a random walk visiting the network in an unbiased fashion. To this end, each node records the time elapsed between visits of that random walk (called return time in the sequel) and computes the standard deviation (or second order moment) of such return times. The key point is that central nodes see regularly the random walk compared to other topology nodes. Both through theoretical analysis and simulation, we show that the standard deviation can be used to accurately identify critical nodes as well as to globally characterize graphs topology in a distributed way. We finally compare our proposal to well-known centralities to assess its competitivity.     

Social centrality using network hierarchy and community structure

Several centrality measures have been formulated to quantify the notion of ‘importance’ of actors in social networks. Current measures scrutinize either local or global connectivity of the nodes and have been found to be inadequate for social networks. Ignoring hierarchy and community structure, which are inherent in all human social networks, is the primary cause of this inadequacy. Positional hierarchy and embeddedness of an actor in the community are intuitively crucial determinants of his importance. The theory of social capital asserts that an actor’s importance is derived from his position in network hierarchy as well as from the potential to mobilize resources through intra-community (bonding) and inter-community (bridging) ties. Inspired by this idea, we propose a novel centrality measure social centrality (SC) for actors in social networks. Our measure accounts for—(1) an individual’s propensity to socialize, and (2) his connections within and outside the community. These two factors are suitably aggregated to produce social centrality score. Comparative analysis of SC measure with classical and recent centrality measures using large public networks shows that it consistently produces more realistic ranking of nodes. The inference is based on the available ground truth for each tested networks. Extensive analysis of rankings delivered by SC measure and mapping with known facts in well-studied networks justifies its effectiveness in diverse social networks. Scalability evaluation of SC measure justifies its efficacy for real-world large networks.     

An analysis model of diagnosis and treatment for COVID-19 pandemic based on medical information fusion

Exploring the complicated relationships underlying the clinical information is essential for the diagnosis and treatment of the Coronavirus Disease 2019 (COVID-19). Currently, few approaches are mature enough to show operational impact. Based on electronic medical records (EMRs) of 570 COVID-19 inpatients, we proposed an analysis model of diagnosis and treatment for COVID-19 based on the machine learning algorithms and complex networks. Introducing the medical information fusion, we constructed the heterogeneous information network to discover the complex relationships among the syndromes, symptoms, and medicines. We generated the numerical symptom (medicine) embeddings and divided them into seven communities (syndromes) using the combination of Skip-Gram model and Spectral Clustering (SC) algorithm. After analyzing the symptoms and medicine networks, we identified the key factors using six evaluation metrics of node centrality. The experimental results indicate that the proposed analysis model is capable of discovering the critical symptoms and symptom distribution for diagnosis; the key medicines and medicine combinations for treatment. Based on the latest COVID-19 clinical guidelines, this model could result in the higher accuracy results than the other representative clustering algorithms. Furthermore, the proposed model is able to provide tremendously valuable guidance and help the physicians to combat the COVID-19.     

ML-SOR: Message routing using multi-layer social networks in opportunistic communications

Opportunistic networks are a generalization of DTNs in which disconnections are frequent and encounter patterns between mobile devices are unpredictable. In such scenarios, message routing is a fundamental issue. Social-based routing protocols usually exploit the social information extracted from the history of encounters between mobile devices to find an appropriate message relay. Protocols based on encounter history, however, take time to build up a knowledge database from which to take routing decisions. While contact information changes constantly and it takes time to identify strong social ties, other types of ties remain rather stable and could be exploited to augment available partial contact information. In this paper, we start defining a multi-layer social network model combining the social network detected through encounters with other social networks and investigate the relationship between these social network layers in terms of node centrality, community structure, tie strength and link prediction. The purpose of this analysis is to better understand user behavior in a multi-layered complex network combining online and offline social relationships. Then, we propose a novel opportunistic routing approach ML-SOR (Multi-layer Social Network based Routing) which extracts social network information from such a model to perform routing decisions. To select an effective forwarding node, ML-SOR measures the forwarding capability of a node when compared to an encountered node in terms of node centrality, tie strength and link prediction. Trace driven simulations show that a routing metric combining social information extracted from multiple social network layers allows users to achieve good routing performance with low overhead cost.     

Predicting temporal centrality in Opportunistic Mobile Social Networks based on social behavior of people

Predicting the centrality of nodes is a significant problem for different applications in Opportunistic Mobile Social Networks (OMSNs). However, when calculating such metrics, current studies focused on analyzing static networks that do not change over time or using aggregated contact information over a period of time. Furthermore, the centrality measured in the past is not verified whether it is useful as a predictor for the future. In this paper, in order to capture the dynamic behavior of people, we focus on predicting nodes’ future centrality (importance) from the temporal perspective using real mobility traces in OMSNs. Three important centrality metrics, namely betweenness, closeness, and degree centrality, are considered. Through real trace-driven simulations, we find that nodes’ future centrality is highly predictable due to natural social behavior of people. Then, based on the observations in the simulation, we design several reasonable prediction methods to predict nodes’ future temporal centrality. Finally, extensive real trace-driven simulations are conducted to evaluate the performance of our proposed methods. The results show that the Recent Weighted Average Method performs best in the MIT Reality trace, and the recent Uniform Average Method performs best in the Infocom 06 trace. Furthermore, we also evaluate the impact of parameters m and w on the performance of the proposed methods and find proper values of different parameters for each proposed method at the same time.     

基于多属性综合评价的食品安全标准引用网络重要节点发现方法

针对如何利用食品安全标准引用网络来从众多的食品安全国家标准中找到对食品安全检验、检测影响较大的关键标准，提出了一种基于多属性综合评价的食品安全标准引用网络重要节点发现方法。首先，利用社交网络分析中的度中心性、紧密度中心性、介数中心性以及Web页面重要度评价算法PageRank，分别对标准节点的重要性进行评价；然后，使用层次分析法（AHP）计算各个评价指标在重要性评价中的权重，通过基于逼近理想解排序法（TOPSIS）的多属性决策方法综合评价标准节点的重要性并寻找到重要节点；其次，将基于综合评价得到的重要节点与基于度的评价得到的重要节点分别从各自的引用网络中删除，并检验重要节点删除后引用网络的连通性，连通性越差，说明节点越重要；最后，使用Louvain社区发现算法检验网络的连通性，即对网络节点进行社区发现，没有被划入社区的节点越多，说明网络的连通性越差。实验结果表明，相较于基于度的评价方法，基于多属性的综合评价方法发现的重要节点被删除后不能划入社区的节点更多，证明后者能更好地发现引用网络中的重要节点。可见所提方法有助于标准制定者在修改、更新标准时，快速把握核心内容与关键节点，对食品安全国家标准的体系构建起到指导作用。     

The effects of a player’s network centrality on resource accessibility,game enjoyment,and continuance intention: A study on online gaming communities

This study applies social capital theory to investigate how a player’s network centrality in an online gaming community (i.e., a guild) affects his/her attitude and continuance intention toward a Massive Multiplayer Online Game (MMOG). Analysis of 347 usable responses shows that players’ network centrality has a negative impact on their ties to players who belong to other guilds (i.e., non-guild interaction), but a positive effect on players’ access to resources. However, players’ network centrality fails to increase their perceived game enjoyment directly. Players’ resource accessibility and perceived game enjoyment play mediating roles in the relationship between network centrality and attitude toward playing an MMOG, which in turn influences game continuance intention. The results also show that although players’ non-guild interaction is negatively related to their resource accessibility from the networks, it is positively associated with perceived game enjoyment. The article concludes with implications and limitations of the study.     

小世界网络抗毁性及介-度相关性研究

日常生活中,复杂网络主要面临随机攻击和选择性攻击,网络模型的结构特性使复杂网络在不同攻击方式下的抗毁性有很大的差异.综合考虑复杂网络的抗毁性参数和网络模型的结构特性差异,文章以节点的最大度值、平均度值、最大介数和平均介数为度量参数,通过5种不同攻击方式对WS小世界网络的抗毁性进行了测试,得到了介度关系曲线,随着节点的移除,动态分析了WS小世界网络的抗毁性和攻击下小世界网络的介 度相关性.实验结果表明,WS小世界网络在RD攻击下表现出一定的脆弱性,在其他攻击方式下有很强的鲁棒性,而其介度关系在某些区域呈线性关系,但大部分区域呈现无规律性,其动态相关性需要进一步研究.小世界网络较强的抗毁性对组建网络有重要的影响,鉴于小世界网络的结构特性,组建网络时应尽量不要把网络的功能集中在少数Hub节点上.针对WS小世界网络较强的鲁棒性,结合小世界网络的结构特性,将做进一步研究,以便提出更高效的攻击策略.     

Privacy policies for shared content in social network sites

Social networking is one of the major technological phenomena of the Web 2.0, with hundreds of millions of subscribed users. Social networks enable a form of self-expression for users and help them to socialize and share content with other users. In spite of the fact that content sharing represents one of the prominent features of existing Social network sites, they do not provide any mechanisms for collective management of privacy settings for shared content. In this paper, using game theory, we model the problem of collective enforcement of privacy policies on shared data. In particular, we propose a solution that offers automated ways to share images based on an extended notion of content ownership. Building upon the Clarke-Tax mechanism, we describe a simple mechanism that promotes truthfulness and that rewards users who promote co-ownership. Our approach enables social network users to compose friendship based policies based on distances from an agreed upon central user selected using several social networks metrics. We integrate our design with inference techniques that free the users from the burden of manually selecting privacy preferences for each picture. To the best of our knowledge, this is the first time such a privacy protection mechanism for social networking has been proposed. We also extend our mechanism so as to support collective enforcement across multiple social network sites. In the paper, we also show a proof-of-concept application, which we implemented in the context of Facebook, one of today’s most popular social networks. Through our implementation, we show the feasibility of such approach and show that it can be implemented with a minimal increase in overhead to end-users. We complete our analysis by conducting a user study to investigate users’ understanding of co-ownership, usefulness and understanding of our approach. Users responded favorably to the approach, indicating a general understanding of co-ownership and the auction, and found the approach to be both useful and fair.     

基于重叠盒覆盖算法的节点重要度评估

由于单一的节点评估方法存在不足,在融合复杂网络的局部特征以及全局特征前提下,提出了一种基于重叠盒覆盖算法的节点重要度评估方法.该方法利用重叠中心性对网络中的节点进行重要度排序,并且与其他不同中心性方法在复杂网络数据集中的节点排序方法进行比较;利用susceptible-infected (SI)模型模拟不同中心性方法前10个节点的传播能力,在此基础上以肯德尔系数进行比较,肯德尔系数越大表明相关性越高.实验结果表明,与其他中心性方法相比,重叠中心性得到的初始节点集合的累积平均感染能力高于其他中心性方法,并且与SI模型具有较高的相关性,该方法对于节点重要度评估是有效并且可行的.     

Flocking based evolutionary computation strategy for measuring centrality of online social networks

Centrality in social network is one of the major research topics in social network analysis. Even though there are more than half a dozen methods to find centrality of a node, each of these methods has some drawbacks in one aspect or the other. This paper analyses different centrality calculation methods and proposes a new swarm based method named Flocking Based Centrality for Social network (FBCS). This new computation technique makes use of parameters that are more realistic and practical in online social networks. The interactions between nodes play a significant role in determining the centrality of node. The new method has been calculated both empirically as well as experimentally. The new method is tested, verified and validated for different sets of random networks and benchmark datasets. The method has been correlated with other state of the art centrality measures. The new centrality measure is found to be realistic and suits well with online social networks. The proposed method can be used in applications such as finding the most prestigious node and for discovering the node which can influence maximum number of users in an online social network. FBCS centrality has higher Kendall’s tau correlation when compared with other state of the art centrality methods. The robustness of the FBCS centrality is found to be better than other centrality measures.     

How is the Semantic Web evolving? A dynamic social network perspective

Finding how the Semantic Web has evolved can help understand the status of Semantic Web community and predict the diffusion of the Semantic Web. One of the promising applications of the Semantic Web is the representation of personal profiles using Friend of a Friend (FOAF). A key characteristic of such social networks is their continual change. However, extant analyses of social networks on the Semantic Web are essentially static in that the information about the change of social networks is neglected. To address the limitations, we analyzed the dynamics of a large-scale real-world social network in this paper. Social network ties were extracted from both within and between FOAF documents. The former was based on knows relations between persons, and the latter was based on revision relations. We found that the social network evolves in a speckled fashion, which is highly distributed. The network went through rapid increase in size at an early stage and became stabilized later. By examining the changes of structural properties over time, we identified the evolution patterns of social networks on the Semantic Web and provided evidence for the growth and sustainability of the Semantic Web community.     

Robust network planning in nonuniform traffic scenarios

Robustness to the environmental variations is an important feature of any reliable communication network. This paper reports on a network theory approach to the design of such networks where the environmental changes are traffic fluctuations, topology modifications, and changes in the source of external traffic. Motivated by the definition of betweenness centrality in network science, we introduce the notion of traffic-aware betweenness (TAB) for data networks, where usually an explicit (or implicit) traffic matrix governs the distribution of external traffic into the network. We use the average normalized traffic-aware betweenness, which is referred to as traffic-aware network criticality (TANC), as our main metric to quantify the robustness of a network. We show that TANC is directly related to some important network performance metrics, such as average network utilization and average network cost. We prove that TANC is a linear function of end-to-end effective resistances of the graph. As a result, TANC is a convex function of link weights and can be minimized using convex optimization techniques. We use semi-definite programming method to study the properties of the optimization problem and derive useful results to be employed for robust network planning purposes.