Influence maximization with limit cost in social network

Social networking service (SNS) applications are changing the way information spreads in online communities. As real social relationships are projected into SNS applications, word of mouth has been an important factor in the information spreading processes of those applications. By assuming each user needs a cost to accept some specific information, this paper studies the initial "seed user" selection strategy to maximize information spreading in a social network with a cost budget. The main contributions of this paper are: 1) proposing a graphic SEIR model (gSEIR) by extending the epidemic compartmental model to simulate the dynamic information spreading process between individuals in the social network; 2) proposing a formal definition for the influence maximization problem with limit cost (IMLC) in social networks, and proving that this problem can be transformed to the weighted set-cover problem (WSCP) and thus is NP-Complete; 3) providing four different greedy algorithms to solve the IMLC problem; 4) proposing a heuristic algorithm based on the method of Lagrange multipliers (HILR) for the same problem; 5) providing two parts of experiments to test the proposed models and algorithms in this paper. In the first part, we verify that gSEIR can generate similar macro-behavior as an SIR model for the information spreading process in an online community by combining the micro-behaviors of all the users in that community, and that gSEIR can also simulate the dynamic change process of the statuses of all the individuals in the corresponding social networks during the information spreading process. In the second part, by applying the simulation result from gSEIR as the prediction of information spreading in the given social network, we test the effectiveness and efficiency of all provided algorithms to solve the influence maximization problem with cost limit. The result show that the heuristic algorithm HILR is the best for the IMLC problem.     

Restricted Bayesian classification networks

Bayesian networks are graphical models that describe dependency relationships between variables, and are powerful tools for studying probability classifiers. At present, the causal Bayesian network learning method is used in constructing Bayesian network classifiers while the contribution of attribute to class is over-looked. In this paper, a Bayesian network specifically for classification-restricted Bayesian classification networks is proposed. Combining dependency analysis between variables, classification accuracy evaluation criteria and a search algorithm, a learning method for restricted Bayesian classification networks is presented. Experiments and analysis are done using data sets from UCI machine learning repository. The results show that the restricted Bayesian classification network is more accurate than other well-known classifiers.     

Personalized Tag Recommendation Using Social Influence

Tag recommendation encourages users to add more tags in bridging the semantic gap between human concept and the features of media object,which provides a feasible solution for content-based multimedia information retrieval.In this paper,we study personalized tag recommendation in a popular online photo sharing site - Flickr.Social relationship information of users is collected to generate an online social network.From the perspective of network topology,we propose node topological potential to characterize user’s social influence.With this metric,we distinguish different social relations between users and find out those who really have influence on the target users.Tag recommendations are based on tagging history and the latent personalized preference learned from those who have most influence in user’s social network.We evaluate our method on large scale real-world data.The experimental results demonstrate that our method can outperform the non-personalized global co-occurrence method and other two state-of-the-art personalized approaches using social networks.We also analyze the further usage of our approach for the cold-start problem of tag recommendation.     

Multidimensional Projections for Visual Analysis of Social Networks

Visual analysis of social networks is usually based on graph drawing algorithms and tools.However,social networks are a special kind of graph in the sense that interpretation of displayed relationships is heavily dependent on context.Context,in its turn,is given by attributes associated with graph elements,such as individual nodes,edges,and groups of edges,as well as by the nature of the connections between individuals.In most systems,attributes of individuals and communities are not taken into consideration during graph layout,except to derive weights for force-based placement strategies.This paper proposes a set of novel tools for displaying and exploring social networks based on attribute and connectivity mappings.These properties are employed to layout nodes on the plane via multidimensional projection techniques.For the attribute mapping,we show that node proximity in the layout corresponds to similarity in attribute,leading to easiness in locating similar groups of nodes.The projection based on connectivity yields an initial placement that forgoes force-based or graph analysis algorithm,reaching a meaningful layout in one pass.When a force algorithm is then applied to this initial mapping,the final layout presents better properties than conventional force-based approaches.Numerical evaluations show a number of advantages of pre-mapping points via projections.User evaluation demonstrates that these tools promote ease of manipulation as well as fast identification of concepts and associations which cannot be easily expressed by conventional graph visualization alone.In order to allow better space usage for complex networks,a graph mapping on the surface of a sphere is also implemented.     

An Effective Framework for Fast Expert Mining in Collaboration Networks: A Group-Oriented and Cost-Based Method

