Where is evolutionary computation going? A temporal analysis of the EC community

Studying an evolving complex system and drawing some conclusions from it is an integral part of nature-inspired computing; being a part of that complex system, some insight can also be gained from our knowledge of it. In this paper we study the evolution of the evolutionary computation co-authorship network using social network analysis tools, with the aim of extracting some conclusions on its mechanisms. In order to do this, we first examine the evolution of macroscopic properties of the EC co-authorship graph, and then we look at its community structure and its corresponding change along time. The EC network is shown to be in a strongly expansive phase, exhibiting distinctive growth patterns, both at the macroscopic and the mesoscopic level.

Modelling opinion formation driven communities in social networks

In a previous paper we proposed a model to study the dynamics of opinion formation in human societies by a co-evolution process involving two distinct time scales of fast transaction and slower network evolution dynamics. In the transaction dynamics we take into account short range interactions as discussions between individuals and long range interactions to describe the attitude to the overall mood of society. The latter is handled by a uniformly distributed parameter α, assigned randomly to each individual, as quenched personal bias. The network evolution dynamics is realised by rewiring the societal network due to state variable changes as a result of transaction dynamics. The main consequence of this complex dynamics is that communities emerge in the social network for a range of values in the ratio between time scales. In this paper we focus our attention on the attitude parameter α and its influence on the conformation of opinion and the size of the resulting communities. We present numerical studies and extract interesting features of the model that can be interpreted in terms of social behaviour.     

Cluster ranking with an application to mining mailbox networks

We initiate the study of a new clustering framework, called cluster ranking. Rather than simply partitioning a network into clusters, a cluster ranking algorithm also orders the clusters by their strength. To this end, we introduce a novel strength measure for clusters—the integrated cohesion—which is applicable to arbitrary weighted networks. We then present a new cluster ranking algorithm, called C-Rank. We provide extensive theoretical and empirical analysis of C-Rank and show that it is likely to have high precision and recall. A main component of C-Rank is a heuristic algorithm for finding sparse vertex separators. At the core of this algorithm is a new connection between vertex betweenness and multicommodity flow. Our experiments focus on mining mailbox networks. A mailbox network is an egocentric social network, consisting of contacts with whom an individual exchanges email. Edges between contacts represent the frequency of their co–occurrence on message headers. C-Rank is well suited to mine such networks, since they are abundant with overlapping communities of highly variable strengths. We demonstrate the effectiveness of C-Rank on the Enron data set, consisting of 130 mailbox networks.     

Predicting unobserved links in incompletely observed networks

In this paper we consider networks in which the links (edges) are imperfectly observed. This may be a result of sampling, or it may be caused by actors (vertices) who are actively attempting to hide their links (edges). Thus the network is incompletely observed, and we wish to predict which of the possible unobserved links are actually present in the network. To this end, we apply a constrained random dot product graph (CRDPG) to rank the potential edges according to the probability (under the model) that they are in fact present. This model is then extended to utilize covariates measured on the actors, to improve the link prediction. The method is illustrated on a data set of alliances between nations, in which a subset of the links (alliances) is assumed unobserved for the purposes of illustration.     

The nature of virtual communities

The impressive development of electronic communication techniques has given rise to virtual communities. The nature of these computer-mediated communities has been the subject of much recent debate. Are they ordinary social groups in electronic form, or are they fundamentally different from traditional communities? Understanding virtual communities seems a prerequisite for the design of better communication systems. To clarify this debate, we will resort to the classical sociological distinction between small traditional communities (based on personal relations) and modern social groups (bound by looser, more impersonal links). We will argue that the discussion about virtual communities is often vitiated by a simplistic assimilation to traditional communities, whereas they may be in fact quite different and much more impersonal. Virtual communities are often bound by reference to common objects or goals, and not by personal relations. In this respect, virtual communities are just another example of a long-term evolution of modern society toward more abstract social relationships.     

Stochastic graph as a model for social networks

