Narrow Results

With the popularization of social networks, the source detection problem has attracted a lot of attention since rumors can spread widely in social networks in a short time. Some existing heuristic methods tend to choose the most influential user as the source, which may result in inaccurate results. Besides, some solutions based on maximum likelihood estimation (MLE) are also proposed, where the key issue is to quantify the probability of a source activating a nonadjacent user. Although Monte Carlo method can be used to estimate this probability, it is extremely time-consuming for large-scale networks. To address this problem, we adopt the duplicate forwarding model to analyze the diffusion process in social networks, which is close to the independent cascade model. Then we calculate the probability that a user receives at least one message after a source generates a message, and use it to detect the source by adopting MLE. Besides, to make research cases more reasonable, we consider snapshots where at least two active users are observed after the diffusion process terminates. Then we need to adjust the likelihood estimation to get better results. Experimental results demonstrate that our method not only achieves better accuracy but also consumes less time than referenced methods. We believe the method proposed here offers valuable insights to solve the source detection problem in large-scale networks.

In today’s world, the web is a prominent communication channel. However, the variety of strategies available on event-based social networks (EBSNs) also makes it difficult for users to choose the events that are most relevant to their interests. In EBSNs, searching for events that better fit a user’s preferences are necessary, complex, and time consuming due to a large number of events available. Toward this end, a community-contributed data event recommender framework assists consumers in filtering daunting information and providing appropriate feedback, making EBSNs more appealing to them. A novel customized event recommendation system that uses the “multi-criteria decision-making (MCDM) approach” to rank the events is introduced in this research work. The calculation of categorical, geographical, temporal, and social factors is carried out in the proposed model, and the recommendation list is ordered using a contextual post-filtering system that includes Weight and Filter. To align the recommendation list, a new probabilistic weight model is added. To be more constructive, this model incorporates metaheuristic reasoning, which will fine-tune the probabilistic threshold value using a new hybrid algorithm. The proposed hybrid model is referred to as Beetle Swarm Hybridized Elephant Herding Algorithm (BSH-EHA), which combines the algorithms like Elephant Herding Optimization (EHO) and Beetle Swarm Optimization (BSO) Algorithm. Finally, the top recommendations will be given to the users.

Static Edge Voting Model is a random graph model that implements a streamlined approach to graph construction. Within this framework, a finite set of nodes constitutes the network, where each node establishes connections by “voting” for potential edges, influenced by their unique states. The probability of forming a connection between two distinct nodes depends on the aggregate votes. This study demonstrates how this model can be employed to generate networks that exhibit the key attributes of socially constructed networks. These networks have a giant component, are small-worlds, have a fat-tailed degree distribution, exhibit high clustering coefficients and assortative. The model’s parameters are intuitively interpretable, allowing for the manipulation of different network properties to quantify their impact on various processes.

We study how a monopolist seller should price an indivisible product iteratively to the consumers who are connected by a known link-weighted directed social network. For two consumers $u$ and $v$, there is an arc directed from $u$ to $v$ if and only if $v$ is a fashion leader of $u$. Assuming complete information about the network, the seller offers consumers a sequence of prices over time and the goal is to obtain the maximum revenue. We assume that the consumers buy the product as soon as the seller posts a price not greater than their valuations of the product. The product’s value for a consumer is determined by three factors: a fixed consumer specified intrinsic value and a variable positive (resp. negative) externality that is exerted from the consumer’s out(resp. in)-neighbours. The setting of positive externality is that the influence of fashion leaders on a consumer is the total weight of links from herself to her fashion leaders who have owned the product, and more fashion leaders of a consumer owning the product will increase the influence (external value) on the consumer. And the setting of negative externalities is that the product’s value of showing off for a consumer is the total weight of links from her followers who do not own the product to herself, and more followers of a consumer owning the product will decrease this external value for the consumer. We confirm that finding an optimal iterative pricing is NP-hard even for acyclic networks with maximum total degree $3$ and with all intrinsic values zero. We design a greedy algorithm which achieves $(n-1)$-approximation for networks with all intrinsic values zero and show that the approximation ratio $n-1$ is tight. Complementary to the hardness result, we design a $(1.8+𝜖)$-approximation algorithm for Barabási–Albert networks.

