Mathematical Programming Models for Influence Maximization on Social Networks

In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.

Team performance according to ball possession characteristics : a social networks approach

Over the last few years, football entered in a period of accelerated access to large amount of match analysis data. Social networks have been adopted to reveal the structure and organization of the web of interactions, such as the players passing distribution tendencies. In this study we investigated the influence of ball possession characteristics in the competitive success of Spanish La Liga teams. The sample was composed by OPTA passing distribution raw data (n=269,055 passes) obtained from 380 matches involving all the 20 teams of the 2012/2013 season. Then, we generated 760 adjacency matrixes and their corresponding social networks using Node XL software. For each network we calculated three team performance measures to evaluate ball possession tendencies: graph density, average clustering and passing intensity. Three levels of competitive success were determined using two-step cluster analysis based on two input variables: the total points scored by each team and the scored per conceded goals ratio. Our analyses revealed significant differences between competitive performances on all the three team performance measures (p < .001). Bottom-ranked teams had less number of connected players (graph density) and triangulations (average clustering) than intermediate and top-ranked teams. However, all the three clusters diverged in terms of passing intensity, with top-ranked teams having higher number of passes per possession time, than intermediate and bottom-ranked teams. Finally, similarities and dissimilarities in team signatures of play between the 20 teams were displayed using Cohen’s effect size. In sum, findings suggest the competitive performance was influenced by the density and connectivity of the teams, mainly due to the way teams use their possession time to give intensity to their game.

First-priority relation graph-based malicious users detection in mobile social networks

Mobile social networks (MSNs) consist of many mobile users (individuals) with social characteristics, that provide a variety of data delivery services involving the social relationship among mobile individuals. Because mobile users move around based on their common interests and contact with each other more frequently if they have more social features in common in MSNs. In this paper, we first propose the first-priority relation graph, say FPRG, of MSNs. However, some users in MSNs may be malicious. Malicious users can break the data delivery through terminating the data delivery or tampering with the data. Therefore, malicious users will be detected in the process of looking for the data delivery routing to obtain efficient and reliable data delivery routing along the first-priority relation graph. Secondly, we propose one hamiltonian cycle decomposition of FPRG-based adaptive detection algorithm based on in MSNs under the PMC detection model (the system-level detection model).

Space-crossing : community-based data forwarding in mobile social networks under the hybrid communication architecture

In this paper, we study two tightly coupled issues, space-crossing community detection and its influence on data forwarding in mobile social networks (MSNs). We propose a communication framework containing the hybrid underlying network with access point (AP) support for data forwarding and the base stations for managing most of control traffic. The concept of physical proximity community can be extended to be one across the geographical space, because APs can facilitate the communication among long-distance nodes. Space-crossing communities are obtained by merging some pairs of physical proximity communities. Based on the space-crossing community, we define two cases of node local activity and use them as the input of inner product similarity measurement. We design a novel data forwarding algorithm Social Attraction and Infrastructure Support (SAIS), which applies similarity attraction to route to neighbor more similar to destination, and infrastructure support phase to route the message to other APs within common connected components. We evaluate our SAIS algorithm on real-life datasets from MIT Reality Mining and University of Illinois Movement (UIM). Results show that space-crossing community plays a positive role in data forwarding in MSNs. Based on this new type of community, SAIS achieves a better performance than existing popular social community-based data forwarding algorithms in practice, including Simbet, Bubble Rap and Nguyen's Routing algorithms.

Dynamic social networks in guppies (Poecilia reticulata)

One of the main challenges in the study of social networks in vertebrates is to close the gap between group patterns and dynamics. Usually scan samples or transect data are recorded to provide information about social patterns of animals, but these techniques themselves do not shed much light on the underlying dynamics of such groups. Here we show an approach which captures the fission-fusion dynamics of a fish population in the wild and demonstrates how the gap between pattern and dynamics may be closed. Our analysis revealed that guppies have complex association patterns that are characterised by close strong connections between individuals of similar behavioural type. Intriguingly, the preference for particular social partners is not expressed in the length of associations but in their frequency. Finally, we show that the observed association preferences could have important consequences for transmission processes in animal social networks, thus moving the emphasis of network research from descriptive mechanistic studies to functional and predictive ones.

Funzioni di Matrici. Proprieta' e applicazione ai social networks

