A game-theoretic framework to identify overlapping communities in social networks

In this paper, we introduce a game-theoretic framework to address the community detection problem based on the structures of social networks. We formulate the dynamics of community formation as a strategic game called community formation game: Given an underlying social graph, we assume that each node is a selfish agent who selects communities to join or leave based on her own utility measurement. A community structure can be interpreted as an equilibrium of this game. We formulate the agents’ utility by the combination of a gain function and a loss function. We allow each agent to select multiple communities, which naturally captures the concept of “overlapping communities”. We propose a gain function based on the modularity concept introduced by Newman (Proc Natl Acad Sci 103(23):8577–8582, 2006), and a simple loss function that reflects the intrinsic costs incurred when people join the communities. We conduct extensive experiments under this framework, and our results show that our algorithm is effective in identifying overlapping communities, and are often better then other algorithms we evaluated especially when many people belong to multiple communities. To the best of our knowledge, this is the first time the community detection problem is addressed by a game-theoretic framework that considers community formation as the result of individual agents’ rational behaviors.     

A new method to identify collaborative partners in social service provider networks

The interactions among service providers are represented as a social network to support service-oriented collaborations across multiple manufacturing enterprises. The combination of service-oriented computing and social network facilitates the connection and collaboration within enterprises. It is essential to identify a group of prosperous collaborative partners in a social network in a prompt and efficient way, especially when the number of alternative service providers is large. However, traditional exhaustive searching approaches are inapplicable in identifying a host enterprise and constitutive members due to the prohibitive computations. In this paper, a new and efficient approach has been proposed to identify service providers optimally based on existing social relations. Three innovations in the proposal are (i) a set of new concepts has been defined to construct a social service provider network; (ii) based on remodeling the social graph, the betweenness centrality algorithm has been enhanced to efficiently find the leader who serves as the host enterprise of a given engineering project; (iii) to improve the efficiency of computation, an innovative algorithm is proposed to identify the collaborative partners by confining the searching space in the set of connector nodes. For the validation purpose, the experimental simulation is conducted and the results have demonstrated that the proposed algorithms outperform several existing algorithms in terms of computation time in dealing with the increasing number of enterprises.     

Inter-organisational knowledge transfer in social networks: A definition of intermediate ties

A social network perspective helps identify and analyse informal knowledge transfer among people and organisations with the aim to recommend organisational interventions and improvements, for example in the form of Information and Communication Technology (ICT) support. This paper particularly focuses on a key concept of social network analysis (SNA), the concept of tie strength, in an inter-organisational knowledge transfer context. Tie strength describes the strength of a social relationship. In the past, SNA literature with a knowledge management context has often emphasized the importance of strong and/or weak ties rather than of intermediate (medium strong) ties in a social network. Nevertheless, in this study, intermediate ties are identified as the dominant links among key groups of organisation in a social network. Intermediate ties also help connect otherwise weakly linked organisations. Moreover, a definition of intermediate ties in the context of knowledge management is introduced. With the help of cluster analysis and an investigation into the levels of reciprocity, intermediate ties can be clearly defined in a social network. Due to their importance for knowledge transfer in a social network, intermediate ties should be primarily supported, for example by appropriate ICT.     

Anonymizing social networks: A generalization approach

Social networks provide a mathematical picture of various relationships that exist in society. A social network can be represented by graph data structures. These graphs are rich sources of information that must be published to share with the world. As a result, however, the privacy of users is compromised. Conventional techniques such as anonymization, randomization and masking are used to protect privacy. The techniques proposed to date do not consider the utility of published data. Absolute privacy implies zero utility, and vice versa. This paper focuses on the importance of users and the protection of their privacy. The importance of a user is determined by centrality or prestige measures. Generalization of the user is performed based on their importance to ensure privacy and utility in social networks. The information lost due to generalization is also measured.     

Actively learning to infer social ties

We study the extent to which social ties between people can be inferred in large social network, in particular via active user interactions. In most online social networks, relationships are lack of meaning labels (e.g., ??colleague?? and ??intimate friends??) due to various reasons. Understanding the formation of different types of social relationships can provide us insights into the micro-level dynamics of the social network. In this work, we precisely define the problem of inferring social ties and propose a Partially-Labeled Pairwise Factor Graph Model (PLP-FGM) for learning to infer the type of social relationships. The model formalizes the problem of inferring social ties into a flexible semi-supervised framework. We test the model on three different genres of data sets and demonstrate its effectiveness. We further study how to leverage user interactions to help improve the inferring accuracy. Two active learning algorithms are proposed to actively select relationships to query users for their labels. Experimental results show that with only a few user corrections, the accuracy of inferring social ties can be significantly improved. Finally, to scale the model to handle real large networks, a distributed learning algorithm has been developed.     