The growth of social networks in modern information systems has enabled the collaboration of experts at a scale that was unseen before.Given a task and a graph of experts where each expert possesses some skills,we tend to find an effective team of experts who are able to accomplish the task.This team should consider how team members collaborate in an effective manner to perform the task as well as how efficient the team assignment is,considering each expert has the minimum required level of skill.Here,we generalize the problem in multiple perspectives.First,a method is provided to determine the skill level of each expert based on his/her skill and collaboration among neighbors.Second,the graph is aggregated to the set of skilled expert groups that are strongly correlated based on their skills as well as the best connection among them.By considering the groups,search space is significantly reduced and moreover it causes to prevent from the growth of redundant communication costs and team cardinality while assigning the team members.Third,the existing RarestFirst algorithm is extended to more generalized version,and finally the cost definition is customized to improve the efficiency of selected team.Experiments on DBLP co-authorship graph show that in terms of efficiency and effectiveness,our proposed framework is achieved well in practice.     

Local Community Detection Using Link Similarity

Exploring local community structure is an appealing problem that has drawn much recent attention in the area of social network analysis.As the complete information of network is often difficult to obtain,such as networks of web pages,research papers and Facebook users,people can only detect community structure from a certain source vertex with limited knowledge of the entire graph.The existing approaches do well in measuring the community quality,but they are largely dependent on source vertex and putting too strict policy in agglomerating new vertices.Moreover,they have predefined parameters which are difficult to obtain.This paper proposes a method to find local community structure by analyzing link similarity between the community and the vertex.Inspired by the fact that elements in the same community are more likely to share common links,we explore community structure heuristically by giving priority to vertices which have a high link similarity with the community.A three-phase process is also used for the sake of improving quality of community structure.Experimental results prove that our method performs effectively not only in computer-generated graphs but also in real-world graphs.     

Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks

In this paper,we propose a balanced multi-label propagation algorithm(BMLPA) for overlapping community detection in social networks.As well as its fast speed,another important advantage of our method is good stability,which other multi-label propagation algorithms,such as COPRA,lack.In BMLPA,we propose a new update strategy,which requires that community identifiers of one vertex should have balanced belonging coefficients.The advantage of this strategy is that it allows vertices to belong to any number of communities without a global limit on the largest number of community memberships,which is needed for COPRA.Also,we propose a fast method to generate rough cores,which can be used to initialize labels for multi-label propagation algorithms,and are able to improve the quality and stability of results.Experimental results on synthetic and real social networks show that BMLPA is very efficient and effective for uncovering overlapping communities.     

在线社会网络的k-shell结构研究

分析研究了Twitter与You Tube两个在线社会网络的结构。用k-shell(k-壳)分解法对网络分解,并对比分析了它们的入(出)度、入(出)k-shell、以及度与k-shell之间的关系,发现它们之间有较大的差异。You Tube的入(出)度、入(出)k-shell分布均服从幂律分布,而Twitter的分布服从漂移幂律分布、指数截断的幂律分布,但它们的度与k-shell关系基本相同,都未表现出较强的相关性。此外,根据度相关系数的定义还提出k-shell相关性的定义及其计算方法,并用来刻画网络k-shell之间的同(异)配性。     

基于社会网络的群体情绪模型

为了能够深入认识群体事件中群体情绪的演化过程,提出了基于社会人际关系的群体情绪模型构建方法。以小世界网络模型构建个体间社会关系,并通过引入情感关系参数表达现实生活中个体间的强情感、弱情感和陌生关系。基于Bosse等人提出的群体情绪模型,以社会网络作为情绪传播媒介对不同类别人际关系情境中群体情绪的演化态势进行了实验模拟,分析了近邻数K、重连概率P和情感关系R对群体情绪涌现所产生的影响。结果表明,情感关系越亲近、近邻数K越大,群体情绪最终的强度则越强烈,情绪涌现所需时间越短;重连概率P对群体情绪强度也有微弱影响,但作用并不十分显见。     

Asymptotic behaviours of a class of threshold models for collective action in social networks

A class of dynamic threshold models is proposed for describing the upset of collective actions in social networks. The agents of the network have to decide whether to undertake certain action or not. They make their decision by comparing the activity level of their neighbours with a time-varying threshold, evolving according to a time-invariant opinion dynamic model. Key features of the model are a parameter representing the degree of self-confidence of the agents and the mechanism adopted by the agents to evaluate the activity level of their neighbours. The case in which a radical agent, initially eager to undertake the action, interacts with a group of ordinary agents, is considered. The main contribution of the paper is the complete characterisation of the asymptotic behaviours of the network, for three different graph topologies. The asymptotic activity patterns are determined as a function of the self-confidence parameter and of the initial threshold of the ordinary agents. Numerical validation on a real ego network shows that the theoretical results obtained for simple graph structures provide useful insights on the network behaviour in more complex settings.     

