Social networks are considered from the point of view of informational influences on network participants (agents). The dynamic processes of forming opinions and the dynamics of information influence on network agents are considered. Models and algorithms for identifying critical points of a social network (influencing agents) are presented, the impact on which allows manipulating the aggregate opinion of network participants that form a social network.
An instrument of active influence on the
actions of network users and a means of forming
and disseminating opinions is undoubtedly a new
type of resource - online social networks. Their
role has grown significantly with the advent of
Web 2.0 [
A social network can be represented as a
graph, the vertices of which are individuals
(agents), and the edges are the various
relationships between them. It is known that the
opinion of an individual in a social network is
largely determined by the opinion of his
influential neighbors [
The decisions of most agents can be based on
the decisions of other agents they observe. This is
especially typical in conditions of a lack of
information or the impossibility for various
reasons to process it and draw appropriate
conclusions. At the same time, the structure of the
network, which determines who trusts whom, can
contribute to the emergence of large information
cascade changes even with insignificant changes
in the decisions of an insignificant part of agents
[
In this paper, the formation and dynamics of opinions in a social network is considered, and an attempt is made to highlight those critical points of the social network (influencing agents), the impact on which allows manipulating the aggregate opinion of the network participants forming the social network, as well as the resulting game-theoretic problems information confrontation.
A social network at a qualitative level is understood as a social structure consisting of a set of agents (subjects - individual or collective, for example, individuals, families, groups, organizations) and a set of relations defined on it (a set of connections between agents, for example, acquaintance, friendship, cooperation, communication). Formally, a social network is a graph G(N, E), in which N = {1, 2, ..., n} is a set of vertices (agents) and E is a set of edges reflecting the interaction of agents.
Social networks contribute, firstly, to the organization of social communications between people and, secondly, to the realization of their basic social needs. There are two intersecting interpretations of the social network - as a social structure and its specific Internet implementation.
When modeling social networks, the mutual
influence of their members (agents), the dynamics
of their opinions, etc. there is a need to take into
account the factors (effects) that take place in real
social networks. In general, in real social
networks, the following effects and properties
can occur, due to both the characteristics and
needs of agents (influencing and being
influenced), the nature of their interaction, and the
properties of the social network itself. Of the
many effects and properties of the social network
presented in [
3. the different significance of the opinions (influence, trust) of some agents for other agents; 4. varying degrees of agents' susceptibility to influence (conformism, stability of opinions); 5. the existence of an indirect influence in the chain of social contacts. Decrease in indirect influence with increasing "distance";
6. the existence of "opinion leaders" (agents with the maximum "influence"), formalization of influence indices;
7. the impact of the structural properties of social networks on the dynamics of opinions; 8. the activity (purposeful behavior) of agents; 9. optimization of information impacts; 10. information management in social networks.
Should be noted the peculiarities of the impact
of the structural properties of social networks on
the opinions dynamics [
Influence is the process and result of an individual (subject of influence) changing the behavior of another subject (individual or collective object of influence), his attitudes, intentions, ideas and assessments (as well as actions based on them) in the course of interaction with it. Influence - the ability to influence someone's ideas or actions. Distinguish between directed and undirected influence. Directed (purposeful) influence - influence that uses persuasion and suggestion as mechanisms of influence on another subject. In this case, the subject of influence sets itself the task of achieving certain results (for example, choosing certain actions) from the object of influence. Nondirected (non-targeted) influence is an influence in which the individual does not set himself the task of achieving certain results from the object of influence.
In a social network, agents often do not have sufficient information for making decisions or cannot independently process it, so their decisions can be based on the decisions they observe or the perceptions of other agents (social influence). Social influence is realized in two processes: communication (in the course of communication, exchange of experience and information, discussion of certain issues with authoritative neighbors for the agent, he comes to certain ideas, attitudes, opinions) and comparison (in search of social identity and social approval, the agent accepts representations and actions expected from him by other agents in a given situation; the agent asks the question “what would the other agent (the standard for comparison) do if he were in my situation?” and, comparing himself with him, determines his adequacy and plays the corresponding role; can be explained by comparison and the search for strategic advantage: by comparing himself with other agents occupying the same positions in the social system, the agent can introduce or accept innovations that will make him more attractive as an object of relations). It should be noted that with a communicative approach to influence, agents may arrive at similar ideas, but not necessarily similar behavior. In comparison, the agent usually copies the behavior indirectly. Obviously, the behavior of an agent is determined not only by perceptions, but also by the constraints it faces. Therefore, agents with similar views can behave differently, and vice versa, agents with different views can behave in the same way.
The social network plays a large role in the dissemination of information, ideas and influence among its members. Influence in the social media literature is closely related to the term diffusion of innovations.
A social network can be viewed as a set of agents - potential voters who “vote” for a particular product, service, or candidate from a particular political party in the elections. In this case, the value (utility) of an agent in a social network depends not only on himself (for example, directly by the expected choice), but also on his influence on other agents. In other words, the configuration and state of the network is important - the totality of the opinions of potential voters regarding their choice. Therefore, there is a need to identify a small number of agents (the problem of maximizing influence) that contribute to the formation of the required opinion throughout the network.
The problem of determining the k most
influential agents in a social network arose in the
context of the so-called viral marketing [
To identify the most valuable (authoritative, influential) agents, the task can be formulated as follows. Let us define the optimal informational influences IA = {IA1, …, IAn} (IAi can be both a Boolean variable: 1 - the presence of informational influence, 0 - its absence for the ith agent; and continuous - the level of influence) for a set of n agents with a predicate Xi = 1 if agent i made the required choice and Xi = 0 otherwise. Suppose that the choice is described by the following set of attributes: Y = {Y1, …, Ym}. Each agent i has a set of neighbors Ni that directly affect Xi, thereby defining a network of agents. In turn, the i-th agent influences its neighbors.
Let the cost c of the implementation of the information influence per one agent be given, the utility rv1 from the adoption of the required decision, if the corresponding information influence was exerted on it, and the utility rv0 from the adoption of the required decision, if the information influence was not carried out. For simplicity, let IA be a Boolean vector.
Let fi1 ( IA) will be the set-result of setting IAi to 1 (all other values are unchanged), similarly defined for fi0 ( IA). Then the expected increase in utility from the information impact for the agent without taking into account its impact on other agents, i.e., the expected utility from the successful implementation of the information impact (intrinsic value of customer) is determined by the formula
ELPi ( X k ,Y , IA) = rv1P ( Xi = 1| X k ,Y , fi1 ( IA)) − , −rv0P( Xi = 1| X k ,Y , fi0 ( IA)) − c where Xk – the set of agents whose decisions are known (about whom it is known that they made the required decisions), P( Xi | X k ,Y , IA) – conditional probability of making the required decision by the i-th agent.
Then the expected increase in utility from the information campaign for the selected agents will be
n ELP ( X k ,Y , IA) = rv1P ( Xi = 1| X k ,Y , IA) − i=1 n − rv0P ( Xi = 1| X k ,Y , IA0 ) − IA c i=1 where IA0 – zero vector; rvi = rv1, if IAi = 1 (else rvi = rv0); |IA| – number of selected agents.
The overall value of an agent on the network (total value of customer = network value of customer + intrinsic value of customer) will be ELP ( X k ,Y , fi1 ( IA)) − ELP ( X k ,Y , fi0 ( IA)) , (i.e., the value of IA will change for other agents and may affect their probability of making a decision). Then the agent's network value (network value of customer) is the difference between his general and personal value (network value of customer = total value of customer - intrinsic value of customer). As can be seen, the value depends on whether the promotions were held for other agents and whether other agents made the required decision.
Let's return to the problem of determining the k most influential nodes in a social network. Obviously, in order to find them in this case, you need to find an IA that maximizes ELP. In the general case, finding the optimal IA requires an enumeration of all its possible combinations. The following approximating procedures are possible, giving an approximate solution:
1) A single bypass. For the i-th agent there is a special offer
IAi = 1, if ELP ( X k ,Y , fi1 ( IA0 )) 0 ; 2) Greedy algorithm. Set IA = IA0. It is necessary to bypass IAi in the loop, setting the value to one, if
ELP( X k ,Y , fi1 ( IA)) ELP( X k ,Y , IA) ;
Hill-climbing search. Set IA = IA0, IAi1 = 1, where
i1 = arg maxi ( ELP( X k ,Y , fi1 ( IA))) .
Repeat as long as the i-th agent exists, setting for which IAi = 1 leads to an increase in ELP.
In [
The problem of maximizing influence can be formulated as follows. The influence (A) of the set of agents A is defined as the expected number of active agents upon completion of the process of propagation of information actions initiated by agents from the set A. For both models (linear threshold and independent cascades), an NP-hard problem arises: for a given parameter k, find kelements set A maximizing (A). Since the problem of maximizing the influence is similar to the problem of maximizing submodular functions, then for the appropriate application of the algorithm it is only necessary to prove that (A) is a submodular function. The submodular function f maps a finite set U to non-negative real numbers and satisfies the natural property of "diminishing returns" (the marginal revenue from adding an element to a set S is at least as high as the marginal revenue from adding the same element to any set including S).
Generalized Threshold Model. An agent's decision to activate is determined by a monotonic threshold function fv : S Nv → 0,1 , where Nv is the set of neighbors v and fv() = 0. Each agent initially chooses a threshold v uniformly randomly and becomes active if fv(S) 0.
Generalized cascade model. The probability pv(u, S) that agent u activates agent v depends on the set S of agents that have already unsuccessfully tried to activate agent v. A restriction is imposed on the model: if neighbors u1, ..., ul try to activate v, then the probability that v will become active after l attempts does not depend on the order of activation attempts.
Generalized information impact strategies. Let there be m different ways of informational influence I1, …, Im, each of which can affect a certain subset of agents of the social network, increasing their probability of activation. That is, the initial set of active agents A0 is not defined. The amount of investments xi in each marketing action is selected, which is limited in aggregate by the budget. Marketing strategy - vector x = {x1, ..., xm}. The probability hv(x) of agent v becoming active is determined by strategy x. The function hv() is non-decreasing and has the property of “diminishing incomes”, that is x y a 0 hv ( x + a) − hv ( x) hv ( y + a) − hv ( y )
The resulting expected number of active agents in this case (taking into account direct marketing and subsequent influence) is equal to EG ( x) = ( A)hu ( x) 1 − hv ( x)
AV uA vA
In order to approximately maximize this functional, it is assumed that can be estimated EG(x) at each point x and can be found the direction i with an approximately maximum gradient. Let ei be the unit vector of the i-axis and δ a constant. It is assumed that there exists 1 such that can be found i for which EG(x + δei) – EG(x) (EG(x + δei) – EG(x)) for any j. Then, dividing the budget k into parts of size δ, at each step (all of these parts k/), we can invest δ funds from the budget into Ii, which maximizes the gradient EG().
Competing information influences. In [
Two models extended in relation to the model of independent cascades are proposed:
1) A model based on distance (distancebased), in which the agent receives the corresponding innovation from the "closest" activated agent from I.
2) The wave model. The innovation is spreading step by step. An agent that is not active at the previous step is activated at the current step by uniformly randomly choosing one of the neighbors located at a distance proportional to the number of the step.
For these conditions, it is promising to calculate the Nash equilibrium and consider the Stackelberg game.
Voting model. In [
The social network is represented by an undirected graph with loops G(N, E). Each node v has many neighbors N(v) and is randomly initialized (assigned a value of 1 or 0). At each moment in time, each node randomly chooses one of its neighbors (the probability of choosing each neighbor is the same) and accepts his opinion: u N (v) : ft (u ) = 1 1, with probability N (v) fi+1 (v) = u N (v) : ft (u ) = 0 0, with probability N (v)
The budget is bounded from above by a constant B, the cost of the initial “persuasion” f0(v)=1 of agent v is cv. Thus, the problem of maximizing influence is formulated as follows: f0: N → 0; 1} maximizing the mathematical expectation E[∑vN ft(v)] for a given budget constraint v| f 0(v)=1 cv B .
The paper considers the dynamic processes of forming opinions in a social network, and also presents models and algorithms for identifying critical points of a social network (influencing agents), the impact on which allows manipulating the aggregate opinion of network participants forming a social network, as well as the resulting game-theoretic problems information confrontation.