Arnetminer: expertise oriented search using social networks

Expertise Oriented Search (EOS) aims at providing comprehensive expertise analysis on data from distributed sources. It is useful in many application domains, for example, finding experts on a given topic, detecting the confliction of interest between researchers, and assigning reviewers to proposals. In this paper, we present the design and implementation of our expertise oriented search system, Arnetminer (). Arnetminer has gathered and integrated information about a half-million computer science researchers from the Web, including their profiles and publications. Moreover, Arnetminer constructs a social network among these researchers through their co-authorship, and utilizes this network information as well as the individual profiles to facilitate expertise oriented search tasks. In particular, the co-authorship information is used both in ranking the expertise of individual researchers for a given topic and in searching for associations between researchers. We have conducted initial experiments on Arnetminer. Our results demonstrate that the proposed relevancy propagation expert finding method outperforms the method that only uses person local information, and the proposed two-stage association search on a large-scale social network is order of magnitude faster than the baseline method.     

社会网络中基于集合枚举树的k匿名方法

k匿名方法是一种重要的数据隐私保护方法.在应用k匿名方法保护社会网络中用户的隐私时,现有的方法对社会网络的结构进行匿名化处理,当攻击者了解了网络的文本信息后可以很容易识别出用户的身份等隐私信息.为此,提出一种包含结构和文本的k匿名方法.该方法在采用传统的节点度匿名化的基础上,将社会网络中的文本信息分成不同的值域,对每一个值域构建一个全局的层次结构树,对所有的值域采用集合枚举树来优化文本标记泛化时的信息丢失,并针对集合枚举树的特征提出了三种剪枝方法.实验表明,提出的k匿名方法在实现了社会网络的结构和文本匿名化的同时具有较低额的开销.     

A set oriented approach to optimal feedback stabilization

We present a numerical construction of an optimal control based feedback law for the stabilization of discrete time nonlinear control systems. The feedback is based on a recently developed numerical solution method for optimal control problems using set oriented and graph theoretic algorithms. We show how this method can be used to construct approximately optimal and stabilizing feedback laws and present an a posteriori error estimation technique for the adaptive generation of the underlying set oriented space discretization.     

Target oriented network intelligence collection: effective exploration of social networks

World Wide Web - Target Oriented Network Intelligence Collection (TONIC) is a crawling process whose goal is to find social network profiles that contain information about a given target. Such...     

A learning-theory approach to sensor networks

We propose a unified approach to various sensor network applications, using supervised learning. Supervised learning refers to learning from examples, in the form of input-output pairs, by which a system that isn't programmed in advance can estimate an unknown function and predict its values for inputs outside the training set. In particular, we examined random wireless sensor networks, in which nodes are randomly distributed in the region of deployment. When operating normally, nodes communicate and collaborate only with other nearby nodes (within communication range). However, a base station - with a more powerful computer on board - can query a node or group of nodes when necessary and perform data fusion. Learning techniques have been applied in many diverse scenarios. Preliminary research shows that a well-known algorithm from learning theory effectively applies to environmental monitoring, tracking of moving objects and plumes, and localization. We considered some basic concepts of learning theory and how they might address the needs of random wireless sensor networks.     

A social approach to context-aware retrieval

We present a general purpose solution to Web content and services perusal by means of mobile devices, named Social Context-Aware Browser. This is a novel approach for information access based on users’ context, that exploits social and collaborative models to overtake the limits of the existing solutions. Instead of relying on a pool of experts and on a rigid categorization, as it is usually done in the context-aware field, our solution allows the crowd of users to model, control, and manage the contextual knowledge through collaboration and participation. To have a dynamic and user-tailored context representation, and to enhance the process of retrieval based on users’ actual situation, the community of users is encouraged to define the contexts of interest, to share, use, and discuss them, and to associate context to content and resources (Web pages, services, applications, etc.). This paper provides an overall presentation of our solution, describing the idea, the implementation, and the evaluation through a benchmark based methodology.     

