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

Online social networks (OSNs) have become a powerful medium of communicating, sharing and disseminating information. Because of popularity and availability of OSNs throughout the world, the connected users can spread information faster and thus propagate influence over each other constantly. Due to such impact, a lot of applications on OSNs focused on picking an initial set of users (seeds) to infuse their message in the OSN. Due to huge size of the network, the main challenge in picking the initial set is to maximize the resultant influence over the users in the network. The optimization problem of finding out the most influential set of members in an OSN for maximization of influence is an NP-hard problem. In this paper, we propose using the Positive Influential Dominating Set (PIDS) algorithm for the initial seed. PIDS is a well-known algorithm which determines the influential backbone nodes in the networks. We implemented PIDS-based influence maximization by using different propagation models. We compared PIDS performance to that of the existing approaches based on greedy and random heuristics. The experimental results from extensive simulation on real-world network data sets show that PIDS gives better influence spread than greedy and random for both Independent Cascade Model and Linear Threshold Model of influence propagation. PIDS is also scalable to large networks and in all size ranges, it performs well in influence maximization.

With online social networks such as Facebook and Twitter becoming globally popular, there is renewed interest in understanding the structural and dynamical properties of social networks. In this thesis we study several stochastic models arising in the context of the spread of influence or information in social networks. Our objective is to provide compact and accurate quantitative descriptions of the spread processes, to understand the effects of various system parameters, and to design policies for the control of such diffusions. One of the well established models for influence spread in social networks is the threshold model. An individual’s threshold indicates the minimum level of “influence” that must be exerted, by other members of the population engaged in some activity, before the individual will join the activity. We begin with the well-known Linear Threshold (LT) model introduced by Kempe et al. [1]. We analytically characterize the expected influence for a given initial set under the LT model, and provide an equivalent interpretation in terms of acyclic path probabilities in a Markov chain. We derive explicit optimal initial sets for some simple networks and also study the effectiveness of the Pagerank [2] algorithm for the problem of influence maximization. Using insights from our analytical characterization, we then propose a computationally efficient G1-sieving algorithm for influence maximization and show that it performs on par with the greedy algorithm, through experiments on a coauthorship dataset. The Markov chain characterisation gives only limited insights into the dynamics of influence spread and the effects of the various parameters. We next provide such insights in a restricted setting, namely that of a homogeneous version of the LT model but with a general threshold distribution, by taking the fluid limit of a probabilistically scaled version of the spread Markov process. We observe that the threshold distribution features in the fluid limit via its hazard function. We study the effect of various threshold distributions and show that the influence evolution can exhibit qualitatively different behaviors, depending on the threshold distribution, even in a homogeneous setting. We show that under the exponential threshold distribution, the LT model becomes equivalent to the SIR (Susceptible-Infected-Recovered) epidemic model [3]. We also show how our approach is easily amenable to networks with heterogeneous community structures. Hundreds of millions of people today interact with social networks via their mobile devices. If the peer-to-peer radios on such devices are used, then influence spread and information spread can take place opportunistically when pairs of such devices come in proximity. In this context, we develop a framework for content delivery in mobile opportunistic networks with joint evolution of content popularity and availability. We model the evolution of influence and content spread using a multi-layer controlled epidemic model, and, using the monotonicity properties of the o.d.e.s, prove that a time-threshold policy for copying to relay nodes is delay-cost optimal. Information spread occurs seldom in isolation on online social networks. Several contents might spread simultaneously, competing for the common resource of user attention. Hence, we turn our attention to the study of competition between content creators for a common population, across multiple social networks, as a non-cooperative game. We characterize the best response function, and observe that it has a threshold structure. We obtain the Nash equilibria and study the effect of cost parameters on the equilibrium budget allocation by the content creators. Another key aspect to capturing competition between contents, is to understand how a single end-user receives and processes content. Most social networks’ interface involves a timeline, a reverse chronological list of contents displayed to the user, similar to an email inbox. We study competition between content creators for visibility on a social network user’s timeline. We study a non-cooperative game among content creators over timelines of fixed size, show that the equilibrium rate of operation under a symmetric setting, exhibits a non-monotonic behavior with increasing number of players. We then consider timelines of infinite size, along with a behavioral model for user’s scanning behavior, while also accounting for variability in quality (influence weight) among content creators. We obtain integral equations, that capture the evolution of average influence of competing contents on a social network user’s timeline, and study various content competition formulations involving quality and quantity.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-20T19:33:13Z No. of bitstreams: 1 CRISTOVÃO MÁCIO DE OLIVEIRA LIMA FILHO - DISSERTAÇÃO PPGEE 2010..pdf: 2095765 bytes, checksum: 1c2232fd0f1557df7308e04bad6426c2 (MD5) / Made available in DSpace on 2018-08-20T19:33:13Z (GMT). No. of bitstreams: 1 CRISTOVÃO MÁCIO DE OLIVEIRA LIMA FILHO - DISSERTAÇÃO PPGEE 2010..pdf: 2095765 bytes, checksum: 1c2232fd0f1557df7308e04bad6426c2 (MD5) Previous issue date: 2010-06-09 / Esta dissertação descreve o desenvolvimento de um leiaute de uma nova arquitetura de multiplicador em corpos finitos baseada no multiplicador de Mastrovito. Tal arquitetura tem como unidades de processamento as portas de limiar linear, que é o elemento básico de uma rede neural discreta. As redes neurais discretas implementadas com portas de limiar linear permitem reduzir a complexidade de certos circuitos antes implementados com lógica tradicional (Portas AND, OR e NOT). Com isso, a idéia de estender o uso de portas de limiar linear em operações aritméticas em corpos finitos se torna bastante atraente. Assim, para comprovar de forma prática, a eficiência das portas de limiar linear, a arquitetura de um multiplicador em GF(24), proposta em (LIDIANO - 2000), foi implementada utilizando as ferramentas de desenho de leiaute de circuito integrado da Mentor Graphics®. Os resultados da simulação do leiaute do circuito integrado do multiplicador em GF(24) são apresentados. Os mesmos indicaram um desempenho abaixo do esperado, devido a complexidade espacial do multiplicador em GF(2n) com 4=n não ser suficiente para que as vantagens da implementação com portas de limiar linear sejam visualizada. / This dissertation describes the development of a layout of new multiplication architecture in Galois field based on the Mastrovito multiplier. The processing unit of this new architecture is a threshold logic gate, which is a basic element of a discrete neural network. The discrete neural network built with threshold logic gates allow reduce de complexity of a certain circuits once built using traditional boolean gates (AND, OR and NOT). Therewith, the idea of extending the advantages of the threshold logic gates for arithmetic operations in Galois field to become very attractive. Thus, to confirm into practice form, the advantages of the threshold logic gates, a multiplier architecture in GF(24), proposed in (LIDIANO - 2000), was implemented using the integrated circuit layout tools of Mentor Graphics®. The results from simulations of the layout of multiplier in GF(24) are presented. These results indicated a low performance, due to the space complexity of GF(2n) multiplier with n = 4 is not enough for show the advantages of the multiplier implementation with threshold logic gates.