The graph clustering problem has become highly relevant due to the growing interest of several research communities in social networks and their possible applications. Overlapped graph clustering algorithms try to find subsets of nodes that can belong to different clusters. In social network-based applications it is quite usual for a node of the network to belong to different groups, or communities, in the graph. Therefore, algorithms trying to discover, or analyze, the behavior of these networks needed to handle this feature, detecting and identifying the overlapped nodes. This paper shows a soft clustering approach based on a genetic algorithm where a new encoding is designed to achieve two main goals: first, the automatic adaptation of the number of communities that can be detected and second, the definition of several fitness functions that guide the searching process using some measures extracted from graph theory. Finally, our approach has been experimentally tested using the Eurovision contest dataset, a well-known social-based data network, to show how overlapped communities can be found using our method.

The introduction of trust-based approaches in social scenarios modeled as multi-agent systems (MAS) has been recognized as a valid solution to improve the effectiveness of these communities. In fact, they make interactions taking place in social scenarios much fruitful as possible, limiting or even avoiding malicious or fraudulent behaviors, including collusion. This is also the case of multi-layered neural networks (NN), which can face limited, incomplete, misleading, controversial or noisy datasets, produced by untrustworthy agents. Many strategies to deal with malicious agents in social networks have been proposed in the literature. One of the most effective is represented by Eigentrust, often adopted as a benchmark. It can be seen as a variation of PageRank, an algorithm for determining result rankings used by search engines like Google. Moreover, Eigentrust can also be viewed as a linear neural network whose architecture is represented by the graph of Web pages. A major drawback of Eigentrust is that it uses some additional information about agents that can be a priori considered particularly trustworthy, rewarding them in terms of reputation, while the non pre-trusted agents are penalized. In this paper, we propose a different strategy to detect malicious agents which does not modify the real reputation values of the honest ones. We introduce a measure of effectiveness when computing reputation in presence of malicious agents. Moreover, we define a metric of error useful to quantitatively determine how much an algorithm for the identification of malicious agents modifies the reputation scores of the honest ones. We have performed an experimental campaign of mathematical simulations on a dynamic multi-agent environment. The obtained results show that our method is more effective than Eigentrust in determining reputation values, presenting an error which is about a thousand times lower than the error produced by Eigentrust on medium-sized social networks.

We present a simple model for growing up and depletion of parties due to the permanent communication between the participants of the events. Because of the rapid exchange of information, everybody is able to evaluate its own and all other parties by means of the list of its friends. Therefore, the number of participants at different parties can be changed incessantly. Depending on the depth of the social contacts, which will be characterized by a parameter α, a stable distribution of party members emerges. At a critical α_c an abrupt depletion of almost all parties is observed and as the consequence all the people are assembled at a single party. The model is based on a hierarchical social network. The probability that a certain person is contacted by another one depends on the social distance introduced within the network and homophily parameter α.

Networks describe various complex natural systems including social systems. We investigate the social network of co-occurrence in Reuters-21578 corpus, which consists of news articles that appeared in the Reuters newswire in 1987. People are represented as vertices and two persons are connected if they co-occur in the same article. The network has small-world features with power-law degree distribution. The network is disconnected and the component size distribution has power-law characteristics. Community detection on a degree-reduced network provides meaningful communities. An edge-reduced network, which contains only the strong ties has a star topology. "Importance" of persons are investigated. The network is the situation in 1987. After 20 years, a better judgment on the importance of the people can be done. A number of ranking algorithms, including Citation count and PageRank, are used to assign ranks to vertices. The ranks given by the algorithms are compared against how well a person is represented in Wikipedia. We find up to medium level Spearman's rank correlations. A noteworthy finding is that PageRank consistently performed worse than the other algorithms. We analyze this further and find reasons.

Small-world networks, exhibiting short nodal distances and high clustering, and scale-free networks, typified by a scale-free, power-law node-degree distribution, have been shown to be widespread both in natural and artificial systems. We propose a new type of network — cluster-dense network — characterized by multiple clusters that are highly intra-connected and sparsely inter-connected. Employing two graph-theoretic measures — local density and relative density — we demonstrate that such networks are prevalent in the world of networks.