Change-aware community detection approach for dynamic social networks

Community mining is one of the most popular issues in social network analysis. Although various changes may occur in a dynamic social network, they can be classified into two categories, gradual changes and abrupt changes. Many researchers have attempted to propose a method to discover communities in dynamic social networks with various changes more accurately. Most of them have assumed that changes in dynamic social networks occur gradually. This presumption for the dynamic social network in which abrupt changes may occur misleads the problem. Few methods have tried to detect abrupt changes, but they used the statistical approach which has such disadvantages as the need for a lot of snapshots. In this paper, we propose a novel method to detect the type of changes using the least information of social networks and then, apply it to a new community detection framework named change-aware model. The experimental results on different benchmark and real-life datasets confirmed that the new method and framework have improved the performance of community detection algorithms.     

A collaborative learning approach for geographic information retrieval based on social networks

Nowadays, spatial and temporal data play an important role in social networks. These data are distributed and dispersed in several heterogeneous data sources. These peculiarities make that geographic information retrieval being a non-trivial task, considering that the spatial data are often unstructured and built by different collaborative communities from social networks. The problem arises when user queries are performed with different levels of semantic granularity. This fact is very typical in social communities, where users have different levels of expertise. In this paper, a novelty approach based on three matching-query layers driven by ontologies on the heterogeneous data sources is presented. A technique of query contextualization is proposed for addressing to available heterogeneous data sources including social networks. It consists of contextualizing a query in which whether a data source does not contain a relevant result, other sources either provide an answer or in the best case, each one adds a relevant answer to the set of results. This approach is a collaborative learning system based on experience level of users in different domains. The retrieval process is achieved from three domains: temporal, geographical and social, which are involved in the user-content context. The work is oriented towards defining a GIScience collaborative learning for geographic information retrieval, using social networks, web and geodatabases.     

A new approach to artificial neural networks

A novel approach to artificial neural networks is presented. The philosophy of this approach is based on two aspects: the design of task-specific networks, and a new neuron model with multiple synapses. The synapses' connective strengths are modified through selective and cumulative processes conducted by axo-axonic connections from a feedforward circuit. This new concept was applied to the position control of a planar two-link manipulator exhibiting excellent results on learning capability and generalization when compared with a conventional feedforward network. In the present paper, the example shows only a network developed from a neuronal reflexive circuit with some useful artifices, nevertheless without the intention of covering all possibilities devised.     

A neural networks approach to minority game

The minority game (MG) comes from the so-called “El Farol bar” problem by W.B. Arthur. The underlying idea is competition for limited resources and it can be applied to different fields such as: stock markets, alternative roads between two locations and in general problems in which the players in the “minority” win. Players in this game use a window of the global history for making their decisions, we propose a neural networks approach with learning algorithms in order to determine players strategies. We use three different algorithms to generate the sequence of minority decisions and consider the prediction power of a neural network that uses the Hebbian algorithm. The case of sequences randomly generated is also studied. Research supported by Local Project 2004–2006 (EX 40%) Università di Foggia. A. Sfrecola is a researcher financially supported by Dipartimento di Scienze Economiche, Matematiche e Statistiche, Università degli Studi di Foggia, Foggia, Italy.     

A metrology-based approach for measuring the social dimension of cognitive trust in collaborative networks

This paper addresses the measurement of the social dimension of cognitive trust in collaborative networks. Trust indicators are typically measured and combined in literature in order to calculate partners’ trustworthiness. When expressing the result of a measurement, some quantitative indication of the quality of the result—the uncertainty of measurement—should be given. However, currently this is not taken into account for the measurement of the social dimension of cognitive trust in collaborative networks. In view of this, an innovative metrology-based approach for the measurement of social cognitive trust indicators in collaborative networks is presented. Thus, a measurement result is always accompanied by its uncertainty of measurement, as well as by information traditionally used to properly interpret the results: the sample size, and the standard deviation of the sample.

     

A modelling approach to Service oriented Architecture for on-line diagnosis