Examining online citizenship behaviours in social network sites: a social capital perspective

As users have flocked to social network sites (SNSs), these sites have gained tremendous scale and concomitant social influence. This growth has come at the cost of social disruption caused by the posting of abusive comments and rumours that turn out to be false. To combat these negative phenomena, this study proposes SNS citizenship behaviour and examines it from the perspective of social capital theory. This study further examines how the key characteristics of SNS in terms of the concept of customer value affect social capital development in an SNS context. The test results explain that the structural, relational, and cognitive dimensions of social capital have significant direct and indirect effects on the SNS citizenship behaviour. These findings also explain that four key characteristics (exploration, communication support, playfulness, and responsiveness) of SNS affect the three dimensions of social capital. This study contributes to the literature in its establishment of the concept of SNS citizenship behaviour and examines it from the social capital theory perspective. Its findings have practical implications through its guidance on how to develop SNS features and manage these sites for the citizenship behaviour of their users, which are achievements for the harmonious and effective functioning of SNS.     

Analyzing market performance via social media: a case study of a banking industry crisis

Analyzing market performance via social media has attracted a great deal of attention in the finance and machine-learning disciplines.However,the vast majority of research does not consider the enormous influence a crisis has on social media that further affects the relationship between social media and the stock market.This article aims to address these challenges by proposing a multistage dynamic analysis framework.In this framework,we use an authorship analysis technique and topic model method to identify stakeholder groups and topics related to a special firm.We analyze the activities of stakeholder groups and topics in different periods of a crisis to evaluate the crisis’s influence on various social media parameters.Then,we construct a stock regression model in each stage of crisis to analyze the relationships of changes among stakeholder groups/topics and stock behavior during a crisis.Finally,we discuss some interesting and significant results,which show that a crisis affects social media discussion topics and that different stakeholder groups/topics have distinct effects on stock market predictions during each stage of a crisis.     

GAMLSS and neural networks in combat simulation metamodelling: A case study

The GAMLSS (Generalised Additive Models for Location, Scale and Shape) regression approach is compared to neural networks in the context of modelling the relationship between the inputs and outputs of the stochastic combat simulation model SIMBAT. The similarities and differences in these modelling approaches, and their advantages and disadvantages in this case, are discussed. Comparison of out-of-sample prediction suggests that some GAMLSS models are better able to cope with skewed data, but otherwise performance is broadly similar.     

PAIDD: a hybrid P2P-based architecture for improving data distribution in social networks

Rapid growth in social networks(SNs)presents a unique scalability challenge for SN operators because of the massive amounts of data distribution among large number of concurrent online users.A request from any user may trigger hundreds of server activities to generate a customized page and which has already become a huge burden.Based on the theoretical model and analytical study considering realistic network scenarios,this article proposes a hybrid P2P-based architecture called PAIDD.PAIDD fulfills effective data distribution primarily through P2P connectivity and social graph among users but with the help of central servers.To increase system efficiency,PAIDD performs optimized content prefetching based on social interactions among users.PAIDD chooses interaction as the criteria because user’s interaction graph is measured to be much smaller than the social graph.Our experiments confirm that PAIDD ensures satisfactory user experience without incurring extensive overhead on clients’network.More importantly,PAIDD can effectively achieve one order of magnitude of load reduction at central servers.     

Developer social networks in software engineering:construction,analysis,and applications

With the increasing popularity of Internet, more and more developers are collaborating together for software development. During the collaboration, a lot of information related to software development, including communication and coordination information of developers, can be recorded in software repositories. The information can be employed to construct Developer Social Networks （DSNs） for facilitating tasks in software engineering. In this paper, we survey recent advances of DSNs and examine three fundamental steps of DSNs, namely construction, analysis, and applications. We summarize the state-of-the-art methods in the three steps and investigate the relationships among them. Furthermore, we discuss the main issues and point out the future opportunities in the study of DSNs.     

Virtual vignettes: the acquisition,analysis, and presentation of social network data

Online social networks （OSNs） are immensely important part of the modern, developed society. However digital forensic investigators who have no experience online prevalent and have now become a ubiquitous and online social networks pose significant problems to Data will reside on multiples of servers in multiple countries, across multiple jurisdictions. Capturing it before it is overwritten or deleted is a known problem, mirrored in other cloud based services. In this article, a novel method has been developed for the extraction, analysis, visualization, and comparison of snapshotted user profile data from the online social network Twitter. The research follows a process of design, implementation, simulation, and experimentation. Source code of the tool that was developed to facilitate data extraction has been made available on the Internet.