Dans cette thèse nous étudierons des problématiques de graphes. Nous proposons deux études théoriques sur la recherche et l'énumération de cliques et quasi-cliques. Ensuite nous proposons une étude appliquée sur la propagation d'information dans un graphe d'entités nommées. Premièrement, nous étudierons la recherche de cliques dans des graphes compressés. Les problèmes MCE et MCP sont des problèmes rencontrés dans l'analyse des graphes. Ce sont des problèmes difficiles, pour lesquels des solutions adaptées doivent être conçues pour les grands graphes. Nous proposons de travailler sur une version compressée du graphe. Nous montrons les bons résultats obtenus par notre méthode pour l'énumération de cliques maximales. Secondement, nous étudierons l'énumération de quasi-cliques maximales. Nous proposons un algorithme distribué qui énumère l'ensemble des quasi-cliques maximales. Nous proposons aussi une heuristique qui liste des quasi-cliques plus rapidement. Nous montrons l'intérêt de l'énumération de ces quasi-cliques par une évaluation des relations en regardant la co-occurrence des noeuds dans l'ensemble des quasi-cliques énumérées. Troisièmement, nous travaillerons sur la diffusion d'événements dans un graphe d'entités nommées. De nombreux modèles existent pour simuler des problèmes de diffusion de rumeurs ou de maladies dans des réseaux sociaux ou des problèmes de propagation de faillites dans les milieux bancaires. Nous proposons de répondre au problème de diffusion d'événements dans des réseaux hétérogènes représentant un environnement économique du monde. Nous proposons un problème de diffusion, nommé problème de classification de l'infection, qui consiste à déterminer quelles entités sont concernées par un événement. Pour ce problème, nous proposons deux modèles inspirés du modèle de seuil linéaire auxquels nous ajoutons différentes fonctionnalités. Finalement, nous testons et validons nos modèles sur un ensemble d'événements / In this thesis we will study graph problems. We will study theoretical problems in pattern research and applied problems in information diffusion. We propose two theoretical studies on the identification/detection and enumeration of dense subgraphs, such as cliques and quasi-cliques. Then we propose an applied study on the propagation of information in a named entities graph. First, we will study the identification/detection of cliques in compressed graphs. The MCE and MCP are problems that are encountered in the analysis of data graphs. These problem are difficult to solve (NP-Hard for MCE and NP-Complete for MCP), and adapted solutions must be found for large graphs. We propose to solve these problems by working on a compressed version of the initial graph. We show the correct results obtained by our method for the enumeration of maximal cliques on compressed graphs. Secondly, we will study the enumeration of maximal quasi-cliques. We propose a distributed algorithm that enumerates the set of maximal quasi-cliques of the graph. We show that this algorithm lists the set of maximal quasi-cliques of the graph. We also propose a heuristic that lists a set of quasi-cliques more quickly. We show the interest of enumerating these quasi-cliques by an evaluation of relations by looking at the co-occurrence of nodes in the set of enumerated quasi-cliques. Finally, we work on the event diffusion in a named entities graph. Many models exist to simulate diffusion problems of rumors or diseases in social networks and bankruptcies in banking networks. We address the issue of significant events diffusion in heterogeneous networks, representing a global economic environment. We propose a diffusion problem, called infection classification problem, which consists to dertemine which entities are concerned by an event. To solve this problem we propose two models inspired by the linear threshold model to which we add different features. Finally, we test and validate our models on a set of events