An online social network can be defined as a set of socially relevant individuals with some patterns of interactions or contacts among them, which are connected by one or more online relations [1][2]. Online social networks provide platforms for users to share information or statuses and to communicate with their families and friends online. These complex, emergent, dynamic and heterogeneous networks have been developed on an unprecedented scale. With the prosperous development of online social networks, many marketers have exploited the opportunities and attempt to select influential users within online social media to influence other users through online ?word-of-mouth? effect or viral marketing approaches, which are now replacing traditional marketing strategies [3]. Such ?word-of-mouth? effect and viral marketing approaches can enhance brand awareness and achieve the marketing objectives of companies withlimited resources. In this situation, the propagation of influence to online users with limited resources over the largest possible range, known as influence maximisation, is an important problem. The solution of influence maximisation is known to be NP-hard. Hence, approximation approaches are better replacements with guarantee [4][5][6]. This thesis explores appropriate approaches for solving the influence maximisation problem effectively and efficiently. Based on the existing problems of influence maximisation in online social networks, influence maximisation is developed through two different approaches; centralised and decentralised. In centralised approaches, all tasks are completed by a single central component. By contrast, decentralised approaches share the workload by distributing the computational tasks to individuals. Classic influence diffusion models with static and predefined probabilities are too ideal, as they consider only the physical link connections [3][5], whereas online social networks contain additional subjective factors, such as, user preference. User preference plays an important role in influence maximisation, but is not considered in most of the existing influence maximisation models. To alleviate these problems, we proposed a Preference-based Trust Independent Cascade Model, which is founded on a classic centralised approach. This develops influence maximisation in terms of both user preference and trust connection (physical link connection). Based on these two factors, the Preference-based Trust Independent Cascade Model computes the influence propagation probabilities. In this way, hub users in an online social network, who are interested in the promoted items, can be selected as influential users. In experimental results, the Preference-based Trust Independent Cascade Model demonstrated better performance than other existing approaches. Furthermore, by reviewing the previous researches and implementing experiments, we discover that centralised approaches are generally inefficient because they limit the stability and scalability of large-scale, dynamic online social networks. To overcome this problem, we propose a novel decentralised approach called Stigmergy-based Influence Maximisation Model, which simulates the influence propagation process by ants crawling across the network topology. The model mimics the key behaviours of ants, i.e., path selection and pheromone allocation. The former identifies the next node to reach when an ant faces multiple options; the latter deposits pheromone on the specific nodes based on the heuristics when an ant explores a possible influence-diffusion path. The superior performance and operating time of the Stigmergy-based Influence Maximisation Model was confirmed in comparison experiments against existing approaches.
展开▼