Teoria delle funzioni di matrici. Spiegazione del concetto di network, proprietà rilevanti rilevate attraverso determinate funzioni di matrici. Applicazione della teoria a due esempi di network reali.

Social networks in Argentinian libraries : Tips to formulate a communicational policy

En base a los resultados obtenidos en investigaciones efectuadas por el grupo de investigación del Instituto de Investigaciones en Humanidades y Ciencias Sociales (UNLP-CONICET) sobre redes sociales en distintos tipos de bibliotecas (de investigación, universitarias y populares) en Argentina, se efectúa un balance sobre su uso en este tipo de instituciones y se proponen lineamientos para la formulación de una política comunicacional que las contemple y forme parte del plan de gestión de estas unidades de información. Los mismos apuntan a considerar cabalmente todos los aspectos vinculados a los alcances, limitaciones, usos, riesgos y demás que implica la adopción y la apropiación de diferentes redes sociales (tales como Facebook, Twitter, entre otras), su convivencia, gestión y sustentabilidad a lo largo del tiempo

Trustworthiness-hypercube-based reliable communication in mobile social networks

In mobile social networks (MSNs), the routing packet is forwarded from any user of in a group to any user of the other group until it reaches the destination group - the group where the destination is located. However, it is inevitable that malicious groups could compromise the quality and reliability of data. To alleviate such effect, analyzing the trustworthiness of a group has a positive influence on the confidence with which a group conducts transactions with that group. In our previous work, the feature-based first-priority relation graph (FPRG) of MSNs is proposed, in which two vertices (groups) are connected iff they have a first-priority relationship. In this paper, the trustworthiness computation of a group is firstly presented in the algorithm TC (Trustworthiness Computing) based on the FPRG. The trustworthiness of a group is evaluated based on the trustworthiness of neighbors and the number of malicious users in the group. We then establish the Trustworthiness-Hypercube-based Reliable Communication (THRC) algorithm in MSNs. The algorithm THRC can provide an effective and reliable data delivery routing. Finally, we also give two scenario simulations to elaborate the processes of the trustworthiness computation and reliable communication.

Criação de uma plataforma e-commerce para a página de Facebook Handmade, nós apoiamos

Trabalho de projeto apresentado à Escola Superior de Comunicação Social como parte dos requisitos para obtenção de grau de mestre em Publicidade e Marketing.

Plateforme pour se protéger tant de soi-même que de ses "amis" sur Facebook

Les réseaux sociaux accueillent chaque jour des millions d’utilisateurs. Les usagers de ces réseaux, qu’ils soient des particuliers ou des entreprises, sont directement affectés par leur fulgurante expansion. Certains ont même développé une certaine dépendance à l’usage des réseaux sociaux allant même jusqu’à transformer leurs habitudes de vie de tous les jours. Cependant, cet engouement pour les réseaux sociaux n’est pas sans danger. Il va de soi que leur expansion favorise et sert également l’expansion des attaques en ligne. Les réseaux sociaux constituent une opportunité idéale pour les délinquants et les fraudeurs de porter préjudice aux usagers. Ils ont accès à des millions de victimes potentielles. Les menaces qui proviennent des amis et auxquelles font face les utilisateurs de réseaux sociaux sont nombreuses. On peut citer, à titre d’exemple, la cyberintimidation, les fraudes, le harcèlement criminel, la menace, l’incitation au suicide, la diffusion de contenu compromettant, la promotion de la haine, l’atteinte morale et physique, etc. Il y a aussi un « ami très proche » qui peut être très menaçant sur les réseaux sociaux : soi-même. Lorsqu’un utilisateur divulgue trop d’informations sur lui-même, il contribue sans le vouloir à attirer vers lui les arnaqueurs qui sont à la recherche continue d’une proie. On présente dans cette thèse une nouvelle approche pour protéger les utilisateurs de Facebook. On a créé une plateforme basée sur deux systèmes : Protect_U et Protect_UFF. Le premier système permet de protéger les utilisateurs d’eux-mêmes en analysant le contenu de leurs profils et en leur proposant un ensemble de recommandations dans le but de leur faire réduire la publication d’informations privées. Le second système vise à protéger les utilisateurs de leurs « amis » dont les profils présentent des symptômes alarmants (psychopathes, fraudeurs, criminels, etc.) en tenant compte essentiellement de trois paramètres principaux : le narcissisme, le manque d’émotions et le comportement agressif.

