Graph decompositions have useful applications in optimization problems that are categorized as NP-Hard. Modular Decomposition of a graph is a technique to decompose the graph into non-overlapping modules. A module M of an undirected graph G = (V, E) is commonly defined as a set of vertices such that any vertex outside of M is either adjacent or non-adjacent to all vertices in M . By the theory of modular decomposition, the modules can be categorized as parallel, series or prime modules. Series modules which are maximal and are also cliques are termed as simple series modules or critical cliques. There are modular decomposition algorithms that can be used to decompose the graph into modules and obtain critical cliques. In this current research, we present a new algorithm to decompose the graph into critical cliques without applying the process of modular decomposition. Given a simple, undirected graph G = (V, E), the runtime complexity of our proposed algorithm is O(|V| + |E|) under certain input constraints. Thus, one of our main contributions is to propose a novel algorithm for decomposing a simple, undirected graph directly into critical cliques. We apply the idea of critical cliques to propose a new way for solving the influence maximization problem in online social networks. Influence maximization in online social networks is the problem of identifying a small, initial set of influential individuals which can influence the maximum number of individuals in the network. In this research, we propose a new model of online social networks based on the notion of critical cliques. We utilize the properties of critical cliques to assign parameters for our proposed model and select an initial set of activation nodes. We then simulate the influence propagation process in the online social network using our proposed model and experimentally compare our approach to the greedy algorithm proposed by Kempe, Kleinberg and Tardos. Our main contribution in the influence maximization research is to propose a new model of online social network taking into account the structural properties of the social network graph and a new, faster algorithm for determining the initial set of influential individuals in the online social network.

In recent years, social networks have become an important part of our daily lives. Billions of people daily use Facebook and other prominent social media networks. This makes them an effective medium for advertising and marketing. Finding the most influential users in a social network is an interesting problem in this domain, as promoters can reach large audiences by targeting these few influential users. This is the influence maximization problem, where we want to maximize the influence spread using as few users as possible. As these social networks are huge, scalability and runtime of the algorithm to find the most influential users is of high importance. We propose innovative improvements in the implementation of the state-of-the-art sketching algorithm for influence analysis on social networks. The primary goal of this thesis is to make the algorithm fast, efficient, and scalable. We devise new data structures to improve the speed of the sketching algorithm. We introduce the compressed version of the algorithm which reduces the space taken in the memory by the data structures without compromising the runtime. By performing extensive experiments on real-world graphs, we prove that our algorithms are able to compute the most influential users within a reasonable amount of time and space on a consumer grade machine. These modifications can further be enhanced to reflect the constantly updating social media graphs to provide accurate estimations in real-time. / Graduate

This thesis studies social influence from the perspective of users' characteristics. The importance of users' characteristics in word-of-mouth applications has been emphasized in economics and marketing fields. We model a category of users called mavens where their unique characteristics nominate them to be the preferable seeds in viral marketing applications. In addition, we develop some methods to learn their characteristics based on a real dataset. We also illustrate the ways to maximize information flow through mavens in social networks. Our experiments show that our model can successfully detect mavens as well as fulfill significant roles in maximizing the information flow in a social network where mavens considerably outperform general influential users for influence maximization. The results verify the compatibility of our model with real marketing applications.

The problem of influence maximization has been studied extensively with applications that include viral marketing, recommendations, and feed ranking. The optimization problem, first formulated by Kempe, Kleinberg and Tardos, is known to be NP-hard. Thus, several heuristics have been proposed to solve this problem. This thesis studies the problem of influence maximization under the deterministic linear threshold model and presents a novel heuristic for finding influential nodes in a graph with the goal of maximizing contagion spread that emanates from these influential nodes. Inputs to our algorithm include edge weights and vertex thresholds. The threshold difference greedy algorithm presented in this thesis takes into account both the edge weights as well as vertex thresholds in computing influence of a node. The threshold difference greedy algorithm is evaluated on 14 real-world networks. Results demonstrate that the new algorithm performs consistently better than the seven other heuristics that we evaluated in terms of final spread size. The threshold difference greedy algorithm has tuneable parameters which can make the algorithm run faster. As a part of the approach, the algorithm also computes the infected nodes in the graph. This eliminates the need for running simulations to determine the spread size from the influential nodes. We also study the target set selection problem with our algorithm. In this problem, the final spread size is specified and a seed (or influential) set is computed that will generate the required spread size. / Master of Science