Social networks are usually modeled and represented as deterministic graphs with a set of nodes as users and edges as connection between users of networks. Due to the uncertain and dynamic nature of user behavior and human activities in social networks, their structural and behavioral parameters are time varying parameters and for this reason using deterministic graphs for modeling and analysis of behavior of users may not be appropriate. In this paper, we propose that stochastic graphs, in which weights associated with edges are random variables, may be a better candidate as a graph model for social network analysis. Thus, we first propose generalization of some network measures for stochastic graphs and then propose six learning automata based algorithms for calculating these measures under the situation that the probability distribution functions of the edge weights of the graph are unknown. Simulations on different synthetic stochastic graphs for calculating the network measures using the proposed algorithms show that in order to obtain good estimates for the network measures, the required number of samples taken from edges of the graph is significantly lower than that of standard sampling method aims to analysis of human behavior in online social networks.     

“With a little help from new friends”: Boosting information cascades in social networks based on link injection

We investigate information cascades in the context of viral marketing applications. Recent research has identified that communities in social networks may hinder cascades. To overcome this problem, we propose a novel method for injecting social links in a social network, aiming at boosting the spread of information cascades. Unlike the proposed approach, existing link prediction methods do not consider the optimization of information cascades as an explicit objective. In our proposed method, the injected links are being predicted in a collaborative-filtering fashion, based on factorizing the adjacency matrix that represents the structure of the social network. Our method controls the number of injected links to avoid an “aggressive” injection scheme that may compromise the experience of users. We evaluate the performance of the proposed method by examining real data sets from social networks and several additional factors. Our results indicate that the proposed scheme can boost information cascades in social networks and can operate as a “people recommendations” strategy complementary to currently applied methods that are based on the number of common neighbors (e.g., “friend of friend”) or on the similarity of user profiles.     

A framework for exploring organizational structure in dynamic social networks

Recent research has provided promising results relating to discovering communities within a social network. We find that further representing the organizational structure of a social network is an interesting issue that helps gain better understandings of the social network. In this paper, we define a data structure, named Community Tree, to depict the organizational structure and provide a framework for exploring the organizational structure in a social network. In this framework, an algorithm, which combines a modified PageRank and Random Walk on graph, is developed to derive the community tree from the social network. In the real world, a social network is constantly evolving. In order to explore the organizational structure in a dynamic social network, we develop a tree learning algorithm, which employs tree edit distance as the scoring function, to derive an evolving community tree that enables a smooth transition between two community trees. We also propose an approach to threading communities in community trees to obtain an evolution graph of the organizational structure, by which we can reach new insights from the dynamic social network. The experiments conducted on synthetic and real dataset demonstrate the feasibility and applicability of the framework. Based on the theoretical outcomes, we further apply the proposed framework to explore the evolution of organizational structure with the 2001 Enron dataset, and obtain several interesting findings that match the context of Enron.     

Perspectives on the evolution of online communities

The rapid growth of social networks opens interesting research opportunities to make use of the massive information exchanged in day-to-day communication. One of the active research issues related to this aspect is the study of online community formation and evolution in dynamic social networks. As community structure is usually ambiguous, then defining how it evolves over time becomes a challenge in terms of tracking mechanism and evaluation method. In this study, we review the online communities and their evolution tracking mechanisms and discuss the main categories of approaches for tracking community evolution and how they work. We analyse the different solutions proposed under each community evolution tracking category and provide an assessment of their projected performance. Finally, a discussion of analysis insights concerning community evolution and its influence is introduced.     

一种面向度中心性及重叠网络社区的发现算法

针对社会网络中存在较多以度中心节点为中心并且具有多社区重叠节点的网络社区结构,提出了一种面向度中心性及重叠网络社区的两阶段发现算法。第一阶段发现初始社区:选取度最大的Top-k个节点作为候选中心节点,并将每个节点与其邻居节点形成候选初始社区,其中如果某候选社区与已形成的初始社区的重叠度低于阈值,则形成一个新的初始社区;第二阶段调整社区划分:通过偏离度机制进行调整,将偏离度最大值对应的节点划分到连接紧密的相应社区内,形成最终社区划分。实验表明,该方法不仅能够揭示网络中以某个节点为中心的密集的社区结构,还能有效处理初始社区不同程度的重叠问题。相比现有算法,所提方法对预先输入的候选初始社区数k值不敏感,并具有较高的准确性和灵活性。     

Alt.support: modeling social support online