Failure diagnosis is one of the key challenges of Service oriented Architectures. One of the methods of identifying occurrences of failure is to use Diagnosers; software modules or services are deployed with the system to monitor the interaction between services for identifying whether a failure has happened or may have happened. This paper aims to present a suitable modelling framework to allow automated creation of Diagnosers based on Discrete Event System (DES) theory. Coming up with an appropriate modelling language framework is a prerequisite to applying DES techniques. Modelling languages popular in DES, such as Petri nets and automata, despite being sufficiently adequate for modelling, are not well adopted by the SoA community. Inspired by Petri nets and Workflow Graph, the modelling suggested in this paper closely follows BPEL that is widely used by the community. In particular, our language includes constructs that are supported by major tool vendors. To demonstrate that the suggested formal language is a suitable basis for the application of DES theory, we have extended one of the existing DES methods for the creation of centralised Diagnoser. Two algorithms for creating Diagnosers are put forward. These algorithms are applied into the models that are abstracted from the BPEL representation of the involving services. As a proof of concept, an implementation of the suggested approach is created as an Oracle JDeveloper plugin that automatically produces new Diagnosing services and integrates them to work with existing services. The paper ends with a series of empirical results on the performance-related aspects of the proposed method.     

A cost-effective approach to deadlock handling in wormhole networks

Wormhole networks have traditionally used deadlock avoidance strategies. More recently, deadlock recovery strategies have begun to gain acceptance. In particular, progressive deadlock recovery techniques allocate a few dedicated resources to quickly deliver deadlocked packets. Deadlock recovery is based on the assumption that deadlocks are rare; otherwise, recovery techniques are not efficient. Measurements of deadlock occurrence frequency show that deadlocks are highly unlikely when enough routing freedom is provided. However, networks are more prone to deadlocks when the network is close to or beyond saturation, causing some network performance degradation. Similar performance degradation behavior at saturation was also observed in networks using deadlock avoidance strategies. In this paper, we take a different approach to handling deadlocks and performance degradation. We propose the use of an injection limitation mechanism that prevents performance degradation near the saturation point and, at the same time, reduces the probability of deadlock to negligible values. We also propose an improved deadlock detection mechanism that uses only local information, detects all deadlocks, and considerably reduces the probability of false deadlock detection over previous proposals. In the rare case when impending deadlock is detected, our proposal consists of using a simple recovery technique that absorbs the deadlocked message at the current node and later reinjects it for continued routing toward its destination. Performance evaluation results show that our new approach to handling deadlock is more efficient than previously proposed techniques     

A game-theoretic approach to advertisement dissemination in ephemeral networks

In ephemeral networks, disseminating advertisements faces two dilemmatic problems: on the one hand, disseminators own the limited resources and have privacy concerns, thus, often preferring to avoid disseminating advertisements without enough incentives; Even if advertisements are disseminated, their dissemination accuracy is lower. On the other hand, false advertisements may flood in ephemeral networks if too many incentives but no punishments are given. Thus, it is a challenge to design an effective scheme to guarantee rational disseminators have sufficient impetus to forward true advertisements to the interested consumers and report false advertisements, despite facing the limitation of resources and the risk of privacy leakage. To solve this problem, in this paper, a bargaining-based scheme is proposed to motive disseminators to forward the true advertisements to the interested node and a semi-grim policy is designed for punishing the disseminators who releases and disseminates false advertisements. Acknowledging the assumption of incomplete information, a repeated dissemination game is proposed to help disseminators to decide whether to forward advertisements or report false advertisements. Simulation results demonstrate that our scheme not only provides disseminators a strong impetus to disseminate the advertisements with higher dissemination accuracy, but also effectively prevents disseminators from forwarding false advertisements.     

User-centric social context information management: an ontology-based approach and platform

Social context information has been used with encouraging results in developing socially aware applications in different domains. However, users’ social context information is distributed over the Web and managed by many different proprietary applications, which is a challenge for application developers as they must collect information from different sources and wade through a lot of irrelevant information to obtain the social context information of interest. On the other hand, it is extremely hard for information owners to control how their information should be exposed to different users and applications. Combining the social context information from the diverse sources, incorporating richer semantics and preserving information owners’ privacy could greatly assist the developers and as well as the information owners. In this paper, we introduce a social context information management system (SCIMS). It includes the ability to acquire raw social data from multiple sources; an ontology-based model for classifying, inferring and storing social context information, in particular, social relationships and status; an ontology-based policy model and language for owners to control access to their information; a query interface for accessing and utilizing social context information. We evaluate the performance of SCIMS using real data from Facebook, LinkedIn, Twitter, and Google Calendar and demonstrate its applicability through a socially aware phone call application.