Graphs are commonly selected as a model of scientific information: graphs can successfully represent imprecise, uncertain, noisy data; and graph theory has a well-developed mathematical apparatus forming a solid and sound foundation for graph research. Design and experimental confirmation of new, scalable, and practical analytics for massive graphs have been actively researched for decades. Our work concentrates on developing new accurate and efficient algorithms that calculate the most influential nodes and communities in an arbitrary graph. Our algorithms for graph decomposition into families of most influential communities compute influential communities faster and using smaller memory footprint than existing algorithms for the problem. Our algorithms solving the problem of influence maximization in large graphs use much smaller memory than the existing state-of-the-art algorithms while providing solutions with equal accuracy. Our main contribution is designing data structures and algorithms that drastically cut the memory footprint and scale up the computation of influential communities and nodes to massive modern graphs. The algorithms and their implementations can efficiently handle networks of billions of edges using a single consumer-grade machine. These claims are supported by extensive experiments on large real-world graphs of different types. / Graduate

<p>With an increasing number of users spending time on social media platforms and engaging with family, friends, and influencers within communities of interest (such as in fashion, cooking, gaming, etc.), there are significant opportunities for marketing firms to leverage word-of-mouth advertising on these platforms. In particular, marketing firms can select sets of influencers within relevant communities to sponsor, namely by providing free product samples to those influencers so that so they will discuss and promote the product on their social media accounts.</p><p>The question of which set of influencers to sponsor is known as <b>influence maximization</b> (IM) formally defined as follows: "if we can try to convince a subset of individuals in a social network to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target?'' Under standard diffusion models, this optimization problem is known to be NP-hard. This problem has been widely studied in the literature and several approaches for solving it have been proposed. Some approaches provide near-optimal solutions but are costly in terms of runtime. On the other hand, some approaches are faster but heuristics, i.e., do not have approximation guarantees.</p><p>In this dissertation, we study the influence maximization problem extensively. We provide efficient algorithms for solving the original problem and its important generalizations. Furthermore, we provide theoretical guarantees and experimental evaluations to support the claims made in this dissertation.</p><p>We first study the original IM problem referred to as the discrete influence maximization (DIM) problem where the marketer can either provide a free sample to an influencer or not, i.e., they cannot give fractional discounts like 10% off, etc. As already mentioned the existing solution methods (for instance, the simulation-based greedy algorithm) provide near-optimal solutions that are costly in terms of runtime and the approaches that are faster do not have approximation guarantees. Motivated by the idea of addressing this trade-off between accuracy and runtime, we propose a community-aware divide-and-conquer framework to provide a time-efficient solution to the DIM problem. The proposed framework outperforms the standard methods in terms of runtime and the heuristic methods in terms of influence.</p><p>We next study a natural extension of the DIM problem referred to as the fractional influence maximization (FIM) problem where the marketer may offer fractional discounts (as opposed to either providing a free sample to an influencer or not in the DIM problem) to the influencers. Clearly, the FIM problem provides more flexibility to the marketer in allocating the available budget among different influencers. The existing solution methods propose to use a continuous extension of the simulation-based greedy approximation algorithm for solving the DIM problem. This continuous extension suggests greedily building the solution for the given fractional budget by taking small steps through the interior of the feasible region. On the contrary, we first characterize the solution to the FIM problem in terms of the solution to the DIM problem. We then use this characterization to propose an efficient greedy approximation algorithm that only iterates through the corners of the feasible region. This leads to huge savings in terms of runtime compared to the existing methods that suggest iterating through the interior of the feasible region. Furthermore, we provide an approximation guarantee for the proposed greedy algorithm to solve the FIM problem.</p><p>Finally, we study another extension of the DIM problem referred to as the online discrete influence maximization (ODIM) problem, where the marketer provides free samples not just once but repeatedly over a given time horizon and the goal is to maximize the cumulative influence over time while receiving instantaneous feedback. The existing solution methods are based on semi-bandit instantaneous feedback where the knowledge of some intermediate aspects of how the influence propagates in the social network is assumed or observed. For instance, which specific individuals became influenced at the intermediate steps during the propagation? However, for social networks with user privacy, this information is not available. Hence, we consider the ODIM problem with full-bandit feedback where no knowledge of the underlying social network or diffusion process is assumed. We note that the ODIM problem is an instance of the stochastic combinatorial multi-armed bandit (CMAB) problem with submodular rewards. To solve the ODIM problem, we provide an efficient algorithm that outperforms the existing methods in terms of influence, and time and space complexities.</p><p>Furthermore, we point out the connections of influence maximization with a related problem of disease outbreak prevention and a more general problem of submodular maximization. The methods proposed in this dissertation can also be used to solve those problems.</p>

