# Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks
## 1 Introduction
### Influence and Information-Spreading Mechanisms  
In general, a research approach based on networks and their modelling offers theoretical means to study social phenomena due to the fact that different kinds of relationships and influence between social actors can be represented [1; 2; 3; 4; 5]. A good example is diffusion in a network, which can be viewed as the process of information, influence, or disease spreading from one actor to another [6; 7]. While each of the aforementioned processesdescribes a different phenomenon of human behaviour, they share common features in their transmission mechanisms. They all are manifestations of interactions and consequences of contacts between individuals in social networks. The transmission of information and the spread of social influence are two processes that usually do not exist in their pure form. In the case of a disease that spreads through contacts between individuals, the probability of the disease spreading correlates with the strength and frequency of social interactions between people. Social media and interactive digital channels allow us to create and share information, ideas, interests, and other forms of expression through virtual communities and networks. It is common for models that one piece of information may only be mediated once between two individuals, but in practice, information is not presented in a normalised form like structural data in a database [8]. Unstructured data is presented in text or multimedia formats of different sizes and dimensions. Even if we could normalise some of the data items, a great deal of the information is unstructured, descriptive, or uncertain. It may even include misinformation or fake news. We thus propose that recurrent and repeated mechanisms describe the spreading processes in both structured and unstructured information transmission. [PERSON] [9] has studied the diffusion of innovations and communication processes, where communication is described as a process in which participants create and share information. It is a two-way process in which an individual seeks to transfer a message to another in order to achieve wanted effects. Communication is a convergent process as when two or more individuals exchange information, they will eventually reach a stable state of mutual understanding. In human communication processes, information is exchanged between a pair of individuals and the spread of information may continue through several cycles. [PERSON] [9] defines diffusion as communication in which messages are new ideas or innovations. Communication processes, as defined in [9], and influence spreading processes, studied in our work [6; 7], are two closely related concepts. Influence spreading entails various methods of interactions that can change people's opinions [10], behaviour [11], and beliefs [12] and it can be characterised as a continuous psychological process rather than a chain of nonrecurring information transmission events. People gather together and influence each other in different situations and environments, for example, in families, workplaces, and hobbies. Many diseases, such as viruses, spread through physical contacts, the air, or other transmitting media. It is clear that social interactions are correlated with epidemic-spreading mechanisms. If the only transmission channel of disease is through physical contact, the spreading process can be considered to be similar to the information-transfer mechanism. Traditionally, models of social and biological contagion have been classified into two categories: simple and complex contagion. Simple contagion describes spreading processes induced by a single exposure, while complex contagion requires multiple sources of exposure before an individual adopts a change of behaviour [11; 12; 13]. Recently, the need for generalised contagion models has been discussed and a unifying model has been presented [14]. Furthermore, models of opinion dynamics in social networks have been classified into models with discrete or continuous opinions [10].