Studying attention behavior has its social significance because such behavior is considered to lead the evolution of the friendship network. However, this type of behavior in social networks has attracted relatively little attention before, which is mainly because, in reality, such behaviors are always transitory and rarely recorded. In this paper, we collected the attention behaviors as well as the friendship network from Douban database and then carefully studied the attention behaviors in the friendship network as a latent metric space. The revealed similar patterns of attention behavior and friendship suggest that attention behavior may be the pre-stage of friendship to a certain extent, which can be further validated by the fact that pairwise nodes in Douban network connected by attention links beforehand are indeed far more likely to be connected by friendship links in the near future. This phenomenon can also be used to explain the high clustering of many social networks. More interestingly, it seems that attention behaviors are more likely to take place between individuals who have more mutual friends as well as more different friends, which seems a little different from the principles of many link prediction algorithms. Moreover, it is also found that forward attention is preferred to inverse attention, which is quite natural because, usually, an individual must be more interested in others that he is paying attention to than those paying attention to him. All of these findings can be used to guide the design of more appropriate social network models in the future.

An agent-based model was built representing an economic environment in which m brands are competing for a product market. These agents represent companies that interact within a social network in which a certain agent persuades others to update or shift their brands; the brands of the products they are using. Decision rules were established that caused each agent to react according to the economic benefits it would receive; they updated/shifted only if it was beneficial. Each agent can have only one of the m possible brands, and she can interact with its two nearest neighbors and another set of agents which are chosen according to a particular set of rules in the network topology. An absorbing state was always reached in which a single brand monopolized the network (known as condensation). The condensation time varied as a function of model parameters is studied including an analysis of brand competition using different networks.

In this paper, based on the phenomenon that individuals join into and jump from the organizations in the society, we propose a dynamic community model to construct social networks. Two parameters are adopted in our model, one is the communication rate P_a that denotes the connection strength in the organization and the other is the turnover rate P_b, that stands for the frequency of jumping among the organizations. Based on simulations, we analyze not only the degree distribution, the clustering coefficient, the average distance and the network diameter but also the group distribution which is closely related to their community structure. Moreover, we discover that the networks generated by the proposed model possess the small-world property and can well reproduce the networks of social contacts.

Partly due to the difficulty of the access to a worldwide dataset that simultaneously captures the location history and social networks, our understanding of the relationship between human mobility and the social ties has been limited. However, this topic is essential for a deeper study from human dynamics and social networks aspects. In this paper, we examine the location history data and social networks data of 712 email users and 399 offline events users from a map-editing based social network website. Based on these data, we expand all our experiment both from individual aspect and community aspect. We find that the physical distance is still the most influential factor to social ties among the nine representative human mobility features extracted from our GPS trajectory dataset, although Internet revolution has made long-distance communication dramatically faster, easier and cheaper than ever before, and in turn, partly expand the physical scope of social networks. Furthermore, we find that to a certain extent, the proximity of South–North direction is more influential than East–West direction to social ties. To the our best of our knowledge, this difference between South–North and East–West is the first time to be raised and quantitatively supported by a large dataset. We believe our findings on the interplay of human mobility and social ties offer a new perspective to this field of study.

Opinion formation is a process through which interactions of individuals and dynamism of their opinions in effect of neighbors are modeled. In this paper, in an effort to model the opinion formation more realistically, we have introduced a model that considers the role of network structure in opinion dynamics. In this model, each individual changes his opinion in a way so as to decrease its difference with the opinion of trusted neighbors while he intensifies his dissention with the untrusted ones. Considering trust/distrust relations as a signed network, we have defined a structural indicator which shows the degree of instability in social structure and is calculated based on the structural balance theory. It is also applied as feedback to the opinion formation process affecting its dynamics. Our simulation results show formation of a set of clusters containing individuals holding opinions having similar values. Also, the opinion value of each individual is far from the ones of distrusted neighbors. Since this model considers distrust and instability of relations in society, it can offer a more realistic model of opinion formation.

In this study, the problem of seed selection is investigated. This problem is mainly treated as an optimization problem, which is proved to be NP-hard. There are several heuristic approaches in the literature which mostly use algorithmic heuristics. These approaches mainly focus on the trade-off between computational complexity and accuracy. Although the accuracy of algorithmic heuristics are high, they also have high computational complexity. Furthermore, in the literature, it is generally assumed that complete information on the structure and features of a network is available, which is not the case in most of the times. For the study, a simulation model is constructed, which is capable of creating networks, performing seed selection heuristics, and simulating diffusion models. Novel metric-based seed selection heuristics that rely only on partial information are proposed and tested using the simulation model. These heuristics use local information available from nodes in the synthetically created networks. The performances of heuristics are comparatively analyzed on three different network types. The results clearly show that the performance of a heuristic depends on the structure of a network. A heuristic to be used should be selected after investigating the properties of the network at hand. More importantly, the approach of partial information provided promising results. In certain cases, selection heuristics that rely only on partial network information perform very close to similar heuristics that require complete network data.