Context-awareness privacy in data communications

Internet users consume online targeted advertising based on information collected about them and voluntarily share personal information in social networks. Sensor information and data from smart-phones is collected and used by applications, sometimes in unclear ways. As it happens today with smartphones, in the near future sensors will be shipped in all types of connected devices, enabling ubiquitous information gathering from the physical environment, enabling the vision of Ambient Intelligence. The value of gathered data, if not obvious, can be harnessed through data mining techniques and put to use by enabling personalized and tailored services as well as business intelligence practices, fueling the digital economy. However, the ever-expanding information gathering and use undermines the privacy conceptions of the past. Natural social practices of managing privacy in daily relations are overridden by socially-awkward communication tools, service providers struggle with security issues resulting in harmful data leaks, governments use mass surveillance techniques, the incentives of the digital economy threaten consumer privacy, and the advancement of consumergrade data-gathering technology enables new inter-personal abuses. A wide range of fields attempts to address technology-related privacy problems, however they vary immensely in terms of assumptions, scope and approach. Privacy of future use cases is typically handled vertically, instead of building upon previous work that can be re-contextualized, while current privacy problems are typically addressed per type in a more focused way. Because significant effort was required to make sense of the relations and structure of privacy-related work, this thesis attempts to transmit a structured view of it. It is multi-disciplinary - from cryptography to economics, including distributed systems and information theory - and addresses privacy issues of different natures. As existing work is framed and discussed, the contributions to the state-of-theart done in the scope of this thesis are presented. The contributions add to five distinct areas: 1) identity in distributed systems; 2) future context-aware services; 3) event-based context management; 4) low-latency information flow control; 5) high-dimensional dataset anonymity. Finally, having laid out such landscape of the privacy-preserving work, the current and future privacy challenges are discussed, considering not only technical but also socio-economic perspectives.

Perceções e atitude acerca da publicidade nas redes sociais e nos motores de pesquisa : uma análise comparativa

Mestrado em Marketing

A recommendation method for online dating networks based on social relations and demographic information

A new relationship type of social networks - online dating - are gaining popularity. With a large member base, users of a dating network are overloaded with choices about their ideal partners. Recommendation methods can be utilized to overcome this problem. However, traditional recommendation methods do not work effectively for online dating networks where the dataset is sparse and large, and a two-way matching is required. This paper applies social networking concepts to solve the problem of developing a recommendation method for online dating networks. We propose a method by using clustering, SimRank and adapted SimRank algorithms to recommend matching candidates. Empirical results show that the proposed method can achieve nearly double the performance of the traditional collaborative filtering and common neighbor methods of recommendation.

The influence of social communication networks on intentions to purchase on the web

Despite the increased offering of online communication channels to support web-based retail systems, there is limited marketing research that investigates how these channels act singly, or in combination with online channels, to influence an individual' s intention to purchase online. If the marketer's strategy is to encourage online transactions, this requires a focus on consumer acceptance of the web-based transaction technology, rather than the purchase of the products per se. The exploratory study reported in this paper examines normative influences from referent groups in an individual's on and offline social communication networks that might affect their intention to use online transaction facilities. The findings suggest that for non-adopters, there is no normative influence from referents in either network. For adopters, one online and one offline referent norm positively influenced this group's intentions to use online transaction facilities. The implications of these findings are discussed together with future research directions.

The economies within an online social network market : A case study of Ravelry

The capacity of the internet to handle micro-transactions and to cater to niche markets is a boon for some areas of the creative industries, which have always been associated with smallscale micro business activities. This paper looks at the specific case of the specialist Social Networking Site Ravelry: a site for knitters, crocheters, spinners and dyers. It traces the interactions between amateurs and professionals through the emergence of social networking sites. An analytic framework of social network markets (see Potts, Cunningham, Hartley and Omerod, 2008) is employed to allow for the inclusion of amateur, social, semi-professional,professional and institutional actors within a networked sphere of activity, rather than excluding some of these actors as outside of recognised value-production. The reliance on social networks to determine the economic success of design, production and consumption is exemplified in this small scale example. This paper eschews the dichotomy of commercial and non-commercial by bringing to the fore the hybridity of this site where financial and social economies co-exist.