Analysis of large network datasets has become increasingly important. Algorithms have been designed to find many kinds of structure, with numerous applications across the social and biological sciences. However, a tradeoff is always present between accuracy and scalability; otherwise promising techniques can be computationally infeasible when applied to networks with huge numbers of nodes and edges. One way of extending the reach of network analysis is to sparsify the graph by retaining only a subset of its edges. The reduced network could prove much more tractable. For this thesis, I propose a new sparsification algorithm that preserves the properties of a random walk on the network. Specifically, the algorithm finds a subset of edges that best preserves the stationary distribution of a random walk by minimizing the Kullback-Leibler divergence between a walk on the original and sparsified graphs. A highly efficient greedy search strategy is developed to optimize this objective. Experimental results are presented that test the performance of the algorithm on the influence maximization task. These results demonstrate that sparsification allows near-optimal solutions to be found in a small fraction of the runtime that would required using the full network. Two cases are shown where sparsification allows an influence maximization algorithm to be applied to a dataset that previous work had considered intractable.

病毒式行銷(viral marketing)透過人際之間的互動，藉由消費者對消費者的推薦，達到廣告效益。而廣告商要如何進行病毒式行銷？廣告商必須在有限資源下從人群中找出具有影響力的人，將產品或是概念推薦給更多的消費者，以說服消費者會採納他們的意見。 利用社會網絡(Social network)，我們可以簡單地將消費者之間的關係用節點跟邊呈現，而Influence Maximization就是在社會網絡上選擇最具有影響力的k個消費者，而這k個消費者能影響最多的消費者。 然而，廣告相當重視目標消費群，廣告目的就是希望能夠影響目標消費群，使目標消費群購買產品。因此，我們針對標籤社會網絡(Labeled social network)提出Labeled influence maximization的問題，不同過往的研究，我們加入了標籤的條件，希望在標籤社會網絡中影響到最多符合標籤條件的節點。 針對標籤社會網絡，我們除了修改四個解決Influence maximization problem的方法，Greedy、NewGreedy、CELFGreedy和DegreeDiscount，以找出影響最多符合類別條件的節點的趨近解。我們也提出了兩個新的方法ProximityDiscount和MaximumCoverage來解決Labeled influence maximization problem。我們在Offline時，先計算節點與節點之間的Proximity，當行銷人員Online擬定行效策略時，系統利用Proximity，Onlin找出趨近解。 實驗所採用的資料是Internet Movie Database的社會網絡。根據實驗結果顯示，在兼顧效率與效果的情況下，適合用ProximityDiscount來解決Labeled influence maximization problem。 / Influence maximization problem is to find a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. But when marketers advertise for some products, they have a set of target audience. However, influence maximization doesn’t take target audience into account. This thesis addresses a new problem called labeled influence maximization problem, which is to find a subset of nodes in a labeled social network that could influence target audience and maximizes the profit of influence. In labeled social network, every node has a label, and every label has profit which can be set by marketers. We propose six algorithms to solve labeled influence maximization problem. To accommodate the objective of labeled influence maximization, four algorithms, called LabeledGreedy, LabeledNewGreedy, LabeledCELFGreedy, and LabeledDegreeDiscount, are modified from previous studies on original influence maximization. Moreover, we propose two new algorithms, called ProximityDiscount and MaximumCoverage, which offline compute the proximities of any two nodes in the labeled social network. When marketers make strategies online, the system will return the approximate solution by using proximities. Experiments were performed on the labeled social network constructed from Internet Movie Database, the result shows that ProximityDiscount may provide good efficiency and effectiveness.