While there is mounting evidence that people use the Internet to expand their social networks and receive social support, little is known about how they do so and with what effect the Internet has on overall levels of social support. Based on a survey of 213 online support seekers, this study explored social cognitive mechanism such as self-efficacy and outcome expectations as predictors of support activity, online support reliance and support network size. From these relationships, we offer preliminary evidence suggesting that those who actively seek social support online are indeed finding it through a complex support system beginning with self-regulation.     

An empirical study of the factors affecting social network service use

Social network services are emerging as a promising IT-based business, with some services already being provided commercially such as Facebook, Cyworld and Xiaonei. However, it is not yet clear which potential audience groups will be key social network service participants. Moreover, the process showing how an individual actually decides to start using a social network service may be somewhat different from current web-based community services. Hence, the aims of this paper are twofold. First, we empirically examine how individual characteristics affect actual user acceptance of social network services. To examine these individual characteristics, we apply a Technology Acceptance Model (TAM) to construct an amended model that focuses on three individual differences: social identity, altruism and telepresence, and one perceived construct: the perceived encouragement, imported from psychology-based research. Next, we examine if the users’ perception to see a target social network service as human relationship-oriented service or as a task-oriented service could be a moderator between perceived constructs and actual use. As a result, we discover that the perceived encouragement and perceived orientation are significant constructs that affect actual use of social network services.     

Computing in social networks with relationship algebra

Communities are the latest phenomena on the Internet. At the heart of each community lies a social network. In this paper, we show a generalized framework to understand and reason in social networks. Previously, researchers have attempted to use inference-specific type of relationships. We propose a framework to represent and reason with general case of social relationship network in a formal way. We call it relationship algebra. In the paper, we first present this algebra then show how this algebra can be used for various interesting computing on a social network weaved in the virtual communities. We show applications such as determining reviewers in a semi-professional network maintained by conference management systems, finding conflict of interest in a publication system, or to infer various trust relationships in a community of close associates, etc. We also show how future community networks can be used to determine who should be immunized in the case of a contagious disease outbreak and how these networks could be used in crime prevention, etc.     

The impact of self-selected identity on productive or perverse social capital in social network sites

Social network sites can provide a person with the freedom to represent themselves in various ways, thus exhibiting multiple variations of their identity. Research states that an individual’s identity is self-monitored depending on the contextual situation that they are in. The type of social capital that one derives from social network sites can be impacted by this self-monitoring ability. Current research has addressed how productive social capital can be gained in social network sites. However, limited research has addressed the issue of perverse social capital, especially in social network sites. We argue that social network sites are a particularly unique environment that can affect an individual’s representation of their identity, thus increasing the likelihood of producing perverse social capital. We examine how technology affects an individual’s selected self-identity, as measured through their self-monitoring ability, and how this altered behavior leads to productive or perverse social capital in social network sites.     

Visual analysis of social networks in space and time using smartphone logs

We designed and applied interactive visualisation techniques for investigating how social networks are embedded in time and space, using data collected from smartphone logs. Our interest in spatial aspects of social networks is that they may reveal associations between participants missed by simply making contact through smartphone devices. Four linked and co-ordinated views of spatial, temporal, individual and social network aspects of the data, along with demographic and attitudinal variables, helped add context to the behaviours we observed. Using these techniques, we were able to characterise spatial and temporal aspects of participants’ social networks and suggest explanations for some of them. This provides some validation of our techniques.Unexpected deficiencies in the data that became apparent prompted us to evaluate the dataset in more detail. Contrary to what we expected, we found significant gaps in participant records, particularly in terms of location, a poorly connected sample of participants and asymmetries in reciprocal call logs. Although the data captured are of high quality, deficiencies such as these remain and are likely to have a significant impact on interpretations relating to spatial aspects of the social network. We argue that appropriately-designed interactive visualisation techniques–afforded by our flexible prototyping approach–are effective in identifying and characterising data inconsistencies. Such deficiencies are likely to exist in other similar datasets, and although the visual approaches we discuss for identifying data problems may not be scalable, the categories of problems we identify may be used to inform attempts to systematically account for errors in larger smartphone datasets.     

An approach for community detection in social networks based on cooperative games theory