Recent generalization of the coevolving voter model [J. Toruniewska, K. Kułakowski, K. Suchecki and J. Hołyst, Phys. Rev. E96, 042306 (2017).] is further generalized here, including spin-dependent probability of rewiring. Mean field results indicate that either the system splits into two separate networks with different spins, or one spin orientation goes extinct. In both cases, the density of active links is equal to zero. The results are discussed in terms of homophily in social contacts.

As an important research field of social network analysis, influence maximization problem is targeted at selecting a small group of influential nodes such that the spread of influence triggered by the seed nodes will be maximum under a given propagation model. It is yet filled with challenging research topics to develop effective and efficient algorithms for the problem especially in large-scale social networks. In this paper, an adaptive discrete particle swarm optimization (ADPSO) is proposed based on network topology for influence maximization in community networks. According to the framework of ADPSO, community structures are detected by label propagation algorithm in the first stage, then dynamic encoding mechanism for particle individuals and discrete evolutionary rules for the swarm are conceived based on network community structure for the meta-heuristic optimization algorithm to identify the allocated number of influential nodes within different communities. To expand the seed nodes reasonably, a local influence preferential strategy is presented to allocate the number of candidate nodes to each community according to its marginal gain. The experimental results on six social networks demonstrate that the proposed ADPSO can achieve comparable influence spread to CELF in an efficient way.

We compared the social character networks of biographical, legendary and fictional texts in search for marks of genre differentiation. We examined the degree distribution of character appearance and found a power-law-like distribution that does not depend on the literary genre. We also analyzed local and global complex network measures, in particular, correlation plots between the recently introduced Lobby index and degree, betweenness and closeness centralities. Assortativity plots, which previous literature claims to separate fictional from real social networks, were also studied. We found no relevant differences among genres for the books studied when applying these network measures and we provide an explanation why the previous assortativity result is not correct.

The influence maximization problem in social networks aims to select a subset of most influential nodes, denoted as seed set, to maximize the influence diffusion of the seed nodes. The majority of existing works on this problem would ignite all the seed nodes simultaneously at the beginning of the diffusion process and let the influence diffuses passively in the network. However, it cannot depict the practical dynamics exactly of viral marketing campaigns in reality and fails to provide driving policies to control over the diffusion. In this paper, we focus on the dynamic influence maximization problem with limited budget to study the scheduling strategies including which influential node is to be seeded during the diffusion process and when to seed it at the right time. A time-dependent seed activating feedback scheme is modeled firstly by considering the time factor and its impact on the influence obligation in diffusion process. Then a scheduling heuristic based on determinate and latent margin is proposed to evaluate the marginal return of candidate nodes and activate the right seed node to promote the viral marketing. Extensive experiments on four social networks show that the proposed algorithm achieves significantly better results than a typical static influence maximization algorithm based on swarm intelligence and can improve the influence propagation under the time-dependent diffusion model comparing with the centrality-based scheduling heuristics.

Nowadays, an increasing number of people use social networks to receive up-to-date information and express their personal opinions, and popular social networks have become important platforms to conduct viral-marketing for many companies. However, due to the existences of negative opinions and hostile relationships, some spreading behaviors will receive much more undesired responses. To study this process of competitive diffusion, we consider heterogeneous opinions (positive and negative ones) and heterogeneous relationships (friendly and hostile ones), and assume the reaction of a user after receiving a message is determined by the received message type, his/her own opinion and the type of relationship between him/her and the neighbor who sends this message. We then modify the duplicate forwarding model to characterize the diffusion dynamics in competitive diffusion, and define the term positive (negative) user influence which is the mean number of positive (negative) messages received by users after a user generates a message. These user influences and the corresponding diffusion threshold can be analyzed theoretically, which are verified by simulations. We then study the impacts of different factors on user influences on some real networks, and observe that messages of some type are easier to be forwarded and received in a given network if the message spreading intensity approaches the diffusion threshold and users of this type have a larger average homophily factor. These findings can help to explain why a large number of boycotts may be attracted if a user or company publishes a post or advertisement in a social network, and we believe this analysis framework will be of use for advertisers to conduct viral-marketing.