Data dissemination problem is a challenging issue in social networks, especially in mobile social networks, which grows rapidly in recent years worldwide with a significant increasing number of hand-on mobile devices such as smart phones and pads. Short-range radio communications equipped in mobile devices enable mobile users to access their interested contents not only from access points of Internet but also from other mobile users. Through proper data dissemination among mobile users, the bandwidth of the short-range communications can be better utilized and alleviate the stress on the bandwidth of the cellular networks. In this dissertation proposal, data dissemination problem in mobile social networks is studied. Before data dissemination emerges in the research of mobile social networks, routing protocol of finding efficient routing path in mobile social networks was the focus, which later became the pavement for the study of the efficient data dissemination. Data dissemination priorities on packet dissemination from multiple sources to multiple destinations while routing protocol simply focus on finding routing path between two ends in the networks. The first works in the literature of data dissemination problem were based on the modification and improvement of routing protocols in mobile social networks. Therefore, we first studied and proposed a prediction-based routing protocol in delay tolerant networks. Delay tolerant network appears earlier than mobile social networks. With respect to delay tolerant networks, mobile social networks also consider social patterns as well as mobility patterns. In our work, we simply come up with the prediction-based routing protocol through analysis of user mobility patterns. We can also apply our proposed protocol in mobile social networks. Secondly, in literature, efficient data dissemination schemes are proposed to improve the data dissemination ratio and with reasonable overhead in the networks. However, the overhead may be not well controlled in the existing works. A social-aware data dissemination scheme is proposed in this dissertation proposal to study efficient data dissemination problem with controlled overhead in mobile social networks. The data dissemination scheme is based on the study on both mobility patterns and social patterns of mobile social networks. Thirdly, in real world cases, an efficient data dissemination in mobile social networks can never be realized if mobile users are selfish, which is true unfortunately in fact. Therefore, how to strengthen nodal cooperation for data dissemination is studied and a credit-based incentive data dissemination protocol is also proposed in this dissertation. Data dissemination problem was primarily researched on mobile social networks. When consider large social networks like online social networks, another similar problem was researched, namely, information diffusion problem. One specific problem is influence maximization problem in online social networks, which maximize the result of information diffusion process. In this dissertation proposal, we proposed a new information diffusion model, namely, sustaining cascading (SC) model to study the influence maximization problem and based on the SC model, we further plan our research work on the information diffusion problem aiming at minimizing the influence diffusion time with subject to an estimated influence coverage.

The importance of modelling the spreading of infectious diseases as part of a public health strategy has been highlighted by the ongoing coronavirus pandemic. This includes identifying the geographical areas or travel routes most likely to contribute to the spreading of an outbreak. These areas and routes can then be monitored as part of an early warning system, be part of intervention strategies, e.g. lockdowns, aiming to mitigate the spreading of the disease or be a focus of vaccination campaigns.  This thesis focus on developing a network-based infection model between the municipalities of Sweden in order to identify the areas most likely to contribute to an epidemic. First, a human mobility model is constructed based on the well-known radiation model. Then a network-based SEIR compartmental model is employed to simulate epidemic outbreaks with various parameters. Finally, the adoption of the influence maximization problem known in network science to identify the municipalities having the largest impact on the spreading of infectious diseases.  The resulting super-spreading municipalities point towards confirmation of the known fact that central highly populated regions in highly populated areas carry a greater risk than their neighbours initially. However, once these areas are targeted, the other resulting nodes show a greater variety in geographical location than expected. Furthermore, a correlation can be seen between increased infections time and greater variety, although more empirical data is required to support this claim.   For further evaluation of the model, the mobility network was studied due to its central role in creating data for the model parameters. Commuting data in the Gothenburg region were compared to the estimations, showing an overall good accuracy with major deviations in few cases.