Detecting communities is of great importance in social network analysis. However it is an issue that has not yet been satisfactorily solved, despite the efforts made by interdisciplinary research communities over the past few years, because of the nature of complexity in deciding how community structures should be recognized. In this paper we propose an approach based on cooperative game theory for community detection in social networks. We regard individuals as players, and regard communities as coalitions formed by players, and model community detection problem as the formation and optimization of coalitions. Furthermore, we define coalition profile for players to indicate coalitions that players joined, the order of a coalition profile is defined as the number of coalitions in a coalition profile, and we introduce a utility function to measure preference of coalition profiles. Accordingly, we propose an algorithm to detect a coalition profile with maximal utility function values. We have implemented the algorithms developed in this study and experimental results demonstrate the effectiveness of our approaches.     

A model of a trust-based recommendation system on a social network

In this paper, we present a model of a trust-based recommendation system on a social network. The idea of the model is that agents use their social network to reach information and their trust relationships to filter it. We investigate how the dynamics of trust among agents affect the performance of the system by comparing it to a frequency-based recommendation system. Furthermore, we identify the impact of network density, preference heterogeneity among agents, and knowledge sparseness to be crucial factors for the performance of the system. The system self-organises in a state with performance near to the optimum; the performance on the global level is an emergent property of the system, achieved without explicit coordination from the local interactions of agents.     

GeoSRS: A hybrid social recommender system for geolocated data

We present GeoSRS, a hybrid recommender system for a popular location-based social network (LBSN), in which users are able to write short reviews on the places of interest they visit. Using state-of-the-art text mining techniques, our system recommends locations to users using as source the whole set of text reviews in addition to their geographical location. To evaluate our system, we have collected our own data sets by crawling the social network Foursquare. To do this efficiently, we propose the use of a parallel version of the Quadtree technique, which may be applicable to crawling/exploring other spatially distributed sources. Finally, we study the performance of GeoSRS on our collected data set and conclude that by combining sentiment analysis and text modeling, GeoSRS generates more accurate recommendations. The performance of the system improves as more reviews are available, which further motivates the use of large-scale crawling techniques such as the Quadtree.     

Why do people share their context information on Social Network Services? A qualitative study and an experimental study on users' behavior of balancing perceived benefit and risk

Despite the rapid growth of context-aware systems and ubiquitous computing, the factors influencing users' decision to share their context information in a social setting are poorly understood. This study aims to clarify why users share their context information in social network service (SNS), even while they are concerned with the potential risk at the same time. Drawing on the diverse theories of self-disclosure, we take an approach that the consideration of benefit encourages users to endure the existence of risk, and that users actively adjust the way they share their information to optimize the level of benefit and risk. In a qualitative study, we examined what kinds of risks and benefits exist in context information sharing situations and how users control them. An experiment was conducted using stimuli that simulate the actual use of SNS to investigate the effect of various context types and control types on users' expected benefit and risk and their intention to share. The results showed that both expected benefit and expected risk influenced users' intention to share. More interestingly, the effect of expected benefit was found to be stronger than that of expected risk. Moreover, different privacy control strategies were found to have induced different effects on the expected benefit and expected risk. Implications and limitations of this study were proposed at the end of this study.     

Multiobjective approach for detecting communities in heterogeneous networks

Online social networks have a strong potential to be divided into a number of dense substructures, called communities. In such heterogeneous networks, the communities refer not only to dense parts of links but also to clusters present among other dimensions such as users' profiles, comments, and information flows. To find communities in these networks, researchers have developed a number of methods; however, to the best of the authors' knowledge, these methods are limited in taking only 2 dimensions into account, and they are also not able to give a sense of how users behave in their communities. To deal with these issues, this paper proposes a multiobjective optimization model in which a specific objective function has been used for each considered dimension in a given network. Because of the NP‐hardness of the studied problem, an efficient and effective multiobjective metaheuristic algorithm has been developed. By juxtaposing the nondominated solutions obtained, the proposed algorithm can demonstrate how users behave in their communities. To illustrate the effectiveness of the algorithm, a set of experiments with a comprehensive evaluation method is provided. The results show the superiority and the stability of the proposed algorithm.