Keywords: roles, role detection, social network analysis, forums, machine learning, clustering, Bayesian statistics, Dirichlet process, graphs

This thesis addresses the problem of detecting user roles in online discussion forums. A role may be defined as the set of behaviors characteristic of a person or a position. In discussion forums, behaviors are primarily observed through conversations. Hence, we focus our attention on how users discuss. We propose three methods to detect groups of users with similar conversational behaviors.

Our first method for the detection of roles is based on conversational structures. We apply different notions of neighborhood for posts in tree graphs (radius-based, orderbased, and time-based) and compare the conversational patterns that they detect as well as the clusters of users with similar conversational patterns.

Our second method is based on stochastic models of growth for conversation threads. Building upon these models we propose a method to find groups of users that tend to reply to the same type of posts. We show that, while there are clusters of users with similar replying patterns, there is no strong evidence that these behaviors are predictive of future behaviors -except for some groups of users with extreme behaviors.

In out last method, we integrate the type of data used in the two previous methods (feature-based and behavioral or functional-based) and show that we can find clusters using fewer examples. The model exploits the idea that users with similar features have similar behaviors.

Résumé

Nous traitons dans cette thèse le problème de la détection des rôles des utilisateurs sur des forums de discussion en ligne. On peut définir un rôle comme l'ensemble des comportements propres d'une personne ou d'une position. Sur les forums de discussion, les comportements sont surtout observes à travers des conversations. Pour autant, nous centrons notre attention sur la manière dont les utilisateurs dialoguent. Nous proposons trois méthodes pour détecter des groupes d'utilisateurs où les utilisateurs d'un même groupe dialoguent de façon similaire.

Notre première méthode se base sur les structures des conversations dans lesquelles les utilisateurs participent. Nous appliquons des notions de voisinage différentes (radiusbased, order-based, and time-based) applicables aux commentaires qui sont représentés par des noeuds sur un arbre. Nous comparons les motifs de conversation qu'ils permettent de détecter ainsi que les groupes d'utilisateurs associés à des motif similaires.

Notre deuxième méthode se base sur des modèles stochastiques de croissance appliqués aux fils de discussion. Nous proposons une méthode pour trouver des groupes d'utilisateurs qui ont tendance à répondre au même type de commentaire. Nous montrons que, bien qu'il y ait des groupes d'utilisateurs avec des motifs de réponse similaires, il n'y a pas d'évidence forte qui confirme que ces comportements présentent des propriétés prédictives quant aux comportements futurs -sauf pour quelques groupes avec des comportements extrêmes.

Avec notre troisième méthode nous intégrons les types de données utilisés dans les deux méthodes précédentes (feature-based et behavioral ou functional-based) et nous montrons que le modèle trouve des groupes en ayant besoin de moins d'observations. L'hypothèse du modèle est que les utilisateurs qui ont des caractéristiques similaires ont aussi des comportements similaires. mots clé: rôles, détection de rôles, analyse des réseaux sociaux, forums, apprentissage automatique, clustering, statistique bayésienne, processus de Dirichlet, graphes.

Introduction

The more the individual is concerned with the reality that is not available to perception, the more must he concentrate his attention on appearances.

F

rom the first newsgroups in the 1980s up to the present day, online forums have always been amongst the most popular ways of online communication. Even after the huge expansion of social networks, forums are still used by 15% of online users in the U.S. [START_REF] Duggan | Mobile Messaging and Social Media 2015[END_REF]. Modern forums cover a large variety of topics such as politics, health, technology or video-games, and many applications such as questions & answers (Q&A), sharing and discussing news (newsboards), seeking other students help in Massive Open Online Courses (MOOC) or discussing among supporters of a political cause. The current growth of forums like Quora, Reddit, or StackExchange suggests that this form of online communication is stronger than ever and that it still has an enormous potential ahead in terms of the number of users and application to novel areas.

As forums become more populated and users produce more content, they open the door to new challenges and opportunities in fields like Computer Science, Complex Systems and Sociology. Computer Scientists may develop tools to help users explore the content of the forums so that the experience is satisfactory and users do not abandon the community; areas like Machine Learning, Information Retrieval and Recommender Systems are starting to play an important role here. The framework of Complex Networks is excellent to analyze and understand how new dynamics emerge from micro to macro levels, or from the individual to the community. Some models have been proposed, for instance, to explain how the structure of a conversation grows over time [START_REF] Kumar | Dynamics of Conversations[END_REF][START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF], and it is astonishing to see how some mathematical models 1. Introduction of human dynamics have the simplicity of physical laws. Online forums are also places where communities emerge [START_REF] Kollock | Communities in Cyberspace[END_REF]. The net of interactions between users in the form of posts, or comments, ends up creating shared meanings and, in general, a common culture that defines and delimits the set of possible behaviors. As an example, the popular slogan don't feed the troll suggests users to ignore those playing the role of a troll. Nonetheless, the most fruitful approaches need to be interdisciplinary. Forums are big data, complex systems and human communities and, as such, an integrated view is likely to shed more fruitful results than the sum of the parts [START_REF] Mcfarland | Sociology in the Era of Big Data: The Ascent of Forensic Social Science[END_REF][START_REF] Tinati | Big Data: Methodological Challenges and Approaches for Sociological Analysis[END_REF].

The central topic of this thesis is online roles. Social roles have been widely studied by sociologists, anthropologists, and psychologists. For them, a social role is a behavior that a community expects from an individual that occupies some position in that community. A canonical ethnological study of roles in online forums was done in [START_REF] Golder | A Typology of Social Roles in Usenet[END_REF]. Online roles have also been studied by computer scientists, who have put more emphasis on the detection of roles. In computer science, a role is usually regarded as a set of user-centered features or as the position that the individual holds in the social graph.

We think that one of the most interesting aspects of roles in sociology is that, once we know the role of an individual, we can predict, to some extent, how the individual will behave in a given situation. Roles are both descriptive and predictive categories of behavior. We know how to address the two problems separately: a descriptive categorization of users is an unsupervised learning task (clustering), while learning to predict users behaviors from a log of past behaviors is often a supervised learning task. However, integrating both tasks is not trivial.

The aim of this thesis is precisely to integrate both a descriptive and a predictive vision of online roles. By thinking of roles as archetypical behaviors, we will explore some ways to find clusters of users with similar behaviors.

The remaining of this chapter is as follows. In Section 1.1, we will introduce the notion of role in sociology. Before going any further into how roles are conceptualized in online contexts we introduce, in Section 1.2.2, some basic vocabulary of discussion forums and different formal representations of user interactions; we will apply our role detection methods on these representations. In Section 1.3 we will introduce the State of the Art of role analysis and detection in online forums. We close this chapter in Section 1.5 with a summary and an outline of the thesis.

Role Theory

Imagine a metro station. If we observed the social life for several days, including the behaviors and the interactions of the passengers, what would we find? A big amount of what happens there seems ephemeral and chaotic but, after a few days, we would notice some patterns in many aspects such as the way people choose their seats, their interpersonal distances or their conversations [START_REF] Nash | Bus riding: community on wheels[END_REF]. Learning these patterns helps to understand the inner mechanisms of the metro community such as its rituals and its norms. Despite being the first time most of the metro passengers see each 1.1. Role Theory other, and despite the absence of explicit norms for most of the observed behaviors, the emergence of these patterns is possible thanks to a mixture of biology, culture, and a network of inter-personal interactions that enable the propagation of norms, beliefs, and expectations between passengers who never shared the same wagon.

A very special pattern is what sociologists call a role. Following Ervin Goffman's metaphor of the social drama [START_REF] Goffman | The presentation of self in everyday life[END_REF], a role is a script that an individual (actor) plays in front of others (audience) because the others expect the individual to do so. In the metro, when an old lady stands beside a sitting teenager, everyone expects the teenager to offer his seat to the lady. This expectation does not depend on the particular teenager nor the particular lady, but on their social positions.

The idea that a role is attached to a social position has two interesting consequences: on the one hand, a role census of a community, and the description of behaviors attached to every role, represent a good summary of the community. On the other hand, knowing the role of an individual allows us to predict the way the individual is likely to behave in a given situation, even if we have no other information about the individual. Or to put it in Golder and Donath words [START_REF] Golder | Social roles in electronic communities[END_REF]:

Roles, in turn, are useful because, when they comprise sets of expectations, they allow us to generalize across people and have some a priori knowledge about entire categories of people, how to act toward them and what to expect in their actions toward us. More importantly, we categorize people precisely in order to understand them [START_REF] Foucault | Abnormal. In Lectures at the Collège de France 1974 -1975[END_REF], because having expectations is so vital to our understanding of others.

Although role theory has been around at least since the first half of the 20th century, there is neither a unified theory nor a single definition of role. In Role Theory: Expectation, Identities, and Behaviors [START_REF] Biddle | Role Theory: Expectations, Identities, and Behaviors[END_REF], the author complained:

And as a matter of fact, the plasticity of role concepts is one of the major reasons why the role orientation is popular. Since social scientists have rarely found it necessary to spell out exactly what they meant by role, social position, or expectation, these terms could be applied with impunity to almost any purpose. Role might be considered an identity, a set of characteristic behaviors, or a set of expectations; expectations might be descriptive, prescriptive, or evaluative; and so it goes. And given such a superficial level of analysis, it would be possible either to exalt or decry role notions with equal enthusiasm since each of us would be talking about somewhat different things.

Social scientists have confronted the issue of roles from different approaches which, in part, reflect the sociological debate. The functionalist approach considers that a society, as the human body, is a system where every part has a function [START_REF] Linton | The Study of Man[END_REF][START_REF] Parsons | The Social System[END_REF]; functionalism sees a role as the behaviors that the community expects from an individual because he occupies a given position. The symbolic interactionism approach thinks of a society as the result of the interactions between individuals [START_REF] Mead | Mind, self, and society[END_REF]; interactionism sees that roles are continually negotiated and individuals take, define or modify roles as a result of their interactions. The structuralist approach to roles models a society as a set of positions, filled by persons and relationships between positions [START_REF] Nadel | The theory of social structure[END_REF]; individuals that fill the same positions are said to have the same role. Though it imposes a very restrained view of roles, it is easy to formalize mathematically; later we will see a popular formalization called blockmodeling introduced by [START_REF] White | Social structure from multiple networks. I. Blockmodels of roles and positions[END_REF]. See [START_REF] Biddle | Recent Developments in Role Theory[END_REF] for a complete review and further discussion about the different approaches.

Biddle proposes a soft definition that captures the elements that are shared by most approaches [START_REF] Biddle | Role Theory: Expectations, Identities, and Behaviors[END_REF]:

In current social science the term role has come to mean a behavioral repertoire characteristic of a person or a position; a set of standards, descriptions, norms, or concepts held for the behaviors of a person or social position; or (less often) a position itself.

Online forums

Before delving into how roles are analyzed and detected in online communities, let us first introduce some basic concepts regarding the vocabulary of forums and their graph representations.

Vocabulary

• A forum (also online forum, internet forum or message board ) is an online discussion site where people can hold written conversations in the form of textual messages. Forums are made by threads and threads are made by posts. Forum sites usually sub-divide their content in big topics such as sports, politics, science, statistics or programming. Since the same site often hosts forums of different topics we may also use the word subforums.

• A post (also comment or message) is a text message written by a user to participate in a conversation thread. The root post is the first message of a thread. Usually, root posts are questions or links to some content (e.g., an online article) that might interest the community.

• A thread (also discussion thread or conversation) is a conversation around the topic started by the root post. A thread is made by posts where users reply to each other. In some contexts we will also use the term conversation to talk about specific parts of the thread instead of the whole thread.

• A reply is a post written in reply to another post. Every post, except the root, is a reply to some other previous post. The replied post is the parent of the post.

Forums as graphs

In this thesis, we study roles from a structural point of view. To this aim, we represent user activity in the form of graphs. Deciding what vertices and edges represent must be subjected to the type of analysis we want to make. We use three representations: in the coparticipations graph, edges represent participations in the same thread; in the interactions graph, representation edges represent replies between users; in the tree graph, vertices represent posts and edges represent replies from one post to another.

Coparticipations graph: A coparticipation graph is an undirected graph where vertices represent users, and where an edge between u and v, denoted as (u, v), indicates that u and v have participated at least once in the same thread.

Interactions graph: An interactions graph (or replies graph) is a graph where vertices represent users and an edge between u and v, denoted as (u, v), indicates that u has replied to a post of user v in some of the threads.

Discussion tree graph: A discussion tree graph is a graph that represents a single thread. Vertices correspond to posts and an edge between post u and v, denoted as (u, v), indicates that u is a reply to v.

Note that we can-and we should-customize these graphs to our needs. For instance, we can impose a threshold for an edge to exists (a minimum number of coparticipations or interactions), or put weights on edges, or make the interactions graph undirected. Also, we can set stronger conditions for an edge to exist, such as the existence of replies in both directions or a minimum number of replies.

Figure 1.1 we show a real conversation of a forum represented both as a tree and as an interaction graph (although an interactions graph is not limited to one single thread). Unlike the interactions and the coparticipation graphs, which aggregate interactions over a period of time, a tree graphs represent the dynamics of a conversation in a thread without any loss of structural information. That makes them very appropriate to our task of finding roles based on how different users converse. For this reason, we will especially focus our attention in tree graphs.

Looking at the tree of Figure 1.1 one may think -and rightly so-that the textual content in each of the vertices would give much relevant information about a user's behavior. Content and structure are not competitors but complementary perspectives. For example, a debate between two users may be detected either through textual analysis or through a cascade such as

C ← E ← C ← E or C ← E ← C ← E in the figure.

Role detection in online communities

In some sense, an online forum is similar to the metro example that we introduced earlier. Imagine now an online forum. Just as it happens in the metro, forums are places with none or few explicit norms and where most of the participants have never seen each other. The collective behavior of the forum users also follows several patterns [START_REF] Whittaker | The dynamics of mass interaction[END_REF] and individuals also play several social roles. refine the findings at the higher levels. The analysis goes on until the researcher finds a good correlation between a role category and a behavioral pattern.

It is important to choose the right starting point for social role research. Starting from simple behavioral regularities or distinctive social positions is a flawed approach because it is overly inductive: of the infinite patterns we can find, there is no reason to think that the ones that initially stand out will be of any social significance. Starting from abstract categories like 'altruist' commits the error of over-deduction: simply because we can label a set of activities as altruistic does not necessarily mean that those behaviors are motivated by altruism. The key is to connect higher levels and abstract categories to observable behavioral regularities and distinctive network positions in order to discover types of actors relevant to theoretical questions in social research. [START_REF] Gleave | A Conceptual and Operational Definition of 'Social Role' in Online Community[END_REF] When the size of the community is significant, the researcher can only identify and describe the key roles by studying a small set of individuals. However, these methods are not able to label each member of the community.

Blockmodeling

The family of blockmodeling algorithms searches groups of users who share similar relationships to the other groups. Blockmodeling works over the sociomatrix, a U × U matrix where the cell (i, j) contains a value that reflects the relationship from user i to user j. The relationship may be, for instance, the level of affection from i to j, the number of telephone calls or the number of replies from i to j in a discussion forum.

The initial motivation of blockmodeling raised from sociology and the study of structural roles of individuals that hold the same position in their social networks. If our community is a family and relations are "is son of", the positions of two siblings, though not exactly the same, are structurally equivalent since their relationships with the rest of the family members are exactly the same: they both are siblings of their parents, as well as nephews of their mothers' brother, and so forth.

Historically, different notions of similarity have motivated different algorithms. Structural equivalence [START_REF] Lorrain | Structural equivalence of individuals in social networks[END_REF] considers that two users are equivalent if they are equally related to the same other users. Regular equivalence [START_REF] White | Graph and semigroup homomorphisms on networks of relations[END_REF] considers that two users are equivalent if they are equally related to the same other groups of equivalent users. Finally, stochastic equivalence [START_REF] Holland | Stochastic blockmodels: First steps[END_REF] considers that two users are similar if they tend to be equally related to the other groups of equivalent users. Following this last definition, [START_REF] Nowicki | Estimation and prediction for stochastic blockstructures[END_REF] derived a general Bayesian model that has been the base of many Stochastic Blockmodeling adaptations to different kinds of data.

For the sake of illustration, let G be a binary matrix that encodes the set of observed relationships between a group of U individuals (e.g.: g ij = 1 for i likes j and 0 otherwise). Let us assume that each individual is member of one out of K social groups and let 1. Introduction z 1 ,...z U denote the latent, or unknown, membership of each individual. Let η ab be the probability that a member of the group a likes a member of the group b. If we knew the memberships z and the probabilities η, we could compute the likelihood of the observed G as:

p(G|η, z) = U i=1 U j=1 (η z i ,z j ) g ij (1 -η z i ,z j ) g ij (1.1)
But we do not know the values of z and η. The inverse, that is inferring the posterior probabilities of z and η from the observed data, can be done via Bayes formula:

posterior p(η, z|G) = likelihood   U i=1 U j=1 (η z i ,z j ) g ij (1 -η z i ,z j ) g ij   prior p(z)p(η) z η   U i=1 U j=1 (η z i ,z j ) g ij (1 -η z i ,z j ) g ij   p(z)p(η) marginal likelihood (1.2)
where p(z) and p(η) are some prior probabilities that we assign to the latent variables.

The priors are often chosen by analytical convenience so that the term in the denominator becomes integrable. This happens, for instance, when the prior is conjugate to the likelihood. Unfortunately, likelihood functions often lack a conjugate prior. In these cases, the inference is mostly made either by Monte Carlo sampling (usually Gibbs Sampling) or by Variational Inference. While the former is a technique to draw samples from the true posterior, the latter is a (computationally faster) technique to obtain an analytical approximation to the posterior. Because inference in blockmodels is very computationally demanding due to its relational nature, the popularity of the variational approaches has increased in the last years [START_REF] Daudin | A mixture model for random graphs[END_REF][START_REF] Latouche | Variational Bayesian Inference and Complexity Control for Stochastic Block Models[END_REF]. Stochastic Blockmodeling can be adapted to edges with all sorts of weight distributions such as Poisson (DuBois et al., 2013) or Gaussian. Other variations are also possible, such as allowing users to belong to many clusters (Mixed Membership Stochastic Blockmodels, [START_REF] Airoldi | Mixed Membership Stochastic Blockmodels[END_REF]) or to change their interaction patterns, and thus their roles, over time [START_REF] Fu | Dynamic mixed membership blockmodel for evolving networks[END_REF][START_REF] Ho | Evolving Cluster Mixed-Membership Blockmodel for Time-Varying Networks[END_REF]. An appealing contribution is that of non-parametric blockmodeling that infers the number of clusters using a Dirichlet Process prior over the cluster assignments [START_REF] Kemp | Discovering latent classes in relational data[END_REF][START_REF] Kemp | Learning systems of concepts with an infinite relational model[END_REF].

Although blockmodeling can be applied to many types of adjacency matrices, its application to forums has some particular limitations. Figure 1.2 shows the blockmodels in an undirected binary matrix of interactions between the 100 most active users in the forums (according to the model of [START_REF] Daudin | A mixture model for random graphs[END_REF] available in the R package mixer). While blockmodels uncover interesting structures in interaction or coparticipation matrices, such as blocks of users that avoid each other, they have important limitations in the context of online forums. First, the white blocks detected, might represent a group of Figure 1.2 Blockmodeling over the interactions matrix of the 100 most active users users that arrived some time later and thus did not have time to interact with the other users -to solve this, we would need a dynamic or longitudinal blockmodeling where nodes can appear and disappear. Second, even if a blockmodel is applied to analyze the block structure of a single thread, the positions of a user in two different threads are hardly comparable, and it is difficult to say anything about the role of a user beyond a particular conversation.

Feature-based

Most role detection in discussion forums are based on describing each user through a set of features and then classifying users by clustering or by some rules based on thresholds to find groups of users with similar features. The resulting clusters are interpreted as roles. [START_REF] Himelboim | Discussion catalysts in online political discussions: Content importers and conversation starters[END_REF] search catalists -users that start discussions and attract many participants and posts-since they are the ones that set the topics that the community debates about. They classify a user as a catalyst if they have a high score in three metrics: number of posts attracted by their threads (reply share), the number of users in their threads (replier share), and ratio of threads that get comments from at 1. Introduction least two users. [START_REF] Welser | Visualizing the Signatures of Social Roles in Online Discussion Groups Finding Social Roles in Online Discussion[END_REF] and [START_REF] Gleave | A Conceptual and Operational Definition of 'Social Role' in Online Community[END_REF] selected users with recognized roles and found that the egonet of a user is very attached to its role. Based on this idea, [START_REF] Buntain | Identifying Social Roles in Reddit Using Network Structure[END_REF] select some features from the egonet and find clusters over them. The features are undirected network density, low degree distribution, the ratio of neighbors with low degree, the proportion of intense ties, clustering coefficients, and triangle density. [START_REF] Chan | Decomposing discussion forums using common user roles[END_REF] and [START_REF] White | Mixed Membership Models for Exploring User Roles in Online Fora[END_REF] select a set of user features and perform a clustering over them. They analyze the resulting clusters and manually merge some of them if they represent the same type of user; then each cluster is defined as a role. The set of features is the indegree and outdegree exponents of their egonets, the ratio of neighbors that replied to each other, the mean and standard deviation of posts per thread, their in-degree, the number of posts with at least one reply, the ratio of initiated threads. Using these same features, [START_REF] Angeletou | Modelling and analysis of user behaviour in online communities[END_REF] build a rule-based system with adaptive thresholds instead of a clustering. [START_REF] Rowe | Community analysis through semantic rules and role composition derivation[END_REF] extend their work on [START_REF] Angeletou | Modelling and analysis of user behaviour in online communities[END_REF] and propose five features: the proportion of users that the user has replied to, the proportion of threads created by the user, the proportion of threads started by the user, and the average points per post awarded to the user.

In the context of TV-series forums, [START_REF] Anokhin | Social Citation: Finding Roles in Social Networks. An Analysis of TV-Series Web Forums[END_REF] use some basic features and adapt some others from the citation analysis literature such as the h-index [START_REF] Hirsch | An index to quantify an individual's scientific research output[END_REF] and the g-index [START_REF] Egghe | Theory and practise of the g -index[END_REF]. They also use a cross-topic entropy to measure how focused is a user in a TV-show. [START_REF] Forestier | Extracting celebrities from online discussions[END_REF] look for celebrities based on the ethnological study of [START_REF] Golder | Social roles in electronic communities[END_REF]. They build some meta-features based on the number of posts the in-degree and out-degree of the user in the reply network, and the number of threads.

One of the advantages of these methods is that the results are easy to interpret since each role is clearly attached to a range of values in each feature. Besides, a different choice of features will give us a set of roles based on different criteria, which may be useful if the researcher is especially interested in one specific aspect of user behavior.

Table 1.1 summarizes the main features used in the literature.

Triads and motifs

Another approach to detecting user roles is looking at the triads where they appear in the interaction graph (or some other representation). A triad is a graph consisting of three vertices. There are 16 possible triads, from the empty triad with no edges to the fully connected triad (Figure 1.3). Triads have been largely used in social network analysis since they represent their most basic building blocks [START_REF] Wasserman | Social network analysis: Methods and applications[END_REF]. When a triad is statistically over-represented-it appears significantly more frequently than expected-it is called a motif [START_REF] Milo | Network motifs: simple building blocks of complex networks[END_REF]. Motifs have been used in online forums to analyze patterns over the Q&A graph [START_REF] Adamic | Knowledge sharing and yahoo answers[END_REF].

To test whether a triad is over-represented, we need a reference null model. The null model can be built by randomizing the original graph while preserving some of its Figure 1.3 List of all possible triads and their labels in MAN notation [START_REF] Holland | A method for detecting structure in sociometric data[END_REF]. This notation records the number of mutual (M), asymmetric, (A) and null (N) dyads in each triad, along with further indication of the direction of ties.

properties such as the degree distribution. Given a set of randomized versions of the graph, we can then easily compute the z-score and p-value of the triad in the real graph to decide whether its frequency is statistically significant or if it can be explained by the reference model. A good null model should reproduce known properties of the graph so that the motifs that are detected are those that cannot be explained by our current knowledge. Some null models are, for instance, the rewiring of the edges that preserve the degree distribution [START_REF] Wernicke | FANMOD: A tool for fast network motif detection[END_REF] or random graphs that keep the same blockmodel structure [START_REF] Birmelé | Detecting local network motifs[END_REF].

It is important to note that conversation trees are acyclic graphs, and therefore not all randomisation strategies can be applied. A valid strategy would be to re-build the tree sequentially: for every new vertex, choose a parent vertex uniformly from the vertices that are already in the tree. We may respect the degree distribution (e.g., [START_REF] Dorat | Multi-level analysis of an interaction network between individuals in a mailing-list[END_REF]) or give a probability to each parent according to some thread growth model such as [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF].

A major impediment for the application of triads to conversations is that there are only three possible triads in a tree (012, 021U, and 021C, see Figure 1.3) and therefore a triad analysis in a tree is less verbose than a triad analysis in an interaction graph. The obvious solution is to convert the tree into an interactions graph and do the triad analysis there. However, we would be losing the conversation structure; a chain in the interaction graph (triad 021C) does not necessarily correspond to a chain in the tree graph (see Figure 1.1) In Chapter 3, we propose some extensions for a richer analysis of tree-shaped conversations.

Other methods

There are other approaches that fall off the above categories. Some authors, for instance, have proposed different visualizations to spot interesting roles. [START_REF] Viegas | Newsgroup Crowds and AuthorLines: visualizing the activity of individuals in conversational cyberspaces[END_REF] designed a visualization tool to plot some aspects of authors posting behavior, and used this tool to visually identify some roles. [START_REF] Fisher | You Are Who You Talk To: Detecting Roles in Usenet Newsgroups[END_REF] proposed using egonets 1.4. Industrial context of the thesis of second degree and their degree distribution. An analysis of different visualization methods and their utility to find roles can be found in [START_REF] Welser | Visualizing the Signatures of Social Roles in Online Discussion Groups Finding Social Roles in Online Discussion[END_REF].

Of course, the concept of role is not limited to discussion forums. They have also been studied in Q&A forums [START_REF] Furtado | Contributor profiles, their dynamics, and their importance in five q&a sites[END_REF], a feature-based approach that uses features like the number of questions, the number of answers, and the scores to their questions and answers given by the community. [START_REF] Maia | Identifying user behavior in online social networks[END_REF] build a social graph for the case of YouTube where edges mean subscriptions, and use features from the egonet (e.g.: in-degree, out-degree, reciprocity, and clustering coefficient) and activity features (e.g.: number of uploads, the number of watched videos) to cluster users. [START_REF] Labatut | Identifying the community roles of social capitalists in the Twitter network[END_REF] define social capitalists as users trying to increase their number of followers and interactions by any means possible and identify different types of social capitalists clustering users over structural features. [START_REF] Zhang | Expertise networks in online communities: structure and algorithms[END_REF] classify users of a Java forum in terms of expertise with an adapted PageRank algorithm. [START_REF] Welser | Finding social roles in Wikipedia[END_REF] apply their methodology presented in [START_REF] Gleave | A Conceptual and Operational Definition of 'Social Role' in Online Community[END_REF] to find roles in Wikipedia.

Although language is certainly an important indicator of user roles, it has been barely used for their automatic detection. In [START_REF] Golder | Social roles in electronic communities[END_REF], they describe a flamer as someone who tries to trigger long debates (flame wars). For instance, a flamer in Usenet wrote this:

Look moms (and dads), you little babies ARE NOT cute. Sorry to break the news, they are UGLY. So stop bringing them into the office so that fat old bags (who couldn't if they tried) can get up off their fat arses and say things "oh isn't that cute". YUCK.

Detecting this is a flamer requires knowing a cultural context where every one says babies are cute, something that is out beyond the current state of the art of Natural Language Processing. One might instead apply sentiment analysis over posts to detect the positiveness or negativeness of a user and add this feature to the role analysis. Topic analysis was used by [START_REF] Mccallum | Topic and role discovery in social networks with experiments on enron and academic email[END_REF], who mixed topic analysis and blockmodeling over the e-mails between Enron employees to detect their role (position) in the company, exploiting the fact people in the same position write about the same things to people in the same other positions. It is not clear, however, how this assumption would map into online forums where the community is already, by definition, a topic-based community.

Other authors have analyzed community-based roles in social graphs, such as bridges or hubs [START_REF] Scripps | Exploration of Link Structure and Community-Based Node Roles in Network Analysis[END_REF][START_REF] Chou | Discovering community-oriented roles of nodes in a social network[END_REF][START_REF] Gliwa | Analysis of roles and groups in blogosphere[END_REF][START_REF] Henderson | RolX: structural role extraction & mining in large graphs[END_REF] and their evolution over time [START_REF] Rossi | Modeling dynamic behavior in large evolving graphs[END_REF].

Industrial context of the thesis

This is an industrial thesis developed in Technicolor R&D France under the CIFRE program (Conventions Industrielles de Formation par la Recherche) founded by the Association Nationale de la Recherche et de la Technologie (ANRT) of the Ministère de l'Enseignement supérieur et de la Recherche.

Introduction

Technicolor is a company specialized in the media and entertainment sector. Its technologies and services range from film post-production (e.g.: visual effects, color enhancement,...) to Set-Top Boxes. Like many companies in the technological sector, Technicolor is paying a growing attention to the end-user services and, in particular, to user profiling and content personalization. Forums where people talk about movies or series are of particular interest for the company. On the one hand, they are a good source of information to measure the audience reaction to a movie. On the other hand, they can be a service themselves that add value to the final content: be it a simple fan forum or forums where users are also active participants of a transmedia narrative.

In this context, we have filled a patent based on the method presented in Chapter 5.

Outline of the thesis

The current methods of role detection are based on analyzing the interactions graph from different points of view (blockmodels, features or triads). In this thesis, we descend to the conversational level, represented by trees of posts, to find roles based on the different ways how people structurally talk.

The content and contributions of each of the following chapters is as follows.1 Chapter 2 is a general description of our dataset that will allow contextualizing the results of the subsequent chapters. A major conclusion of this chapter is that our forums are not big groups of users where everyone knows everyone -which might suggest, for instance, a blockmodeling approach-but rather a majority of occasional users and a minority of active users that creates most of the content.

In Chapter 3 we present our first method for the detection of roles based on conversational structures. We apply different notions of neighborhood for posts in tree graphs (radius-based, order-based, and time-based ) and show that our order-based neighborhoods, similarly to triads in other types graphs, are able to capture most of the relevant conversational structures with no need of complex patterns. We use these neighborhoods to detect groups of users that tend to participate in the same type of conversation.

In Chapter 4 we present our second method based on stochastic models of growth for conversation threads. Building upon these generative models we propose a method to find groups of users that tend to reply to the same type of posts. We show that, while we are able to find clusters of users based on their past behaviors, there is no evidence that these behaviors are predictive of future behaviors. This finding calls into question our concept of role as a consistent behavior of a user, at least concerning the type of conversational behavior that we consider here.

Note that, in Chapter 3, we cluster users based on feature vectors that are directly built from observed behaviors and, in Chapter 4, we assume an underlying behavioral function with latent parameters and we cluster users based on their estimated parameters. In Chapter 5 we present a third method that integrates the type of data used in the two previous chapters (feature-based and behavioral or functional-based) and that 1.5. Outline of the thesis can find clusters using fewer examples. The model exploits the idea that users with similar features have similar behaviors. Not only the method integrates inputs of different nature, adding more consistency to the clusters, but it tackles the problem of clustering users when most users have only participated a few times. We use synthetic data to show the properties of this model while leaving its application to real forums for our future research.

We conclude in Chapter 6 with a summary of the results and a discussion on the perspectives opened by this thesis.

2 Analysis of datasets • Slashdot (http://www.slashdot.com): Slashdot is a technology-news forum where moderators publish news posts for users to comment on them. In this dataset the tree structure is explicit, but the first post is missing. This forum has been widely analyzed in [START_REF] Gómez | Statistical analysis of the social network and discussion threads in slashdot[END_REF]; [START_REF] Kaltenbrunner | Description and Prediction of Slashdot Activity[END_REF]; [START_REF] Gómez | Modeling the structure and evolution of discussion cascades[END_REF][START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF].

• Reddit (http://www.reddit.com): Reddit is a giant forum of forums, called subreddits. Subreddits cover all kinds of topics, and new subreddits are continuously created. Since July 2015, a dataset with all Reddit content from 2007 is available for download and updated on a monthly basis. This is, by far, the best publicly available dataset regarding quality and quantity. Some Reddit data has been analyzed, for instance, in [START_REF] Wang | From user comments to on-line conversations[END_REF].

We finally chose the Reddit dataset because it is the only one with complete trees and years of data. We chose five subforums from which we downloaded all comments between 2013 and 2016 (Table 2.1):

• podemos (http://www.reddit.com/r/podemos): a forum for supporters of the Spanish party Podemos. It was conceived in March 2014 as a tool for internal democracy, and forum members used it to debate ideological and organizational principles that were later formalized in their first party congress held in Madrid on October 18th and 19th, 2014. Nowadays, its members use it mainly to share and discuss political news.

• gameofthrones (http://www.reddit.com/r/gameofthrones): a forum for discussions about the Game of Thrones TV series. Every new season is broadcasted in April, once a week, and every season has 10 episodes.

• france (http://www.reddit.com/r/france): a francophone generalist forum where users can talk about any subject although France-related topics (culture, politics,...) are especially frequent.

• TwoXChromosomes (http://www.reddit.com/r/TwoXChromosomes): a forum for women where users talk about any women-related topic and very oriented to advice-seeking.

• MachineLearning (http://www.reddit.com/r/MachineLearning): a forum where users asks questions and share news and articles about Machine Learning.

In the following sections, we analyze these subforums at three different levels-forum level, user level conversation (thread) level-computing appropriate measures for each level.

Forum dynamics

The analysis at forum level will give us an overview of the amount of activity in every forum, their periodicity (if any) or peaks that might happen due to internal or external factors. We will also analyze at which paces new users join the forum and how the activity is distributed between older and newer users.

Posting activity

How do the activity levels evolve over time? We first look at the number of comments posted every day in each forum (Figure 2.1). Interestingly, they show different patterns on their activity growth, their periodicities, and their peaks.

Growth. Some forums like france and MachineLearning show a smooth increase in the average number of posts per day. gameofthrones is stable during the inter-season hiatus, but increases its activity levels every time a new season begins, probably thanks to an increasing popularity of the TV series. podemos is the forum with the most drastic initial transition, certainly coupled with its popularity and the expectations that the party raised in Spain. Its current decrease of the mean activity levels might signal either a disaffection or just that the former levels of activity were not sustainable in the long term.

Periodicity. While most forums only have weekly periods with activity decreasing during the weekends, gameofthrones has two different periods: the inter-season period, where no new episodes are broadcasted and the levels of activity do not change significantly, and the intra-season periods, where the broadcasting of every episode generates a new peak. As a curiosity, we noted the height of a peak is often proportional to the positive reception of the episode. For instance, the most popular episode of the third season is, according to the ratings in IMDb, the ninth -often known as the Red Wedding. It was broadcasted on June 2, 2013 and corresponds, indeed, to the highest peak of that season.

Spontaneous peaks. Forums can have spontaneous peaks often related to an external event. In france, the two main peaks correspond to the two terrorist attacks in 2015. In podemos, the highest peak corresponds to the foundational congress of the party. In MachineLearning, the first peak (May 2014) was due to an AMA session (Ask me anything) with Yann LeCun and the second one (April 2015) corresponds to an AMA with Andrew Ng.

Moreover, a visual analysis of forum thread lengths from Figure 2.2 shows that peaks tend to be generated by longer threads. This is because when there is some external france gameofthrones MachineLearning podemos TwoXChromosomes 2 0 1 2 -1 -0 2 0 1 -2 -0 1 2 1 3 -0 1 -0 1 2 0 1 3 -0 2 -0 1 2 0 1 3 -0 3 -0 1 2 0 1 3 -0 4 -0 1 2 0 1 3 -0 5 -0 1 2 0 1 3 -0 6 -0 1 2 0 1 3 -0 7 -0 1 2 0 1 3 -0 8 -0 1 2 0 1 3 -0 9 -0 1 2 0 1 3 -1 0 -0 1 2 0 1 3 -1 1 -0 1 2 0 1 3 -1 2 -0 1 2 0 1 4 -0 1 -0 1 2 0 1 4 -0 2 -0 1 2 0 1 4 -0 3 -0 1 2 0 1 4 -0 4 -0 1 2 0 1 4 -0 5 -0 1 2 0 1 4 -0 6 -0 1 2 0 1 4 -0 7 -0 1 2 0 1 4 -0 8 -0 1 2 0 1 4 -0 9 -0 1 2 0 1 4 -1 0 -0 1 2 0 1 4 -1 1 -0 1 2 0 1 4 -1 2 -0 1 2 0 1 5 -0 1 -0 1 2 0 1 5 -0 2 -0 1 2 0 1 5 -0 3 -0 1 2 0 1 5 -0 4 -0 1 2 0 1 5 -0 5 -0 1 2 0 1 5 -0 6 -0 1 2 0 1 5 -0 7 -0 1 2 0 1 5 -0 8 -0 1 2 0 1 5 -0 9 -0 1 2 0 1 5 -1 0 -0 1 2 0 1 5 -1 1 -0 1 2 0 1 5 -1 2 -0 1 2 0 1 6 -0 1 -0 1 2 0 1 6 -0 2 -0 1 2 0 1 6 -0 3 -0 1 2 0 1 6 -0 4 -0 1 2 0 1 6 -0 5 -0 1 2 0 1 6 -0 6 -0 1 2 0 1 6 -0 7 -0 1 2 0 1 6 -0 8 -0 1 event relevant to the community, the discussion around it is centralized in a few long threads.

Newbies versus oldies

How many users join the community every month? We can think of a forum as a sort of biological community where individuals are born, live and die. From the point of view of the researcher who wants to extract types of behaviors, the longer individuals live, the easiest for any algorithm it will be to detect some patterns. Put the other way around, if all individuals posted only once, it would be harder to learn from them and especially to make a significant classification of individuals in roles. Besides, even if we ignore the minimal quantitative conditions for a community to exist, it seems obvious that it needs more than one participation per individual. In order to analyze how stable the communities are in terms of population, let us first define birth and age: • Birth (or join): a birth is the event where a user participates for the very first time in a forum. A high rate of births is an indicator of the interest of the forum towards non-users.

• Age: the age of a user at time t is the time between t and its date of birth.

For a given period, we call newbies, or new users, those users that are born in that period and oldies, or old users, those that were already born before. Figure 2.3 shows the number of users that are born every month. Interestingly, peaks in births are strongly related to peaks in the total number of posts-we will see later that newborns are not the ones who cause the peak in posts.

Who is responsible for most of the content? Despite being a minority, old users are responsible, at least, for 75% of the posts every month (Figure 2.4). podemos and france are the most extreme cases, where old users account for almost the totality of posts. 2 0 1 -2 -0 1 2 1 3 -0 1 -0 1 2 0 1 3 -0 2 -0 1 2 0 1 3 -0 3 -0 1 2 0 1 3 -0 4 -0 1 2 0 1 3 -0 5 -0 1 2 0 1 3 -0 6 -0 1 2 0 1 3 -0 7 -0 1 2 0 1 3 -0 8 -0 1 2 0 1 3 -0 9 -0 1 2 0 1 3 -1 0 -0 1 2 0 1 3 -1 1 -0 1 2 0 1 3 -1 2 -0 1 2 0 1 4 -0 1 -0 1 2 0 1 4 -0 2 -0 1 2 0 1 4 -0 3 -0 1 2 0 1 4 -0 4 -0 1 2 0 1 4 -0 5 -0 1 2 0 1 4 -0 6 -0 1 2 0 1 4 -0 7 -0 1 2 0 1 4 -0 8 -0 1 2 0 1 4 -0 9 -0 1 2 0 1 4 -1 0 -0 1 2 0 1 4 -1 1 -0 1 2 0 1 4 -1 2 -0 1 2 0 1 5 -0 1 -0 1 2 0 1 5 -0 2 -0 1 2 0 1 5 -0 3 -0 1 2 0 1 5 -0 4 -0 1 2 0 1 5 -0 5 -0 1 2 0 1 5 -0 6 -0 1 2 0 1 5 -0 7 -0 1 2 0 1 5 -0 8 -0 1 2 0 1 5 -0 9 -0 1 2 0 1 5 -1 0 -0 1 2 0 1 5 -1 1 -0 1 2 0 1 5 -1 2 -0 1 2 0 1 6 -0 1 -0 1 2 0 1 6 -0 2 -0 1 2 0 1 6 -0 3 -0 1 2 0 1 6 -0 4 -0 1 2 0 1 6 -0 5 -0 1 2 0 1 6 -0 6 -0 1 2 0 1 6 -0 7 -0 1 2 0 1 6 -0 8 -0 1 date births (new users)

Figure 2.3 Births by day. Dotted lines are users that had already written before (oldies). Birth peaks are very related to peaks in number of posts.

The age distribution of posters shows a different pattern from forum to forum. Figure 2.5 shows the age distribution of the users who post each month. In podemos, the mean age increases almost linearly with time, meaning that the population is getting older without many new users joining the community. The population of gameofthrones gets older during the season break, but every time a new season begins, with the activity peaks, they enjoy a baby-boom that drastically decreases the median age. france is very stable; after the two terrorist attacks, a lot of new users participated in the discussion and then abandoned the forum, decreasing the mean age only during that month. machine learning and TwoXChromosomes enjoy the participations of older members (outliers in the plot) while new participants keep joining the forum, keeping the mean age almost constant.

2 0 1 2 -1 2 2 0 1 3 -0 1 2 0 1 3 -0 2 2 0 1 3 -0 3 2 0 1 3 -0 4 2 0 1 3 -0 5 2 0 1 3 -0 6 2 0 1 3 -0 7 2 0 1 3 -0 8 2 0 1 3 -0 9 2 0 1 3 -1 0 2 0 1 3 -1 1 2 0 1 3 -1 2 2 0 1 4 -0 1 2 0 1 4 -0 2 2 0 1 4 -0 3 2 0 1 4 -0 4 2 0 1 4 -0 5 2 0 1 4 -0 6 2 0 1 4 -0 7 2 0 1 4 -0 8 2 0 1 4 -0 9 2 0 1 4 -1 0 2 0 1 4 -1 1 2 0 1 4 -1 2 2 0 1 5 -0 1 2 0 1 5 -0 2 2 0 1 5 -0 3 2 0 1 5 -0 4 2 0 1 5 -0 5 2 0 1 5 -0 6 2 0 1 5 -0 7 2 0 1 5 -0 8 2 0 1 5 -0 9 2 0 1 5 -1 0 2 0 1 5 -1 1 2 0 1 5 -1 2 2 0 1 6 -0 1 2 0 1 6 -0 2 2 0 1 6 -0 3 2 0 1 6 -0 4 2 0 1 6 -0 5 2 0 1 6 -

User dynamics

Posting

How big are inequalities in posting activity? As commonly observed in social networks, a minority of users creates most of the content. The number of posts per user are much closer to Log-normal (centered at 1 post) than to Power Law distributions, and in some cases, like france, they might be better fitted by slightly different distributions (Figure 2.6). Very few users have written more than 100 posts (Table 2.2). Though this is not surprising, this will make it very difficult to learn behavioral patterns from most users.

Lifespans

How long do users stay in the forums? We define as lifespan the number of days between the first and the last post of the user. Figure 2.7 shows that most users are france gameofthrones MachineLearning podemos TwoXChromosomes 2 0 2 -1 1 2 1 2 -1 2 2 0 1 3 -0 1 2 0 1 3 -0 2 2 0 1 3 -0 3 2 0 1 3 -0 4 2 0 1 3 -0 5 2 0 1 3 -0 6 2 0 1 3 -0 7 2 0 1 3 -0 8 2 0 1 3 -0 9 2 0 1 3 -1 0 2 0 1 3 -1 1 2 0 1 3 -1 2 2 0 1 4 -0 1 2 0 1 4 -0 2 2 0 1 4 -0 3 2 0 1 4 -0 4 2 0 1 4 -0 5 2 0 1 4 -0 6 2 0 1 4 -0 7 2 0 1 4 -0 8 2 0 1 4 -0 9 2 0 1 4 -1 0 2 0 1 4 -1 1 2 0 1 4 -1 2 2 0 1 5 -0 1 2 0 1 5 -0 2 2 0 1 5 -0 3 2 0 1 5 -0 4 2 0 1 5 -0 5 2 0 1 5 -0 6 2 0 1 5 -0 7 2 0 1 5 -0 8 2 0 1 5 -0 9 2 0 1 5 -1 0 2 0 1 5 -1 1 2 0 1 5 -1 2 2 0 1 6 -0 1 2 0 1 6 -0 2 2 0 1 6 -0 3 2 0 1 6 -0 4 2 0 1 6 -0 5 2 0 1 6 -0 6 2 0 1 6 -0 7 date age (months) casual participants, posting once and then abandoning the forum forever (they may also become silent readers, which is known as lurking). Only around 25% of users live more than a year. Lifespans have no important differences between forums, except for gameofthrones, where we can observe the fact that every year a new cohort joins the forum.

Communities

How big are user communities? Given a graph, a community is a set of vertices sharing with a high density of links between them and with sparser connectivity with the other communities. We consider communities in the coparticipation graph, where a link between two users indicates at least one coparticipation in the same thread. In the extreme case where we the graph is made of dense communities with few edges between communities (high modularity), it would mean that the forum is actually a collection 10 -2 10 1 10 3 10 5 10 1 10 3 10 5 10 1 10 3 10 5 10 1 10 3 10 5 10 1 10 3 10 5 posts ccdf of subforums with their own community of users. The modularity of a partition is a scalar value between -1 and 1 that measures the density of links inside communities as compared to links between communities.

It seems reasonable to think that the denser a community is, the easier behaviors and-any cultural artifact such as norms, writing style and so on-are propagated between its members.

We build a coparticipation graph for each month and detect its communities with the Louvain algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. Figure 2.8(a) shows the relative sizes of the top five communities. In france and podemos, the five biggest communities always contain nearly all the users. On the other hand, the five biggest communities in MachineLearning usually contain just a bit more than a half of the users. The modularity (Figure 2.8(b)) shows, indeed, that MachineLearning is the most modular forum. This suggests that MachineLearning has more subtopics and that users tend to concentrate on one or another topic according to their personal (maybe professional) profile and their interests.

Lastly, Figure 2.8(c) shows the community sizes in the aggregated coparticipations graph -a graph where we include all the coparticipations regardless of their month. The largest 10 communities for all three forums have more than 1000 members. In Ma- chineLearning, the size of the largest communities is actually more equally distributed.

Conversation dynamics

Thread size

How large are threads? The distribution of thread sizes may be affected by factors such as the type of forum and the user interface. Nevertheless, most forums share common traits regarding thread sizes such as a high probability of small threads and a long tail of long threads. In [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF], the authors report different distributions between Wikipedia and some news-oriented forums such as Slashdot. While Slashdot showed a distribution with some scale, Wikipedia has a scale-free distribution. Even if Reddit is more similar to a news-oriented forum like Slashdot, the length distributions of analyzed Reddit forums are more similar to Wikipedia. Yet, there distributions are more similar to Log-normals (Figure 2.9).

podemos 2 0 1 2 -1 1 2 0 1 2 -1 2 2 0 1 3 -0 1 2 0 1 3 -0 2 2 0 1 3 -0 3 2 0 1 3 -0 2 0 3 -5 2 1 3 -0 6 2 0 1 3 -0 7 2 0 1 3 -0 8 2 0 1 3 -0 9 2 0 1 3 -1 0 2 0 1 3 -1 1 2 0 1 3 -1 2 2 0 1 4 -0 1 2 0 1 4 -0 2 2 0 1 4 -0 3 2 0 1 4 -0 4 2 0 1 4 -0 5 2 0 1 4 -0 6 2 0 1 4 -0 7 2 0 1 4 -0 8 2 0 1 4 -0 9 2 0 1 4 -1 0 2 0 1 4 -1 1 2 0 1 4 -1 2 2 0 1 5 -0 1 2 0 1 5 -0 2 2 0 1 5 -0 3 2 0 1 5 -0 4 2 0 1 5 -0 5 2 0 1 5 -0 6 2 0 1 5 -0 7 2 0 1 5 -0 8 2 0 1 5 -0 9 2 0 1 5 -1 0 2 0 1 5 -1 1 2 0 1 5 -1 2 2 0 1 6 -0 1 2 0 1 6 -0 2 2 0 1 6 -0 3 2 0 1 6 -0 4 2 0 1 6 -0 5 2 0 1 6 -0 6 2 0 1 6 -0 7 date users (
2 0 1 2 -1 2 2 0 1 3 -0 1 2 0 1 3 -0 2 2 0 1 3 -0 3 2 0 1 3 -0 4 2 0 1 3 -5 2 1 -0 6 2 0 1 3 -0 7 2 0 1 3 -0 8 2 0 1 3 -0 9 2 0 1 3 -1 0 2 0 1 3 -1 1 2 0 1 3 -1 2 2 0 1 4 -0 1 2 0 1 4 -0 2 2 0 1 4 -0 3 2 0 1 4 -0 4 2 0 1 4 -0 5 2 0 1 4 -0 6 2 0 1 4 -0 7 2 0 1 4 -0 8 2 0 1 4 -0 9 2 0 1 4 -1 0 2 0 1 4 -1 1 2 0 1 4 -1 2 2 0 1 5 -0 1 2 0 1 5 -0 2 2 0 1 5 -0 3 2 0 1 5 -0 4 2 0 1 5 -0 5 2 0 1 5 -0 6 2 0 1 5 -0 7 2 0 1 5 -0 8 2 0 1 5 -0 9 2 0 1 5 -1 0 2 0 1 5 -1 1 2 0 1 5 -1 2 2 0 1 6 -0 1 2 0 1 6 -0 2 2 0 1 6 -0 3 2 0 1 6 -0 4 2 0 1 6 -0 5 2

Thread duration

How long do conversations last? Users in a forum have many threads that they can join, and new threads are created every day. Thus, most threads grow during a first period, and this growth stops some time later. We illustrate this in Figure 2.10 where we plot the time between each new post and the start of the thread (time to the root). Only around 15% of posts arrive in the first hour. The main growth of thread is after the first hour and during the first day, when most posts arrive. Almost no posts are written after the first day.

Motifs of interaction in threads

What are the dominant micro-structures of the threads? A triad census counts how many times each of the 16 triads appear in a graph. In this section we show the triad census using the interaction graph and the tree graph of a thread. We will see that triads in interaction graph are ambiguous while in the tree graph there are also two possible triads. This will actually motivate the extension of triads in trees that we propose in Chapter 3.

Triads in interaction graphs. For every thread, we build an interaction graph (recall Figure 1.1) and we compute its triad census. Figure 2.11 shows the sum of census for each month. Although the relative dominance of the triads is different among the forums, it is very constant for each forum. That means that each forum has a different type of conversation and that the type of conversation in a forum does not change much.

In general, we see a dominance of the in-star (021U) and the dyad (012), which is very likely due to the root posts that attract single or multiple replies. The triad 111D is as frequent as the dyad in MachineLearning and podemos. Chains (021C) are specially important in MachineLearning Unfortunately, the interpretation of triads in the interactions graph is ambiguous. We do not know, for instance, if a vertex is in a lot of in-star because the user tends to get replies from different people or because he got replies from different people in one post.

Triads in tree graphs. Unlike triads in the interactions graph, triads over the tree graphs are unambiguous. There are four possible triads in a tree: the empty triad (003), the directed edge (012) the in-star (021U), and the chain (021C). The empty triad is not interesting and the directed edge is trivial in a tree. Thus, we focus on the in-star and the chain. To know how significant the frequency of a triad is, we need to compare 2 0 1 2 1 2 2 0 1 3 0 1 2 0 1 3 0 2 2 0 1 3 0 3 2 0 1 3 0 4 2 0 1 3 0 5 2 0 1 3 0 6 2 0 1 3 0 7 2 0 1 3 0 8 2 0 1 3 0 9 2 0 1 3 1 0 2 0 1 3 1 1 2 0 1 3 1 2 2 0 1 4 0 1 2 0 1 4 0 2 2 0 1 4 0 3 2 0 1 4 0 4 2 0 1 4 0 5 2 0 1 4 0 6 2 0 1 4 0 7 2 0 1 4 0 8 2 0 1 4 0 9 2 0 1 4 1 0 2 0 1 4 1 1 2 0 1 4 1 2 2 0 1 5 0 1 2 0 1 5 0 2 2 0 1 5 0 3 2 0 1 5 0 4 2 0 1 5 0 5 2 0 1 5 0 6 2 0 1 5 0 7 2 0 1 5 0 8 2 0 1 5 0 9 2 0 1 5 1 0 2 0 1 5 1 1 2 0 1 5 1 2 2 0 1 it to its frequency in a null model. Our null model is a random tree that grows by new vertices choosing a random parent among the existing vertices; this is actually the most entropic way of building a tree (assuming that the tree has a fixed number of vertices that are added one by one).

We compute the z-score of a triad in a tree graph g of size |V (g)| as follows. With our null model, we generate 100 random trees of size |V (g)|. Let f g be the frequency of the triad in g. Let µ r and σ r be the mean and the standard deviation of that triad in the set of random trees. The z-score is

z = f g -µ r σ r (2.1)
Triads with z-score near zero are not relevant because they have the same frequency as in random graphs. On the other hand, triads with higher (or lower) z-scores are more (or less) frequent than in random graphs, which means that the null model cannot 2 0 1 2 -1 2 2 0 1 3 -0 1 2 0 1 3 -0 2 2 0 1 3 -0 3 2 0 1 3 -0 4 2 0 1 3 -0 5 2 0 1 3 -0 6 2 0 1 3 -0 7 2 0 1 3 -0 8 2 0 1 3 -0 9 2 0 1 3 -1 0 2 0 1 3 -1 1 2 0 1 3 -1 2 2 0 1 4 -0 1 2 0 1 4 -0 2 2 0 1 4 -0 3 2 0 1 4 -0 4 2 0 1 4 -0 5 2 0 1 4 -0 6 2 0 1 4 -0 7 2 0 1 4 -0 8 2 0 1 4 -0 9 2 0 1 4 -1 0 2 0 1 4 -1 1 2 0 1 4 -1 2 2 0 1 5 -0 1 2 0 1 5 -0 2 2 0 1 5 -0 3 2 0 1 5 -0 4 2 0 1 5 -0 5 2 0 1 5 -0 6 2 0 1 5 -0 7 2 0 1 5 -0 8 2 0 1 5 -0 9 2 0 1 5 -1 0 2 0 1 5 -1 1 2 0 1 5 -1 2 2 0 1 6 -0 1 2 0 1 6

- 0 2 0 1 - 3 0 6 - 0 4 2 0 1 6 - 0 5 2 0 1 6 - 0 6 date mean z-score 021U 021C Figure 2
.12 Triads motifs in the tree graphs. z-score with respect to the expected frequency in a random tree where all posts have the same probability to be chosen as parent.

justify their high (or low) frequency. Figure 2.12 shows the evolution of the triad census in our forums. The in-star is usually higher than in the random graphs, especially in the activity peaks with long threads. That means that long threads are made of posts that attract many replies rather than long chains of posts. In other words, long threads are wide rather than deep. MachineLearning and france have the slowest frequency of in-stars.

When compared to the original set of 16 triads, a set of two triads looks like a very limited tool to analyze conversational structures. We will come back to this point in Chapter 3, where we will attempt to classify users by the discussions where they participate -the motifs where they appear.

Summary

In this chapter, we have introduced our datasets and a descriptive analysis to understand some general characteristics of the forums under study. Some of the most relevant findings are:

Forums: In the short term, forums are very regular regarding the number of posts per day. Yet, they often have increasing or decreasing long-term tendencies that may be related to the health of the forum. A decreasing tendency in podemos, for example, is also linked to a decreasing in the number of users, which signals that users lost their interest in the forum.

External events related to the topic of a forum create peaks in the number postsconcentrated in a few threads-as well as the number of users. Some external triggers that can be observed in our datasets are the two terrorist attacks in France in 2015 (January and November), the broadcasting of a TV show (gameofthrones) or even a popular episode, the initial congress of a political party (podemos) or Ask me anything sessions where some celebrity is invited to answer users questions (MachineLearning).

This activity peaks also attracts lots of new users. In general, and despite being a majority, new users create less than 25% of the content. All forums have a core of users that have an ongoing presence and make the most of the content, and a much bigger periphery of users who only participate once and then just lurk or abandon the forum.

Users: As commonly observed in social networks, a minority of users creates most of the content. The distribution of number of posts per user is better approximated by Log-normal distribution centered at 1 rather than by a power law. The number of users with more than 100 posts is less than 5000 for all the forums in our dataset. Regarding lifespan, the most frequent case is a user that participates one day or two and then leaves the forum.

Conversations: Conversation lengths do not follow power laws either, but rather Log-normal distributions centered at 1. Threads receive most of the comments during the first day, probably due to the competition between threads and the daily creation of new ones. Structurally, thread conversations have a strong tendency towards the in-star, meaning that conversations are more dominated by stars (i.e.: replies to the root) than by cascades (chained replies).

In the beginning, we considered roles as community-based. A role would be defined by the community and not by the individual, and therefore a new individual would just fill in a role after some initial integration. We think this may happen for closer communities or task-oriented communities such as Wikipedia. However, the dimensions of the forums make them more similar to cities than task-oriented communities, and the role study needs to take another approach. The fact that there is only a small elite of active users makes the community-based approach especially hard. The approach that we take in the following chapters is to look at a role from the point of view of the individual behavior.

Role detection based on conversation structures

It is impossible to speak in such a way that you cannot be misunderstood

Karl Popper

In this chapter, we present three definitions of neighborhood in conversation trees and a simple algorithm to extract post neighborhoods in a forum. We describe users by their number of participations in each type of neighborhood (motif) and we find clusters of users that tend to occupy the same position in the same type of conversation. U ser behavior in online forums is often analyzed through metrics such as the number of posts they write, the number of threads, the number of replies per post or their centrality in the social graph. These features allow us to detect some important roles. A celebrity, for instance, defined as a prolific poster who spends a great deal of time and energy contributing to their community and whom everybody knows, can be discovered by their high in-degree and out-degree-among other features [START_REF] Forestier | Extracting celebrities from online discussions[END_REF]. This way of summarizing users activity by a vector of metrics is, however, unable to capture user behaviors at a conversational level. Unfortunately, there is a lack of tools to analyze We represent a thread as a tree of posts where each post has an author. Threads are usually made of a variety of local conversations between different users; as shown in Figure 3.1, this diversity is reflected in the tree representations where some parts may have long branches (e.g.: debates or flame wars) while others may have vertices with lots of replies. (e.g.: a controversial post that gets the consensual disapproval from the other users or a good question that gets many answers). The neighborhood of a post is an induced subgraph that contains the local part of the tree surrounding the post. Thus, the neighborhood captures the structure of the local conversation where the post is embedded. As we will see in this chapter, there is no "natural" definition of neighborhood in the context of conversation trees. We will propose three alternative definitions, and we will analyze their strengths and weaknesses.

We recall that our goal is to detect user roles. In this chapter, we propose the following definition of role:

Definition Two users have the same role if they tend to participate in the same positions of the same type of neighborhoods (motif).

Hence, We will cluster users according to the type of neighborhood where they tend to appear. We will introduce and analyze three new definitions of neighborhoods that we name radius-based, order-based and time-based neighborhoods. Our strategy to detect different types of conversationalists is as follows: first, we extract the neighborhood of each user's post; second, we cluster users according to their tendency to appear in each type of neighborhood.

Discussion trees

We represent a discussion thread by a tree graph G = (V, E) where V is a set of n vertices representing the posts (also called messages or comments) and E is a set of n -1 directed edges that tell us which posts replied to which post. Vertices have two attributes namely time and author. If for two given vertices v i , v j there exists an edge e = (v i , v j ) ∈ E then v j is called the parent of v i , denoted as p(v i ) = v j . The root of the tree is the only vertex with no parent, and corresponds to the post that starts the discussion. We say that two distinct vertices v i and v k are siblings if and only if p(v i ) = p(v k ). A vertex v l is an ancestor of a vertex v i and v i is descendant of v l if and only if v l is in the path from v i to the root. A leaf is a vertex with no descendants (a post with no replies). A branch is the path between a leaf and the root.

Methodology

To cluster users based on the structure of conversations where they participate, we follow two steps. First, a neighborhood extraction step where we detect the structure of the conversation around each post. Second, a clustering where we find groups of users that tend to participate (i.e.: their posts tend to be embedded) in the same type of neighborhood.

For the experiments, we analyze the 1,000 most active users of france, podemos and gameofthrones. We take a sample of 100 of posts for each user.

Neighborhood extraction

The first step consists on detecting the type of neighborhood that surrounds each post. We will call motif or neighborhood motif the set of neighborhoods that (after the extraction process) are isomorphic to each other. The general algorithm of neighborhood extraction (or motif extraction) is as follows: we initialize an empty dictionary to store pairs of motif descriptions and numerical identifiers. We will also initialize a table to where we will note, for each post, the identifier of its neighborhood motif. For every post, we extract its neighborhood and check whether it is isomorphic to any of the motifs that have been previously found. If there is a coincidence, we update the table by writing, for that post, the identifier of its neighborhood motif. Else, we add a new entry in the dictionary with the new motif and a new identifier, and then we update the table of posts. In some cases, a user will be seen in the same neighborhood more than once. It will happen, for instance, in a thread of length two where all posts are written by the same user. To avoid counting the user in the same neighborhood twice, we compute the hash of each neighborhood and remove duplicates at the end. The algorithm is detailed in Algorithm 1. The slowest part is the search in the dictionary since we have to check whether the current neighborhood is isomorphic to any of the motifs. Specifically, the complexity of the algorithm is O(nm) where n is the number of posts, and m is the number of different motifs. In practice, we can reduce the number of operations if, when looking for an isomorphic motif in the dictionary, we do it following their frequency.

Algorithm 1: Neighborhood extraction Data: Set of trees G = {G 1 , .., G n } Result: Table posts; Dictionary motifs. 1 Dictionary motifs ← ∅; 2 Table post motif ← ∅; 3 for G ∈ G do 4 for v ∈ G do # Extract post neighborhood 5 N v ← extract neighborhood(v); 6 N ′ v ← color neighborhood(N v ); 7 N ′′ v ← prune neighborhood(N ′ v ); 8 hn ← hash(N v ); # Compare to motifs in dictionary 9 for i ∈ 1, ...,size(motifs) do 10 if is isomorphic(N ′′ v , motifs[i]) then 11 post motif[v] ← (i,
The function extract neighborhood correspond to any of the three neighborhood definitions that we will describe in sections 3.3, 3.4 and 3.5. The functions color neighborhood and prune neighborhood will be described in Section 3.3.

Clustering

In the first step, we obtained the motif associated to the neighborhood that surrounds each post (Algorithm 1). Now we create, for each user u, a feature vector of counts n u = (n 1 , ..., n m ) where m is the number of motifs and n i is the number of times that a post written by u has a neighborhood of class i. We normalize each feature vector so that the sum of its components is one, hence obtaining a discrete probability distribution. We compute the distance between two users as the Pearson correlation of their vectors, and finally, we apply a hierarchical clustering over this distance matrix1 .

Feature selection. After normalizing the feature vectors-obtaining probability vectors-, we remove some of the features as follows. First, we sort the vector entries by median probability: we compute the medians of the probability vectors n u over all the users, and we sort the entries of the feature vectors so that the first entry has the highest median-over all users-and the last entry has the lowest median. We look for an elbow in the plot -it usually lays before the 20th motif. Then we check the user outliers for each motif that falls beyond the elbow. Outliers indicate that a motif might still be important for some users. Thus, if the number of user outliers is less than 10% of users, we mark the motif as irrelevant-that is intended to keep those features that might be relevant for more than 10% of users. Finally, we merge all the irrelevant motifs into a new category others so that the feature vectors are still probabilities that sum up to one. Outliers are detected using Tukey's Method: they are defined as those who lay below Q 1 -1.5IQR or above Q 3 + 1.5IQR, where Q 1 and Q 3 are the first and the third quartiles, and IQR (that stands for Interquartile Range) is IQR = Q 3 -Q 1 . We will show the elbow and the outliers for every experiment (see, for instance, Figure 3.2(b))

Number of clusters. Since our main goal is to compare different definitions of neighborhood in conversation trees, we apply the same simple criteria to all the cases: for each type of neighborhood and given the dendrogram of the hierarchical clustering obtained in our forums, we cut all dendrograms at different cutting distances h and we choose the distance that gives a more meaningful-explainable-separation. Because we have the same number of users with the same number of posts for each of the forums, fixing h allows comparing the number-and the content-of clusters that we find in each forum using the same levels of granularity.

When we will talk about dictionaries of features, we will say that the most popular features are those with higher medians. In the context of each cluster, we will say that the most dominant triads are those with higher means.

Radius-based neighborhoods

Our first type of neighborhood is based on the classical definition of neighborhood in graph theory:

Definition Given a tree graph G, the radius-based neighborhood with radius r of post v ∈ G, denoted as N v (r), is the induced graph of G that contains all vertices at distance equal or less than r from post v.

According to this definition, the number of possible neighborhoods with a radius r is infinite. This poses a problem when trying to categorize conversations since many conversations, while structurally different, can be considered semantically similar (e.g.: we might not want to put in different categories two structures representing, respectively, a post with 50 replies and another with 40). One way of fixing this is to prune the neighborhood to remove those parts that we consider non-informative.

Besides, two isomorphic neighborhoods may correspond to different types of conversation: the top vertex of an in-stars, for example, may be either a regular post or the root of the thread. While the former might indicate that the post is controversial, the latter is more often related to a good opening question. We will reduce this ambiguity by assigning colors to vertices.

Coloring

Even if the structure contains some important information about the type of conversation, there is still some ambiguity left: two similar neighborhoods can represent very different types of conversation. We can easily reduce this ambiguity by assigning colors to vertices, which allows us to identify some relevant property of the post.

In particular, we assign to each post one of these three colors (see, for instance, Figure 3.2(a)):

• Red : ego post and posts written by the same author as ego. It allows identifying re-entries (when the same author participates several times in the discussion Backstrom et al. ( 2013))

• White: root post. Differentiating the root post from the rest has been proven useful by previous research on online discussions. For instance, some types of users seem to get more replies than others when they initiate a thread [START_REF] Himelboim | Discussion catalysts in online political discussions: Content importers and conversation starters[END_REF]; [START_REF] Lumbreras | Analyse des rôles dans les communautés virtuelles : définitions et premières expérimentations sur IMDb[END_REF]). Also, concerning preferential attachment, root posts usually get more replies than the non-roots [START_REF] Gómez | Modeling the structure and evolution of discussion cascades[END_REF][START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF]).

• Grey: root post if written by the author as ego (i.e.: gray are red-white vertices).

• Black : none of the above.

It is possible to apply other coloring schemes. For instance, we might give a different color to the leafs, or we might color posts according to their content length, or they positive or negative sentiment. To detect discussions between two users, we have also tried giving another color to those posts written by the user to which ego replies. Nonetheless, the more colors we add, the more diverse and large the list of motifs that we will find, which may be an undesirable effect. Hence, we decided to keep only three colors after playing with other schemes.

Pruning

At this point, we can still find structures the only difference of which is that one of them has more leafs hanging from some of the nodes. Thus, we prune every neighborhood by leaving a maximum of two consecutive siblings of the same color and where neither of them has children. The reason of setting the limit to two is that it is the minimum necessary to distinguish between zero, one and more than one consecutive occurrences.

In other words, we consider that the difference between one and zero replies to a post is relevant, but that five and six replies do not make any difference worth being represented. Moreover, this choice encourages smaller structures, which allows the computation of isomorphisms (Section 3.2.1) even in real time.

In the experiments, we will see that some of the found motifs could be merged into the same one since they represent, without much doubt, the same type of conversation. That means that there is still room for a more aggressive pruning. Yet, we have decided to stay with the current pruning in order not to further distort the comparison between neighborhood definitions.

Choice of radius

We have to be careful when choosing a radius. With a small radius r = 1 we cannot include the siblings and grandchildren of the ego post and we will only detect the parent and the children (direct replies). Thus, we will lose structures like ego replies to a post that has more replies or like ego writes a post, someone replies and then ego replies back ; all these structures need a radius r ≥ 2. With larger radius we will find two problems: first, even with the proposed pruning the dictionary of motifs will become larger, and the number of motifs with almost zero frequencies will increase; second, the motifs will be bigger, and this will increase the computational time to check the isomorphisms. As we will see in the experiments, a good middle ground is r = 2, which is the minimum radius necessary to include the grandchildren and the siblings of the ego post.

Results for radius-based neighborhood

We extracted the radius-based neighborhood around each post written by our selected users. We tried radiuses r = 1 and r = 2. For radius r = 1. Figure 3.2 shows the most frequent motifs and their frequency in every forum. Figure 3.4 shows the most frequent motifs for radius two.

Results for r = 1 Dictionaries. We found 28 different motifs in the analyzed forums (Figure 3.2). The motifs dictionary gives us already an interesting perspective of what we can see within each radius. Note that only four of them would be possible without coloring. The most popular triads are replies, replies to root posts and root posts with replies. The more we go into less popular triads, the stranger the patterns that we observe. A common characteristic of the less popular motifs is that they represent conversations where the user replies to themselves. This happens, for instance, when users wish to clarify or extend some point made in their previous post. Beyond the seventh motif, medians are all zero. Hence, our set of selected features is made of the first seven motifs plus those with a high enough number of outliers (10%), which are the 9 and the 11.

Clusters. We collapse the non-selected motifs into the others category (label 0) and look for clusters in the features matrix. The results are shown in Figure 3.3. We name the cluster by their dominant motifs. We denote as (i, j, k) the three most dominant motifs in a cluster. Since the third motif is usually much less dominant than the two first, we merge those clusters that have the first two dominant motifs and we denote the resulting cluster as (i, k, * ). We show a summary in Table 3.1.

• repliers (1,2,*): we find this type of user in all three forums. The activity of the repliers is focused on replying non-root posts. In gameofthrones and france they are the majority group.

• Successful repliers ((2,1,*), (2,3,1)): these are repliers that tend to get replies to their replies. We find them in france and podemos.

• root repliers (3): these are users that tend to reply to root posts and who mostly get no replies. In gameofthrones, this group also reply to non-root posts. In podemos the mean probability of motif 3 for this group is specially high (near 0.5).

• initiators (7): this is a minority group found in france (17 users) and podemos (15 users). These are people that open successful threads -the initiator term was coined in [START_REF] Chan | Decomposing discussion forums using common user roles[END_REF]). Table 3.2 Summary of clusters with radius-based neighborhoods (r=2). Clusters with similar first and second motif, but different third motif, have been collapsed into a same group (the third motif is marked with an asterisk). The question mark corresponds to the others category.

• self-repliers (0): this is a micro cluster (15 users) in podemos whose preferred motifs are the other category. That is, motifs that include a self-reply from the user. The fact that there are a lot of debates in the threads of podemos-sometimes very heated debates, either between supporters or between supporters and trolls-may be the cause of this pattern where a user wants to make their point clear.

Results for r = 2 Dictionary. We found 1269 motifs for r = 2 (Figure 3.4). A good property of this radius is that we detect some interesting motifs that were undetectable with r = 1-to see how a motif with r = 2 would be detected if we applied r = 1 we just have to remove those vertices that are further than two steps from any red vertex. For instance, the most popular motif for r = 2, a reply to a root that has more replies, is non-detectable by r = 1; a neighborhood with r = 1 sees no difference between being the only replier to a root (in a thread that grabbed not attention) or being one among many repliers. A cascade that starts at the root and ends in the ego (motif 9), would be seen by r = 1 as a dyad between the ego and a non-root post. Since these cases are among the most popular motifs, the number of meaningful structures that were being overlooked with r = 1 is not negligible. Nonetheless, the price to pay is a much larger dictionary of motifs.

On the other hand, some motifs that were relevant in r = 1 are now split apart in multiple motifs. Recall, for instance, that a successful root post (motif 7 in r = 1) was the dominant motif in the initiators cluster. Now this motif has been split in multiple sub-cases (see Figure 3.6). The risk of such granularity is that each sub-case has lower probability and they may become insignificant.

Beyond the nineteenth motif, medians are all zero. Hence, our set of selected features is made of the first nineteen motifs plus those with a high enough number of outliers (10%), which are the 21, 31, 35, 37, 39, 40, 46, and 55. Clusters. A consequence of a large dictionary of motifs is that the others category accumulates a lot of the probability mass (see Figure 3.5). Indeed, this feature is the strongest in many clusters -and among the strongest in all of them. We show a summary in Table 3.1.

• root repliers (1,0,*): they are mostly found in france and podemos.

• terminators ((3,7,4), (3,0,7)): these are users that tend to have the last word in a conversation. Their posts are found at the end of chains (consecutive replies). They are found in france and gameofthrones.

• persistent repliers (21,0,1): a small group of users in gameofthrones that tend to give many replies to the root post.

• debaters (0,8,1): debaters are found participating multiple times in the same. The other participant is often the same (A ← B ← A ← B). These are found in podemos. Indeed, reading the content of the posts we have confirmed that they are usually debates. Note that this behavior cannot be detected with radius r = 1.

• initiators (0, 31,37): initiators are still detected in podemos but not in france due to the specialization effect (Figure 3.6).

• others (0,*): users whose dominant motifs are in the other category.

Overall, there are some groups such as the persistents repliers, the terminators that cannot be detected with radius r = 1. Yet the initiators, which is clearly a meaningful group, is not detected in france. Moreover, the other category of motifs is dominant in several clusters, meaning the probability is more spread among the motifs (specialization effect), which makes some patterns to go unnoticed.

Order-based neighborhoods

The previous definition only considers the structural distance to the ego. The closer a post to the ego, the higher its preference to be selected as a neighbor. However, it might be reasonable to also consider time when deciding which posts are neighbors and which posts are not.

There are multiple possibilities to using time to decide what a neighborhood is, although some of them are impractical. We might say, for instance, that the neighborhood is composed of the r posts that are closest in time to the ego. The problem of this is that the closest in time might be far away in the tree -therefore part of another local conversation. We might then say that the neighbors are the r posts that are closest in time and that can reach the ego through a path made by other neighbors. Unfortunately, it happens very often that all the r temporally closest posts are not structurally close as well. In these cases, the ego would be left with no neighbors.

Considering this, we propose a second definition that selects posts first by geodesic distance (to guarantee locality) and then (in the case of a tie) by time distance to the ego. That way we will guarantee the connectivity of the graph. The formal definition is the following: Definition Given a tree graph G with a timestamp annotated in each vertex, the orderbased neighborhood of radius r of vertex v, denoted as denoted as N O v (r), is the subgraph of the r-th closest neighbors (including the ego) where, if a post with timestamp t is included in the subgraph, then all posts with equal distance and less t i are also included.

That is, given r we collect the neighbors of v starting from the adjacent vertices and increase the distance until we fill a neighborhood with r vertices. If, in the last distance, we cannot include every vertex because that would overflow the r limit, we select those that are closest in time to the ego.

One of the strengths of this definition is that, unlike the radius-based neighborhood, the neighborhood size is explicitly upper bounded by r. This will make the post-pruning unnecessary.

Pruning and coloring

Order-based neighborhoods N O v (r) contain at most r vertices and thus they need no post-pruning. Yet, it has some effects that we want to avoid. Imagine a post with many replies. If we extract its order-based neighborhood of r = 3 we may get two of the children (the closest in time) or one child and the parent (if the parent is closer than most children). But we the grandparent of the post will never have an opportunity to enter the neighborhood because there neighborhood will be filled with the parent and children. In the case of cascades, for instance, if the last post of the cascade has many replies, we would systematically ignore the cascade and detect a in-star.

To avoid this we will make our pruning before the neighborhood extraction. That this, we color the tree as in Section 3.3, we prune it as in Section 3.3 and then we extract the order-based neighborhood around the ego. As for the coloring of vertices, we apply the same colors as in the radius-based neighborhoods.

Choice of radius

Similarly to the radius-based neighborhood, the choice of the radius is a compromise between the expressiveness of the motifs and the size of the motifs dictionary. Orderbased motifs with radius r = 2 can only capture dyads (the ego and its parent, or the ego and is son), and thus we rule out this radius. Radius r = 3 can capture the siblings, the grandparents and the grandchildren of the ego -two of them-which might be enough expressiveness whereas keeping the dictionary smaller than radius-based neighborhoods with r = 2.

Results for order-based neighborhood

We repeat the workflow of the experiments in the former section for order-based neighborhoods of radius r = 3.

Dictionary. The dictionary of motifs has a similar size to that of radius-based neighborhoods with of r = 1 (26 motifs) but different content (Figure 3.7). The most popular triads are chains, replies to root posts, posts with replies and root posts with replies. Compared to the radius-based of r = 1, the order-based has no the group of 4vertices motifs that were detected by the radius-based where users reply to themselves. In exchange, it contains popular 3-vertices motifs that were only detected with the neighborhood-based with r = 2. Compared to the radius-based of r = 2, the orderbased does not suffer from the specialization effect (Figure 3.6). Another compelling characteristic of this dictionary is its similarity to the 16-triad list. Indeed, Note this dictionary correspond to the dyad and the two only triads that are possible in trees: the in-start and the chain (see Chapter 1). The novelty here is that they have been colored, giving them the ability to capture more conversational structures.

Beyond the ninth motif, medians are all zero. Hence, our set of selected features is made of the first seven motifs plus those with a high enough number of outliers (10%), which are the 10, 11, 12, 13, 14, 15, 16, 17, 18 and 19. Clusters. Results of the detected clusters are shown in Figure 3.8, and a summary in Table 3.3. We find successful repliers, root repliers, initiators, and terminators. Besides the ability to detect behaviors such as the terminators (undetected in radius-based neighborhood with r = 1), another good property is that the other category is only dominant in one cluster (as happened in radius-based r = 1).

Order-based neighborhoods of r = 2 are able to capture the deep repliers (captured by radius-based of r = 2 but not r = 1) and the initiators in france and podemos (the initiators in france went unnoticed for radius-based of r = 2 due to the specialization effect.)

Time-based neighborhoods

Lastly, we propose a third definition based on time -not just order. To take time explicitly into account, one might set fixed time-based boundaries for the neighborhood and include only those posts whose timestamp t j is at a distance less than τ from the ego post i, i.e.: |t jt i | < τ . However, the pace at which posts are added to the conversation may be very different between conversation threads (and also within a thread) and we have no a priori criteria for a proper choice of τ .

Rather than looking for a fixed time radius, we may instead decide it by looking at changes in the pace how new posts are added to the thread. In statistical analysis, a changepoint in a sequence x 1 , ...x n is a point that comes from a different probability distribution than its precedent values. If sequences are timestamps, they are monotonic increasing. Therefore the changepoints will correspond to sudden pauses in the conversation. In the following, we will differentiate horizontal changepoints, that arise between siblings, from vertical changepoints, that arise within a branch. We say that a sequence posts with timestamps t 1 , ..., t n belong to the same (vertical or horizontal) local dynamic if there is no changepoint t i in the sequence such that 1 < i ≤ n. For the detection of changepoints, we use the PELT algorithm [START_REF] Killick | Optimal detection of changepoints with a linear computational cost[END_REF] 2 . Now we can introduce our new definition: ,4,5,6,10,11,13,14,15,16,18,19}.

Definition Given a tree graph G, the time-based neighborhood of radius r of vertex v, denoted as N T v (r), is the maximal subgraph of the structural neighborhood N v (r) where all the vertices belong to the same vertical and horizontal local dynamic as v.

Note that we still have a radius parameter r to guarantee that the resulting structure remains local even if no changepoint is detected near the post v. This definition can be seen as a radius-based neighborhood with a time-sensitive pruning.

Algorithm 2 extracts time-based neighborhoods of a given post according to the above definition. Since the changepoints only depend on the tree and not on the particular post we analyze, we previously detect the horizontal and vertical changepoints in the tree. In the case of multiple branches with some common posts, we consider that a common post is a vertical changepoint if it is a vertical changepoint in any of the branches. Once we have the changepoints, we can proceed with the algorithm. First, we extract the radius-based neighborhood. The time-based neighborhood will be a subset of the later. Then, we look for horizontal and vertical changepoints, which mark the frontiers of the time-based neighborhood. There are four possible cases:

• A vertical changepoint in the ancestors: If the changepoint is in the path between the post and the root, then the changepoint started the new local dynamic to which the ego post belongs. Thus, we remove the ancestors of the changepoint, but not the changepoint itself.

• A vertical changepoint in the descendants: If the changepoint is a descendant then it started a new different dynamic and therefore we must remove the descendants of the changepoint and the changepoint itself.

• A horizontal changepoint either in the older siblings or the ancestors: If the changepoint is among the older siblings, then it started the horizontal dynamic to which the ego post belongs. Similarly, if the changepoint is among the ancestors, then every older sibling of the changepoint belongs to a previous local dynamic. In both cases, we remove the older siblings of the changepoint but not the changepoint itself.

• A horizontal changepoint elsewhere: In any other case, the horizontal changepoint starts a different local dynamic and therefore we remove its younger siblings and the changepoint.

Any time a vertex is removed we also remove its descendants. N T v (r) is a connected induced subgraph of N v (r). If there are no changepoints in the structural neighborhood, then N T v (r) = N v (r). An example of a time-based neighborhood is given in Figure 3.9. Pruning and coloring are applied as in the radius-based definition.

Choice of radius

Because changepoints are not necessarily close from each other, laying only on the changepoints, or choosing large radiuses would give too large motifs. Thus, we choose a radius r = 2 so that the dictionary is, at most, the size of the radius-based dictionary of r = 2. In this sense, a time-based neighborhood may be seen as a radius-based neighborhood with an extra pruning based on speed changes.

Results for time-based neighborhood

We repeated the workflow of the experiments in the former section. We chose a radius r = 2 so that the dictionary has, at most, the same motifs than a radius-based dictionary with the same radius.

Dictionary. The final dictionary contains 168 motifs, much less than the 1269 for radius-based with r = 2, meaning that changepoints help to considerably reduce the size of neighborhoods (Figure 3.10). Beyond the nineteenth motif, medians are all zero. Hence, our set of selected features is made of the first nineteen motifs plus those with a high enough number of outliers (10%), which are the 21, 31, 36 and 40. 3.4 Summary of clusters with time-based neighborhoods (r=2). Clusters with similar first and second motif, but different third motif, have been collapsed into a same group (the third motif is marked with an asterisk). The question mark corresponds to the others category.

Clusters. Results are shown in Figure 3.11, and a summary in Table 3.4. We detect repliers, root repliers, and terminators and debaters. The debaters, however, are in shorter chains than those found in radius-based with r = 2. The reason is that there is usually a changepoint in the chain. Besides, debaters are not only found in podemos but also in france.

Comparative analysis

In this section, we give an overview of the results for each the neighborhoods.

Radius-based with r = 1 detects repliers, successful repliers, root repliers and initiators. It gives a dictionary of 28 motifs, 7 of which have a median higher than 0. With our feature selection criteria we selected 9 features.

Radius-based with r = 2 detects root repliers, persistent repliers,debaters, initiators and terminators. It gives a dictionary of 1269 motifs, 19 of which have a median higher than 0. With our feature selection criteria we selected 27 features.

Order-based with r = 3 (three vertices) detects successful repliers, initiators and terminators. It gives a dictionary of 26 motifs, 9 of which have a median higher than 0. With our feature selection criteria we selected 14 features.

Time-based with r = 2 detects repliers, root repliers, debaters, and and terminators. It gives a dictionary of 746 motifs, 19 of which have a median higher than 0. With our feature selection criteria we selected 23 features.

It is clear that the radius-based neighborhood with a radius r = 1 misses some interesting structures. It is unable, for instance, to detect users that tend to end conversations. Nonetheless, since it does not suffer from the specialization problem observed in other neighborhoods, the initiators are properly detected.

The main disadvantage of the radius-based neighborhood with a radius r = 2 is its huge dictionary. The consequence of a big dictionary is that the counts, and therefore the probability mass, is too spread and some relevant motifs are actually seen as two different ones (the specialization problem). Since we collapse the motifs with low probability into an other category, we can see that this category is actually dominant is many clusters, which means that the total probability mass in these less frequent motifs is not negligible. In practice, the method does not see the initiators in france. Nevertheless, it is able to detect new types of clusters such as the debaters and the terminators.

The main advantage of the order-based neighborhood with r = 3 is that it keeps a small dictionary. Besides, it sees some clusters that radius-based with r = 1 does not see (terminators). Among the repliers, only successful repliers are detected.

Regarding the time-based neighborhood, proposed as an improvement of the radiusbased with r = 2, it achieved a considerable reduction of the dictionary. However, initiators are even more ignored, even if some motifs that represent initiators have higher popularity in the time-based dictionary.

Given the cost of computing isomorphisms in large dictionaries, the order-based neighborhood seems to us the most practical method to detect conversational structure.

Overall, there are some reasonable arguments to prefer the order-based of r = 2 versus any of the others, namely: (a) a small dictionary (b) with more expressiveness than a radius-based with r = 1. Moreover, we stay in the realm of triads, which are already a common unit of analysis in social networks. Yet some motifs might be merged in order generate a base of relevant motifs where the each motif represents a unique type of conversation.

Summary

The goal of this chapter was to shed some light on what would be a proper method to characterize local conversations in order to detect different types of conversationalists. We have introduced a new approach to describing users behaviors based on the structure of their conversations in the tree representation of discussion threads. Particularly, we have compared three different definitions of neighborhood to capture the structure where a post is embedded: radius-based, order-based and time-based. The choice of the proper neighborhood is not trivial because of a trade-off between expressiveness (i.e.: the variety of structures that a neighborhood definition captures) and sparsity of the dictionary (i.e.: the number of neighborhood classes, or motifs, that have very low frequencies).

To take into account the posts authorship and to differentiate, for instance, between a common reply and a reply to a root post, we have used colors to label posts written by the user under study and the root post. We also apply a pruning strategy to remove redundant parts of the conversations that add no extra information.

Radius-based neighborhoods are extensions of classic neighborhoods in graphs. While neighborhoods of radius r = 1 cannot detect some interesting patterns, the dictionary of motifs for r = 2 grows to more than 1000 motifs, which makes the dictionary too sparse to be useful for clustering and further interpretations. Time-based neighborhoods are built upon radius-based. Once we have the radius-based neighborhood, we apply a pruning in those points of the neighborhood where a sudden decrease in the speed is detected. We have shown that, although this considerably decreases the size of the dictionary, there is no clear improvement in the type of clusters detected.

Order-based neighborhoods are similar to radius based except that it accepts a maximum of r vertices in the neighborhood. First, we add neighbors at distance one, then those at distance two, and so on until we have r neighbors. At each distance, we first add those vertices that are closer to the ego post. Order-based neighborhood with r = 3 give triad motifs, which makes them similar to the classic triads used in social network analysis. Because the reduced size of its dictionary and the type of conversations that it is able to detect, we consider this neighborhood the most promising among all the proposed neighborhoods. Besides, a possible enhancement of the order-based neighborhood is to merge manually -probably under some sociological criteria-those whose difference is not meaningful.

We have shown that the structure of conversation provides novel information that is unveiled by other feature-based methods. We think that the clear cluster structure found in some cases (i.e.: users with a very high preference towards some type of structures) supports this claim.

Also, other variations of these neighborhoods may also be studied to analyze different phenomena. For instance, we might take only those neighbors who are descendants of the ego post; such kind of neighborhood may be used to classify users with respect to the reaction they trigger in the discussion. The inverse technique, that is, take all the neighbors that are not descendants of the ego, may help to understand the kind of discussion that a user tends to be attracted to. This might be useful for posts recommendations or even to improve current generative models that try to reproduce the way how a thread grows [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF]; [START_REF] Kumar | Dynamics of Conversations[END_REF].

Language analysis might also be included in the definition of neighborhood. For instance, we might detect the sentiment of each post and add this information to the motif using a larger color code (e.g.: positive/negative sentiment root, positive/negative sentiment ego, and so on). Nonetheless, this will likely increase the dictionary of motifs, so it probably should be combined with a more aggressive pruning or merging strategies.

Role detection based on thread growth models

This appraisal of the hypothesis relies solely upon deductive consequences (predictions) which may be drawn from the hypothesis: There is no need even to mention "induction".

Karl Popper

In this chapter, we propose a method to cluster users based on behavioral functions. A behavioral function is a probability distribution that models the replying behavior of users. We infer latent groups of users where each group has different parameters of the behavioral function. I magine that we observe the behaviors of individuals in a given population. If we count how many times each person has engaged in each behavior, we might cluster them and find groups of people that behave in a similar way. We might find, for instance, the group of firefighters. Their observed behaviors are eating, sleeping, exercising, firefighting and rescuing cats from trees. However, this cluster is purely descriptive: if we see the firefighter in a given context such as a fire or next to a cat on top of a tree, the cluster will not be able to predict which action the firefighter will choose, either saving the cat or extinguishing the fire.

In the previous chapter, we proposed detecting roles based on the structure of the conversations where users participate. This method may be a good complement to other feature-based method since it considers a new dimension of user behavior: conversations. Nonetheless, this approach is purely descriptive. There is still a missing link that connects a user's observed behavior to some behavioral function that models why the user has chosen that action. We conceptualize a behavioral function as a probability distribution over the space of all possible behaviors in a given context. We assume that there exists a finite repertoire of behavioral functions and that all the observed behaviors of a user are drawn from one of these functions. We say that users who share the same behavioral function hold the same role. This, our definition of role in this chapter is:

Definition Two users have the same role if they tend share the same (parameters of a) behavioral function.

In this chapter we set three main goals: (a) proposing a behavioral function for discussion threads, (b) finding groups of users with the same behavioral function (the same parameters), and (c) testing whether these behavioral functions have predictive power -if they can predict the behavior of a user in a new context.

We will use random graph models as the basis for our behavioral functions. In particular, we will focus our attention on growth models. Growth models are random generators of graphs that try to mimic the growing mechanism of a network through stochastic processes governed by a set of parameters. Formally, a growth model defines a probability distribution that quantifies the probability of an existing vertex i of being chosen as the parent for a new vertex x t :

p(x t ∼ i|G t-1 ; θ) (4.1)
where G t-1 is the state of the graph before x t is attached, and θ are the parameters of the model -the specification of this probability distribution depends on what we think is a reasonable assumption about the growth process. These models may be seen as behavioral functions since they model the way users choose a post to reply. The repertoire of possible behaviors is then a set of parameters θ 1 , ...θ K , and the above probability will therefore depend on the θ associated to the author of the post x i -the author's role. The structure of this chapter is as follows. In Section 4.1, we present the different growth models that can be applied to tree graphs. In Section 4.2, we address our goal (a) by an adaptation of one of the models to allow that posts written by different users have different growth parameters θ. The idea is very simple and consists in estimating, by Expectation-Maximization, clusters of users with their own parameters. In Section 4.3, we address our goals (b) and (c) by finding clusters of users and their parameters in a Reddit dataset, and by testing whether our model is a better predictor in a test set.

Network Growth models

Random graph models are stochastic generators of graphs that try to reproduce the properties of some real-world network. A good random graph reproduces many relevant properties with few assumptions and a small number of parameters. If the generated graphs and the real-world graphs share some relevant properties, then the proposed growth mechanism might be a reasonable approximation of the growth laws under which the real-world graphs evolve [START_REF] Kolaczyk | Statistical Analysis of Network Data: Methods and Models[END_REF].

Following [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF], we represent a discussion tree at time step t as a vector of parents π (1:(t-1)) = (π 1 , ..., π t-1 ) where π n is the parent of the post written at the time-step n. Note that this representation does not loose any structural information (see Figure 4.1). With this notation, Equation 4.1 can be re-expressed as:

p(π t = i|π 1:(t-1) , θ) (4.2)
Our growing graph is therefore a tree that starts its growing process with a first vertex (root post) written at t = 0 that triggers a conversation. The parent of the next post, written at t = 1, will always be the root (π 1 = 1). Then, at each time-step t a post is added to the tree creating a new vertex (a reply) to an older post i (π t = i). One might hypothesize that users tend to reply to popular posts (preferential attachment) or that they prefer recent posts, or well-written posts, or that all posts have indeed the same probability of being replied to. Two growth models for discussion trees have been proposed in [START_REF] Kumar | Dynamics of Conversations[END_REF] and [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF]. In [START_REF] Kumar | Dynamics of Conversations[END_REF], the probability of replying to a post depends on the number of replies and its recency. In [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF], the probability depends on the number of replies, its recency and whether a post is the root.

The remaining of this section is as follows. First, we recall the Preferential Attachment model of [START_REF] Barabási | Emergence of scaling in random networks[END_REF], and three other growth models for discussion where

α i = α 1 for i = 1 α c for i ∈ {2, ..., t} β i = β for i = 1 1 for i ∈ {2, ..., t} (4.9)
Note that α i is the preferential attachment exponent, and that if α 1 = α c and β = 1 we recover the Barabasi-Albert model of preferential attachment. The normalization factor is:

Z t = t l=1 (β l d l,t ) α l (4.10)
The Maximum Likelihood Estimators of the parameters α 1 , α c and β are found using the Nelder-Mead algorithm to minimize the negative log-likelihood [START_REF] Nelder | A simplex method for function minimization[END_REF]. Figure 4.3 shows some trees generated with their estimated parameters for four different datasets.

Gómez et al. (2012)

In [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF], the authors combine preferential-attachment, a bias towards the root, and novelty. Unlike in their former model in [START_REF] Gómez | Modeling the structure and evolution of discussion cascades[END_REF], here they sum these factors instead of multiplying them:

p(π t = i|π 1:t-1 ) = β i + αd i,t + τ t-i Z t for α, β ≥ 0, τ ∈ (0, 1) (4.11)
where

β i = β for i = 1 0 for i ∈ {2, ..., t} (4.12)
The normalization factor resembles the one of [START_REF] Kumar | Dynamics of Conversations[END_REF]. The differences are the bias towards the root β (only counted once since there is only one root) and the fact that [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF] gives an out-degree one to the root -which has no practical impact since it acts as an offset to the β term:

Z t = β + 2(t -1) + τ (τ t -1) τ -1 (4.13)
As in [START_REF] Gómez | Modeling the structure and evolution of discussion cascades[END_REF], Maximum Likelihood Estimators are found by Nelder-Mead optimization. Although the log-likelihood is now non-convex, the authors reported that, for large enough data, the problem seems to approach convexity and the optimization algorithm tends to give the same optimum for different initializations.

A new role-based network growth model

The models presented above consider that the probability of choosing a parent is irrespective of the user who writes the post. In other words, they consider that the model parameters are shared by all the users. However, it seems reasonable to think that different users may behave according to different parameters. Some users, for instance, might tend to reply to the root and avoid conversations deeper in the tree. Others might tend to ignore old posts. Others might be especially attracted by popular posts. Formally, we assume that there are K latent types of users and that users of type k behave according to their own group parameters θ k . We think of these parameters as the ones that control the different user roles. Thus, we will say that users with similar parameters (similar behavioral functions) share the same role. In this section, we present a new model, built upon [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF], that finds different parameters for different groups of users.

Formalization

We use the same parameters than [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF]: α controls the tendency of users to reply to popular posts, β controls the bias to the root and τ controls how much users penalize old posts.

For any given post n, let d n denote the degree of its parent; let r n be 1 if the parent of n is the root, and 0 otherwise. Let l n be the number of time-steps elapsed between the parent of n and n (l n ≥ 1). Let X = {x 1 , ..., x N } be the set of posts and let x i = {t i , d i , r i , l i } be the set of features associated to a post. Let us assume that there are K different types-or roles-of users who behave following different parameters θ 1 ,...,θ K where θ k = {α k , β k , τ k }. Let z u be the cluster -or role-of user u. Let N u be the set of posts written by u. The log-likelihood of the whole dataset can be expressed as:

ln p(X|θ) = U u=1 n∈Nu ln α zu d n + β zu r n + τ ln zu -ln Z n for α, β ≥ 0, τ ∈ (0, 1) (4.14)
where Z n is a normalization factor that guarantees that the probabilities of all possible choices sum up to 1. Let t be the time-step when the post n is written and let M denote the set of posts that have been added to the thread before the post n. The normalization factor associated to the post n written at time t (and therefore with t candidate parents) is: = ln α zn (2t -1) + β zn + τ zn (τ t zn -1) τ zn -1 (4.17)

ln Z n = ln
where the term (2t -1) is the sum of degrees in a tree of size t if the root vertex is considered to have an out-degree 1 (as we do), and τ t -1 τ -1 is the result of a geometric series. Note that this sum only depends on the time-step t and the model parameters, and not on the particular structure of the thread 1 . In practice, X may be represented as a matrix of feature vectors x i that makes the computing of the log-likelihood easy to vectorize in some programming languages.

Expectation-Maximization for the role-based growth model

We want to estimate the parameters of each role θ 1 , ..., θ K and the latent role of every user z 1 , ..., z U . Let z u = (z u1 , ..., z uK ) be the membership vector of user u where z uk = 1 if u belongs to cluster k and 0 otherwise. Let Z be the matrix of membership vectors. If there was one group of θ there would be no Z-or it would be an array of ones-and we could proceed as in [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF], and find the Maximum Likelihood Estimators for the parameters of the only cluster. However, if there are different groups then the optimization of the parameter will depend on the group since the parameters will be optimized taking into a considering who belongs to that group. This is a classic scenario that can be solved by Expectation-Maximization (EM). Let us start by expressing the log-likelihood of our model in terms of our latent variables Z:

ln p(X|θ) = ln Z p(X, Z|θ) (4.18)
Unfortunately we cannot analytically maximize the parameters θ because of the sum inside the logarithm. We make a trick consisting on multiplying and dividing the joint probability by an arbitrary probability distribution over Z in order to transform the term inside the logarithm into an expected value:

ln p(X|θ) = ln E Z [ p(X,Z|θ)] q(Z) Z q(Z) p(X, Z|θ) q(Z) (4.19)
Thanks to this trick, we can use Jensen's inequality to get the sum of outside the logarithm. We know, by Jensen's inequality, that the logarithm of a expected value is always greater or equal than the expected value of the logarithm2 . Therefore:

ln p(X|θ) = ln E Z [ p(X,Z|θ)] q(Z) Z q(Z) p(X, Z|θ) q(Z) ≥ E Z [ln p(X,Z|θ) q(Z) ] Z q(Z) ln p(X, Z|θ) q(Z) (4.20)
which is a lower bound of the log-likelihood ln p(X|θ). The equality holds if the function is a constant. In our case, when p(X, Z|θ)/q(Z) = c, or p(X, Z|θ)/c = q(Z). Since q(Z) is a probability distribution, its integral must be 1. Thus we have that the choice of q(Z) that maximizes the above expression is:

q(Z) = p(X, Z|θ) Z p(X, Z|θ) = p(Z|X, θ) (4.21)
which is the posterior distribution of Z given the observed data and the parameters.

Replacing q(Z) by the posterior in Equation 4.20 we obtain:

Z p(Z|X, θ) ln p(X,Z|θ)
(ln p(Z|π) + ln p(X|Z, θ))

E Z [ln p(X,Z|θ)] - H(Z) Z p(Z|X, θ) ln p(Z|X, θ) (4.22)
where π are the a priori probabilities assigned to each cluster, and H(Z) is the entropy of the posterior.

For the maximization of the log-likelihood we can ignore the entropy term and we can do an iterative optimization over parameters θ 1 , ..., θ K and the class assignments z 1 , ..., z U until a lower bound of the likelihood converges. That is, we maximize this term:

Z p(Z|X, θ) ln p(X,Z|θ) (ln p(Z|π) + ln p(X|Z, θ)) E Z [ln p(X,Z|θ)] (4.23)
At each iteration, we update the posterior p(Z|X, θ) using the θ of the last iteration (Estep) and then we re-compute the parameters θ, π that maximize the whole term using the updated posterior (M-step). We repeat the E and M steps until the improvement in the log-likelihood is lower than some threshold.

We now provide the exact equations for the E and M steps of our model. Let X u be the submatrix of X formed by all the posts written by user u. Let Z = {z 1 , ..., z U } be the indicators matrix where z i = {z i1 , ..., z iK } and where z ik is 1 if user i belongs to group k -otherwise, z ik is 0.

M-step-For the M-step, the expectation of the complete log-likelihood is:

E [ln p(X, Z|θ)] = E U u=1 K k=1 z uk {ln π k + ln p(X u |θ k )} (4.24) = K k=1 U u=1 E [z uk ] {ln π k + ln p(X u |θ k )} (4.25)
where, for a given cluster k, each X u proportionally contributes to E[z uk ]. We note that the parameters of each cluster can be optimized separately as:

arg max θ k U u=1 E [z uk ] {ln π k + ln p(X u |θ k )} (4.26)
and for the π parameter:

π k = 1 U U u=1 E [z uk ] (4.27)
E-step-In the E-step, we update the posterior:

p(Z|X, θ) = p(X, Z|θ) Z p(X, Z|θ) = U u=1 K k=1 p(X u |θ k ) z uk Z U u=1 K k=1 p(X u |θ k ) z uk (4.28)
which can be easily factorized by users, and then we can obtain the expected value for each z uk :

E[z uk ] = z uk z uk π k p(X u |θ k ) K k=1 π k p(X u |θ k ) = π k p(X u |θ k ) K k=1 π k p(X u |θ k ) (4.29)
where the likelihood p(X u |θ k ) can be also factorized:

p(X u |θ k ) = n∈Nu p(x n |θ k ) (4.30)
The E-step is done with Equation 4.29 while the M-step is done with Equation 4.25 And because Equation 4.25 cannot be analytically maximized due to the form of our likelihood, we use Nelder-Mead optimization as in [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF].

Experiments

Ideally, we would like our model to be descriptive and predictive. That is, we would like it to give clusters of users and parameters of each cluster, and to use these parameters to predict a user behavior in new threads. If the model can predict, it would confirm that meaningful roles exist and that the behavior of a group of users is consistent, not just circumstantial or mere noise.

In this section, we infer the parameters for our model and find clusters of users in the podemos and gameofthrones datasets (Section 4.3.2). Then we benchmark our model against [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF] (henceforth gomez and lumbreras) by executing two different tasks. First, we test whether our model can generate synthetic threads that are more realistic than those generated by gomez (Section 4.3.3). Lastly, we test whether our model can make better predictions of post replies in a test set (Section 4.3.4).

Dataset

In order to test the predictive power of our model, we divide each user's posts into training (50%), validation (25%) and test (25%). We used the training set of posts to estimate the parameters of gomez (α, β, τ ) and lumbreras (π, α k , β k , τ k for each cluster and p(z u = k|X u , θ k ) for each user.). We used the validation set to select the final number of clusters in lumbreras, and finally we used the test set to compare the results of the two models.

Users with only one or two posts will be assigned to some of the clusters (and its parameters) even if one or two posts is clearly not enough information to infer anything about the user. Thus, we selected the 1,000 users with more posts in the forum to guarantee a high enough number of observations per user.

Inference

To infer the cluster of each user z 1 , ...z U and the cluster parameters θ 1 , ...θ K we initialize the parameters α, β, τ for each cluster and run the Expectation and Maximization steps defined in Section 4.2.2. Regarding the M-step, the non-convexity of the log-likelihood might make it necessary to try different re-starts to reduce the odds of being trapped in a local maximum. However, as in [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF], we noticed that the Nelder-Mead optimization in our Reddit datasets only gives different maxima when the number of observations is small. Number of clusters. To decide the number of clusters, we computed the Bayesian Information Criteria (BIC) for multiple models, from one cluster (equivalent to gomez model) to more than 50. The BIC is a measure of the likelihood penalized by the complexity of the model. In particular, it is defined as

BIC = -2L + log(n)n p (4.31)
where L is the log-likelihood, n p is the number of parameters (for k clusters with three parameters in each cluster, n p = 3K + K -1) and n is the number of observations. The best model candidates are considered those that minimize the the BIC. We computed the BIC in the validation set and we found a minimum BIC at k = 24 in podemos.

In gameofthrones, we found a first minimum at K = 15. In Figure 4.4 we show the BIC curves for podemos and gameofthrones. 3 We also computed, for each user, the uncertainty of its classification as (1max(z i1 , ...z iK )) [START_REF] Bensmail | Inference in model-based cluster analysis[END_REF]. We obtained a mean uncertainty of 0.03 and a median uncertainty of 0 for podemos, and a mean of 0.12 and a median of 0.03 in gameofthrones, which means that the model is very sure about the user memberships. We finally chose K = 15 for gameofthrones, and K = 15 for podemos to keep a low complexity of the model-as a sanity check, we repeated the experiments below for higher K and obtained very similar results. The estimated parameters are shown in 13 of gameofthrones, made of 8 users whose only predictive parameter is the recency -they tend to penalize old posts less than the other users. Note that the closer to zero are the parameters, the more random the behavior-degree, recency or root posts would not have any effect and all posts would have the same probability of being chosen as parent.

Structural properties

After estimating the parameters for gomez and lumbreras we generated 10,000 synthetic threads with each in order to see whether there are structural difference between the two models. We generated the threads as follows. We assume that we know the authors and the order in which they participate, but we do not know to whom they will reply within their posts -we need the authorship information to know which parameters we have to apply. Thus, for a randomly chosen thread in the dataset (with at least a post from the active users), we keep the sequence of authors of the posts chronologically sorted, and we remove the edges. That leaves us with a sorted sequence of posts with no tree structure. Then, we use the estimated parameters to generate a new set of edges keeping the real sequence of authors. Recall that, in lumbreras, the parameters applied to a post v depend on the cluster of its author a(v). In other words, a post chooses its parent according to its parameters α z(a(v)) , β z(a(v)) , τ z(a(v)) where z(a(v)) denotes the cluster of the author of v. If the author is not in our list of analysed users, we use the parameters estimated in Gomez. Therefore, the only difference between the trees generated by lumbreras and gomez is in the posts written by the 1,000 most active users. Following [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF], we measured the following properties:

• Degree distribution: number of replies to a post

• Subtree size: number of descendants of a post

• Size versus depth: number of posts in the tree versus length of the longest chain

The results are shown in Figure 4.5. We observe that the ability to reproduce real structures is very similar in both models. This is not entirely unsurprising since, as we said above, only posts written by the top 1,000 have different parameters than the gomez model.

Link prediction

We finally analyzed whether our clusters -roles-have predictive power. If users behave, at some degree, according to role archetypes, we should be able to predict their behavior using the parameters associated to their estimated role. Otherwise, the clusters are only a good description of what happened.

We tested the predictive power of our clusters through a task of link prediction, proceeding as follows: for all the trees in our dataset, we removed the parent of those posts that had been labeled as test and we tried to predict their parents with lumbreras and gomez. We took three different metrics (likelihood of the test observations, percentage of hits and ranking error) and compared the two models in each clusters. For a better understanding of the strengths and weaknesses of the models, we included two reference models: a model that always chooses the post with the highest degree (barabasi ) and a model that always chooses the most recent post (tau).

Likelihood of test data. We compute the mean negative log-likelihoods of the choices given the model parameters and (for the lumbreras model) the posts authors. Given a post, a set of candidate parents and the parameters of the model, we know how to compute the likelihood of each possible parent choice. For gomez, the log-likelihood of a choice is computed using Equation 4.11. For lumbreras, we first get the most likely cluster of the author z

′ i = arg max k p(z ik |X, θ k ) (4.32)
and then apply the parameters of the cluster z ′ i to the same equation. Figure 4.6 shows the mean negative log-likelihoods in each cluster. The negative log-likelihood is lower (better) for lumbreras in every cluster. We note that the groups of users with a very high β (cluster 6 in podemos and cluster 8 in gameofthrones), are specially predictable; the small group of users in cluster 13 of gameofthrones (the ones with the smallest α and β) are also very predictable in terms of the likelihood of their choices. Even if these are also the clusters with better likelihood in gomez the improvement in lumbreras is bigger.

Hits. We define as a hit when the chosen parent was the most likely parent according to the model. Figure 4.7 shows the hits for gomez, lumbreras and the other two reference models. On the one hand, there is almost no difference between gomez and barabasi, which means that gomez usually assigns more likelihood to the post with more replies. This is surprising since gomez has very lower α in the two datasets. A possible explanation is that, since gomez has a high β and root posts also tend to have a higher degree, predicting the post with the highest degree often has the same result than predicting the root. Another remarkable result is that the tau model is always the worst model except for the cluster with the lowest β (clusters 10 and 12 in podemos and cluster 13 in gameofthrones), where tau outperforms barabasi and gomez. These are users for whom the degree and the root posts are not as important as for the others, and thus their behaviors are harder to predict by barabasi and gomez. Because lumbreras detected that these users have different behavior, it makes better predictions. Yet, these are the only clusters where lumbreras is clearly better than barabasi and gomez. Normalized Ranking Error. Our hits metric only considers whether the model did a perfect prediction. Yet it is interesting to give some score, for instance, to almostperfect predictions. If the chosen parent was given the second highest likelihood in a very long thread, we might give assign a near 1 score to the prediction. To formalize this idea, we choose to define a Normalized Ranking Error (NRE) as:

N RE = r -1 l -1 (4.33)
where r is the position of the chosen parent in the predicted ranking and l is the length of the thread, or the number of parents to choose from (1 ≤ r ≤ l).

While hits are low for almost every cluster, the ranking error shows a more optimistic picture (Figure 4.8): the medians for gomez and lumbreras are clearly better than those of the reference models. Yet, although for clusters 12 and 14 in podemos and for clusters 3, 4, 11 and 13 in gameofthrones the median score in lumbreras is slightly better than in gomez, there is barely any difference for the rest of clusters.

Finally, Figure 4.9 shows how thread sizes affect the accuracy of the models. We see that the longer the thread, the easier for tau to make better predictions and the harder To summarize, we showed that our model, which infers groups of users with different behavioral, gets better likelihoods than gomez when measured over unobserved behaviors. This supports the hypothesis that users behave, to some extent, following different behavioral functions and that they keep some consistency in their behaviors. That is, there is some role structure. Moreover, for some groups of users with outlier behaviors, our model is able to make better predictions terms of perfect hits. Yet, our (role-based) model does not make better predictions for most clusters. The increase in the likelihood is not enough to make better predictions in those clusters.

Summary

In this chapter, we have conceptualized user roles as probability distributions over behaviors. In particular, we have studied replying behaviors: tendencies to reply to this or that post given the properties of each of the posts in the thread (number of replies, recency, root or not root) These tendencies are formalized as probability distributions with three parameters. Our hypothesis has been that users can be divided into subgroups -clusters or roleswhose members behave according to the same parameters.

We set three goals: (a) proposing a behavioral function for discussion threads (b) finding groups of users with the same behavioral function (the same parameters) and (c) testing whether these behavioral functions have predictive power -if they can predict the behavior of a user in a new context.

We have shown that, indeed, we can find different groups of users with different behavioral functions. That means that our model can be used, for instance, to better understand the dynamics of a community by inferring different groups of users that have contributed to these dynamics in different ways.

Regarding the predictive power, allowing different model parameters for different subgroups of users increases the likelihood of the model in unobserved behaviors (test set). Nonetheless, this improvement in the likelihood is not enough to make better predictions. Indeed, in terms of practical predictions of which post will be the next to be replied, our role-based model makes no better predictions -for most roles-than a model without roles.

Based on that, our conclusion is that our proposed concept of behavioral role has some descriptive power but that the predictive power is almost marginal. It might be that consistency in the behaviors is indeed weak -although not totally random-and that, in terms of signal, there is too much noise. Or it might also be that the tree growth models presented in this chapter are only able to capture a small part of this behavioral signal.

Role detection based on features and latent behavioral functions with dual-view mixture models

The whole is simpler than its parts.

Josiah Willard Gibbs

In this chapter, we present a dual-view mixture model to cluster users based on their features and latent behavioral functions. The model infers the groups of users as well as their latent behavioral functions. We also propose a non-parametric version based on a Dirichlet Process to automatically infer the number of clusters. We test the properties and performance of the model on a synthetic dataset that represents the participation of users in the threads of an online forum. We show that dual-view models outperform single-view ones when one of the views lacks information.

Contents

Introduction. Why a dual-view model?

A common issue we have had to deal with in previous chapters is the scarcity of user data. To assert that a user belongs to a given cluster requires enough data from the user so that we can be confident that her observed behaviors are really a trait of her role and not just a casual behavior without any relevant meaning. We have faced this problem when clustering users based on feature vectors extracted from the structure of conversations where they participate, and also when clustering users based on theirbehavioral-parameters in a stochastic process that models user replies in conversation threads. To overcome that issue we propose, in this chapter, a dual-view model that integrates both approaches.

The dual-view model clusters users based on these two types of information-observed features and latent behavioral functions-to infer user clusters that are more robust and meaningful. The goal is to infer the behavioral function of each user and a clustering of users that takes into account both their features and their behavioral functions. In our model, users in the same cluster are assumed to have similar features and behavioral functions, and thus the inference of the clusters depends on the inference of the behavioral functions, and vice versa. The model prioritizes user partitions where each group has similar features and similar behavioral functions.

In this chapter, we have tested the model on synthetic data in order to evaluate and understand its properties. Both the features and the behavior coefficients in our data are drawn from Gaussian distributions. Nonetheless, the model may be applied to the neighborhood-based features of Chapter 3 and the reply-based behaviors of Chapter 4 if the probability distributions are adapted. In that case, the underlying assumption would be that users who tend to appear in the same type of neighborhood have also similar α, β and τ parameters.

Related models

Latent behavioral functions are used to model individual behaviors such as pairwise choices over products, reactions to medical treatments or user activities in online discussions. The inclusion of latent behavioral functions in clustering methods has several potential applications. On the one hand, it allows richer clusterings in settings where users, besides being described through feature vectors, also perform some observable actions that can be modeled as the output of a latent function. On the other hand, by assuming that users in the same cluster share similar latent functions, it may leverage inference of these functions. In the case, for instance, of recommender systems, this may be used to alleviate the cold-start problem -the fact that we cannot infer user preferences until they have interacted with the system for a while-if we have a set of features describing user profiles. In that context, a user with low activity will be given the same cluster as those users with similar features. Then, the inference of its behavioral function (e.g.: its preferences) will be based on the behavioral functions of the users in the same cluster.

Related models

One of the difficulties in dealing with latent behavioral functions is that, since these functions are latent, they are not representable in a feature-like way and therefore traditional clustering methods are not directly applicable. Our approach is to think of features and behaviors as two different views or representations of users, and to find the partition that is most consensual between the different views. In this sense, this is a multi-view clustering problem [START_REF] Bickel | Multi-view clustering[END_REF]. However, the clustering in one of the views depends on latent variables that need to be inferred. In this regard, it has similarities to Latent Dirichlet Allocation when used for clustering (e.g., cluster together documents that belong to the same latent topics).

Multi-view clustering ranges from [START_REF] Kumar | Co-regularized Multi-view Spectral Clustering[END_REF], which finds a consensual partition by co-training [START_REF] Mitchell | Combining labeled and unlabeled data with co-training[END_REF], to [START_REF] Greene | Multi-View Clustering for Mining Heterogeneous Social Network Data[END_REF], which proposes a two-step multi-view clustering that allows both consensual groups and groups that only exist in one of the views. In [START_REF] Niu | A nonparametric {B}ayesian model for multiple clustering with overlapping feature views[END_REF], the multi-view approach is presented as the problem of finding multiple cluster solutions for a single description of features.

In this chapter, we extend the idea of multi-view clustering to deal with cases where one of the views comprises latent functions that are only indirectly observed through their outputs. The proposed method consists of a dual-view mixture model where every component represents two probability densities: one over the space of features and the other over the space of latent behavioral functions. The model allows to infer both the clusters and the latent functions. Moreover, the inference of the latent functions allows to make predictions on future user behaviors. The main assumption is that users in the same cluster share both similar features and similar latent functions and that users with similar features and behaviors are in the same cluster. Under this assumption, we show that this dual-view model requires less examples than single-view models to make good inferences.

The idea of using similarities in one view to enhance inference in the other view is not new. In bioinformatics, [START_REF] Eisen | Cluster analysis and display of genome-wide expression patterns[END_REF] found evidence suggesting that genes with similar DNA microarray expression data may have similar functions. [START_REF] Brown | Knowledge-based analysis of microarray gene expression data by using support vector machines[END_REF] exploit this evidence to train a Support Vector Machine (SVM) for each functional class and predict whether an unclassified gene belongs to that class given its expression data as an input. [START_REF] Pavlidis | Learning gene functional classifications from multiple data types[END_REF] extend the method of Brown et al. by also exploiting evidence that similar phylogenetic profiles between genes suggested a same functional class as well [START_REF] Pellegrini | Assigning protein functions by comparative genome analysis: protein phylogenetic profiles[END_REF]. Pavlidis et al. propose a multi-view SVM method that uses both types of gene data as input.

More recently, [START_REF] Cheng | Social Role Identification via Dual Uncertainty Minimization Regularization[END_REF] applied multi-view techniques to predict user labels in social networks such as LinkedIn (e.g., engineer, professor) or IMdB (e.g., directors, actors). Their method lies in the maximization of an objective function with a coregularization that penalizes predictions of different labels for users that are similar either in terms of profile features or in terms of graph connectivity.

In the context of preference learning, [START_REF] Bonilla | Gaussian process preference elicitation[END_REF] also work with the assumption that similar users may have similar preferences, and models this assumption via a Gaussian Process prior over user utility functions. This prior favors utility functions that account for user similarity and item similarity. To alleviate the computational cost of this model, [START_REF] Abbasnejad | Learning communitybased preferences via {D}irichlet process mixtures of {G}aussian processes[END_REF] propose an infinite mixture of Gaussian Processes that generates utility functions for groups of users assuming that users in each community share one single utility function. The main difference between our model and [START_REF] Abbasnejad | Learning communitybased preferences via {D}irichlet process mixtures of {G}aussian processes[END_REF] in that their model clusters users only based on their utility functions, while ours considers user features as well. In short, ours is a multi-view clustering model that also infers latent behavioral functions, while theirs is a single-view model focused on the inference of latent functions.

The chapter is structured as follows: first, we briefly recall mixture models. Second, we present our model as an extension of classic mixture models. The description of the model ends up with a generalization to an infinite number of clusters, which makes the model non-parametric. We finally describe an application to cluster users in online forums and end the chapter with experiments on synthetic data to demonstrate the properties of the model.

Model description

In this section, we introduce our model through three sequential steps. First, we start with a simple mixture model. Second, we extend the mixture model to build a dual-view mixture model. And third, we extend the dual-view mixture model so that the number of clusters is automatically inferred.

Mixture models

When a set of observations x 1 , x 2 , ...x n cannot be properly fitted by a single distribution, we may get a better fit by considering that different subsets of observations come from different component distributions. Then, instead of a unique set of parameters θ of a single distribution, we need to infer K sets of parameters θ 1 , ..., θ K of K components and the assignments z 1 , ..., z n of individual observations to one of these components. The model can be expressed as follows:

x i |z i , θ z i ∼ F (θ z i ) z i ∼ Discrete(π) (5.1)
where π = (π 1 , ...π K ) contains the probability of belonging to each component and F is the likelihood function over the observations. In Bayesian settings it is common to add priors over these parameters, resulting in a model such as:

x i |z i , θ z i ∼ F (θ z i ) θ j ∼ G 0 z i |π ∼ Discrete(π) π ∼ Dirichlet(α) (5.2)
where G 0 is the base distribution and α the concentration parameter. Mixture models are mostly used for density estimation. Nonetheless, inference over z allows to use them as clustering methods. In this case, every component is often associated to a cluster.

Dual-view mixture model

In this section, we present an extension of mixture models to account both for features and latent behavioral functions. We denote by behavioral functions any function which, if known, can be used to predict the behavior of a user in a given situation. In the context of preference learning [START_REF] Bonilla | Gaussian process preference elicitation[END_REF][START_REF] Abbasnejad | Learning communitybased preferences via {D}irichlet process mixtures of {G}aussian processes[END_REF] or recommender systems [START_REF] Cheung | Extended Latent Class Models for Collaborative Recommendation[END_REF], behavioral functions may indicate hidden preference patterns, such as utility functions over the items, and the observed behavior may be a list of pairwise choices or ratings. In the context of online forums, behavioral functions may indicate the reaction of a user to a certain type of post and the observed behavior may be the set of replies to different posts. In general, behavioral functions are linked to observed behaviors through a likelihood function p(y|f ) where y represents an observation and f the latent behavioral function. Let a u be the set of (observed) features of user u. Let f u be a (latent) function of user u. Let y u be the (observed) outcome of f u . By slightly adapting the notation from last section we can describe the variables of our dual model as follows:

a u |z u , θ (a) zu ∼ F (a) (θ (a) zu ) f u |z u , θ (f) zu ∼ F (f) (θ (f) zu ) y u |f u ∼ p(y u |f u ) θ (a) j ∼ G (a) 0 θ (f) j ∼ G (f) 0 z u |π ∼ Discrete(π) π ∼ Dirichlet(α) (5.3)
where we use the superindex (a) for elements in the feature view and the superindex (f ) for elements in the latent functions view, henceforth behavior view. Otherwise, the structures are similar except for y u , which represents the set of observed behaviors for user u. The corresponding Probabilistic Graphical Model is shown in Figure 5.1. Every component has two distributions: one for features and one for latent behavioral functions. Latent behavioral functions are not directly observable, but they may be inferred through some observations if we have a likelihood function of observations given the latent functions.

The model can also be expressed in terms of a generative process:

• For every component k:

α π z u a u θ (a) k f u θ (f) k y u G (a) 0 G (f) 0 U K Figure 5
.1 Graphical model of the generative process for U users and K clusters. Shaded circles represent observations and white circles represent latent variables. Views are connected through the latent assignments z. A user u draws a feature vector a u and a behavior f u from the cluster indicated by z u (the u-th element of z).

-Draw feature and function parameters from their base distributions θ • Draw the mixture proportions π ∼ Dirichlet(α).

• For every user u:

-Draw a component assignment z u ∼ Multinomial(π).

-Draw user features a u ∼ F (a) (θ

(a) zu ).
-Draw a user latent function

f u ∼ F (f) (θ (f) zu ).
-Draw a set of observed behaviors y u ∼ p(y u |f u ).

Left and right branches of Figure 5.1 correspond to the feature view and the behavior view, respectively. Note that every component contains two sets of parameters, one for features and one for behaviors, so that the two views can be generated from the same component. This encodes our prior assumption that users who belong to the same cluster should be similar in both views.

Given the user assignments z, variables in one view are conditionally independent from variables in the other view. That means their inferences can be considered separately. However, inference of z uses information from both views. The conditional probability of z given all the other variables is proportional to the product of its prior and the likelihood of both views: p(z|•) ∝ p(z|π)p(a|θ (a) , z)p(f |θ (f) , z)

(5.4)

The information given by each view is conveyed through the likelihood factors p(a|θ (a) , z) and p(f |θ (f) , z). The ratio between the conditional probability of a partition z and the conditional probability of a partition z ′ is:

p(z|•) p(z ′ |•) = p(z|π) p(z ′ |π) p(a|θ (a) , z) p(a|θ (a) , z ′ ) p(f |θ (f) , z) p(f |θ (f) , z ′ ) (5.5)
where the contribution of each view depends on how much more likely z is over the other assignments in that view. An extreme case would be a uniform likelihood in one of the views, meaning that all partitions z are equally likely. In that case, the other view leads the inference.

The two views provide reciprocal feedback to each other through z. This means that if one view is more confident about a given z, it will not only have more influence on z but also it will force the other view to re-consider its beliefs and adapt its latent parameters to fit the suggested z.

Note also that inference of latent behavioral functions may be used for prediction of future behaviors.

Infinite number of clusters

So far, we have considered the number of components K to be known. Nonetheless, if we let K → ∞ and marginalize over the mixture weights π, it becomes a non-parametric model with a Dirichlet Process (DP) based on a Chinese Restaurant Process (CRP) prior over the user assignments, which automatically infers the number of active of components (see the Appendix for the full derivation). Since we integrate out π, user assignments are not independent anymore. Instead, the probability of a user u to be assigned to a non-empty (active) component k, given the assignments of all other users z -u , is: 5.6) where c denotes the number of non-empty components and n k is the number of users already assigned to the k-th component. The probability of assigning a user u to an empty (non-active) component, that would be labelled as c + 1, is:

p(z u = k|z -u ) ∝ n k for k = 1, ..., c (
p(z u = k|z -u ) ∝ α for k = c + 1 (5.7)
These two equations reflect a generative process that assigns users to clusters in a rich get richer manner. The more users in a component, the more attractive this component becomes. Empty components also have a chance of being filled. Despite the appearance of these equations, the idea behind the inference of z remains the same. The only differences between the finite and the infinite cases are the number of components and the probabilities to be assigned to each component.

Application to role detection in online forums

The above model provides a general framework that can be adapted to many scenarios.

In this section, we apply our model to the clustering of users in online forums -role detection. Although clustering based on user features may provide interesting insights (see Chapter 3), we think that the notion of role should include information that allows to predict behaviors (see Chapter 4). After all, as we have stated in previous chapters, this is what roles are useful for. We expect that a person holding a role behaves according to their role. Let us specify the two views of our model for this scenario, given U users who participate in a forum composed of T discussion threads. For the feature view, we describe every user through a feature vector a u = (a u1 , a u2 , ..., a uD ) T that will typically contain features such as centrality metrics or number of posts. For the behavior view, we define a latent behavioral function that we call catalytic power and denote by b u , which represents the ability of a user to promote long discussions; we refer to b as the vector of all user catalytic powers. Let the participation vector of the discussion thread p t = (p 1t , ..., p U t ) T be a binary array indicating which users participated among the first m posts of the thread t. Assuming that the dynamic of a discussion is strongly conditioned by the first participants, we model the final length of a thread y t :

y t ∼ N (p T t b, s -1 y )
where p T t b is the cumulated catalytic power of users who participated in its first m posts and s y represents the precision (inverse of the variance) of the unknown level of noise.

If the assumption that there exist groups of users sharing similar features and similar catalytic power holds, then our model will not only find a clustering based on features and behaviors (catalytic powers), but it will also exploit feature information to infer catalytic powers and, vice versa, the inferred catalytic powers will be treated by the model as an extra feature dimension.

Note that, unlike the model presented in Figure 5.1, the observed output y t is common to all users who participated in the first m posts of thread t. Moreover, y t depends on the observed participations p t . We also defined the noise factor s y which was not explicitly present in the general model. The graphical model would be similar to that of Figure 5.1 but with the thread lengths y, the participation matrix P and the noise s y out of the users plate. In the remaining of this section we provide more details about the components of the two views.

Feature view

In this section we specify the component parameters θ of the feature view. Our choice of priors follows that of the Infinite Gaussian Mixture Model (IGMM) as described by [START_REF] Rasmussen | The infinite Gaussian mixture model[END_REF] and [START_REF] Görür | Dirichlet process Gaussian mixture models: choice of the base distribution[END_REF].

The feature vectors are assumed to come from a mixture of Gaussian distributions:

a u ∼ N µ (a) zu , S (a)
zu -1

( 5.8) where the mean µ

W (a) 0 ∼ W(D, 1 D Σ a ) (5.13) 1 β (a) 0 -D + 1 ∼ G(1, 1 D ) (5.14)
where µ a and Σ a are the mean and covariance of all the features vectors and G is the Gamma distribution. Note that, as pointed out in [START_REF] Görür | Dirichlet process Gaussian mixture models: choice of the base distribution[END_REF], this choice of hyperparameters, which is equivalent to scaling the data and using unit priors, makes the model invariant to translations, rotations, and rescaling of the data. Conjugate priors are chosen whenever possible to make the posteriors analytically accessible. As for β (a) 0 , the prior in Equation 5.14 guarantees that the degrees of freedom in the Wishart distribution in Equation 5.10 are greater than or equal to D -1. The density p(β (a) 0 ) is obtained by a simple transformation of variables (see Appendix).

Shared parameters

As for the common variables z and α, z is given a Chinese Restaurant Process prior:

p(z u = k|z -u , α) ∝ n k for k = 1, ..., c α for k = c + 1 (5.24)
where c denotes the number of non-empty components before the assignment of z u and n k is the number of users already assigned to the k-th component. The concentration parameter α is given a vague inverse gamma prior:

1 α ∼ G(1, 1)

Inference

The latent parameters of our model can be inferred by using Gibbs sampling, and sequentially taking samples of every variable given the others. Conditional distributions are detailed in the appendices. A single iteration of the Gibbs sampler goes as follows:

• Sample component parameters S (a) k , µ (a)
k conditional on the indicators z and all the other variables of the two views.

• Sample hyperparameters µ • Sample coefficients b conditional on the indicators z and all the other variables of the two views.

• Sample s y conditional on the indicators z and all the other variables of the two views.

• Sample indicators z conditional on all the variables of the two views.

Since we use conjugate priors for almost all the variables, their conditional probabilities given all the other variables are analytically accessible. The degrees of freedom β (a) 0 , β (f) 0 and the concentration parameter α can be sampled by Adaptive Rejection Sampling [START_REF] Gilks | Adaptive rejection sampling for {G}ibbs sampling[END_REF], which exploits the log-concavity of p(log β

(a) 0 |•), p(log β (f) 0 |•)
and p(log α|•) (see Appendix). As for the sampling of z, the conditional probability of assigning user u to an active component k is proportional to the prior times the likelihoods: 5.25) and for the conditional probability of assigning z u to a non-active component:

p(z u = k|z -u , α, •) ∝ n k p(a u |µ (a) k , S (a) k )p(b u |µ (f) k , s (f) k ) for k = 1, ..., c (
p(z u = k|z -u , α, •) ∝ α p(a u |µ (a) k , S (a) k )p(µ (a) k )p(S (a) k )dµ (a) k dS (a) k × p(b u |µ (f) k , s (f) k )p(µ (f) k )p(s (f) k )dµ (f) k ds (f) k for k = c + 1 (5.26)
Unfortunately, these integrals are not analytically tractable because the product of the factors does not give a familiar distribution. [START_REF] Neal | Markov chain sampling methods for {D}irichlet process mixture models[END_REF] proposes to create m auxiliary empty components with parameters drawn from the base distribution, and then computing the likelihoods of a and b given those parameters. The higher the m, the closer we will be to the real integral and the less autocorrelated the cluster assignments will be. However, the equilibrium distribution of the Markov Chain is exactly correct for any value of m. To speed up the computations, m is usually small. For our experiments, we chose m = 3. That is, we generate 3 additional empty tables each one with its own parameters µ ′ , S ′ , µ ′ , s ′ . We also run some experiments with m = 4 and m = 5, without observing significant differences neither in the clustering nor in the predictions, while it significantly increased the computational time. See [START_REF] Neal | Markov chain sampling methods for {D}irichlet process mixture models[END_REF] for a more systematic study on the effect of m.

Predictive distribution

We are also interested in the ability of the model to predict new thread lengths. The posterior predictive distribution over the length of a new thread is:

p(y * |p * ,P, y) = θ p(y * |p * , θ)p(θ|y, P)dθ (5.27) where p * is the participation vector of the new thread, and y * its predicted length. If we have samples θ (1) , ..., θ (N ) from the posterior p(θ|y, P), we can use them to approximate the predictive distribution:

p(y * |p * ,P, y) ≈ 1 N N i=1 p(y * |p * , θ (i) ) (5.28)
where θ (i) are the i-th samples of b and σ y .

Experiments

We generated three scenarios to study in which situations dual-view models outperform single-view ones. The data reproduces the scenario of online forums presented in Section 5.4. In the first scenario, users belong to five clusters and those who belong to the same cluster in one view also share the same cluster in the other view (agreement between views). In the second scenario, users belong to five clusters in the behavior view but two of the clusters are completely overlapped in the feature view (disagreement between views). In order to reproduce a more realistic clustering structure, in the last scenario user features and coefficients are taken from the iris dataset.

We will see in Section 5.6.6 that the main bottleneck of the model is the sampling of coefficients b 1 , ..., b U since they are obtained by sampling from a U -dimensional Gaussian distribution that requires, at each Gibbs iteration, inverting a U × U matrix to get its covariance. This issue would disappear if the inference of the behavioral function parameters for a user were independent from the parameters of the other users. In this chapter, we use the iris dataset to demonstrate the properties of the model as a whole, without making any statement on the convenience of the presented behavioral functions.

Compared models

We compared two dual-view models and one single-view model. We call them dualfixed, dual-DP and single. The dual-fixed corresponds to the present model where the number of clusters is set to the ground truth (five clusters). The dual-DP corresponds to the present model where the number of clusters is also inferred (Section 5.3.3). The single model corresponds to a Bayesian linear regression over the coefficients b, which is equivalent to the behavior view specified in Section 5.4.2 where the number of clusters is set to one (that is, no clusters at all) and therefore there is no information flowing from the feature view to the behavior view; this model can only learn the latent coefficients b.

Table 5.1 presents these three models as well as other related models that appear when blinding the models from one of the views. Note that we left out of the analysis those models that use clustering but are blinded of one view. The first two of these (IGMM and GMM), are regular clustering methods over feature vectors; we discarded them because they do not make inferences on latent behaviors. The last two (we call them latent-IGMM and latent-GMM) are Bayesian linear regressions where coefficients are assumed to come from a mixture of Gaussians; because these are in practice very similar to a simple Bayesian linear regression (they can be seen as Bayesian linear regressions with priors that tend to create groups of coefficients), we chose to benchmark only against the single model.

Posterior distributions of parameters are obtained by Gibbs sampling. We used the coda package in R [START_REF] Plummer | CODA: Convergence Diagnosis and Output Analysis for MCMC[END_REF] to examine the traces of the Gibbs sampler. For the convergence diagnostics, we used Geweke's test available in the same package. After some initial runs and examinations of the chains to see how long it took to converge to the stationary distribution for the dual models, we observed that convergence for all the models is usually reached before 5,000 samples. Since we run a large number of automatized experiments, we set a conservative number of 30,000 samples for every run, from which the first 15,000 are discarded as burn-in samples. For the first two experiments we initialized our samplers with all users in the same cluster. For the iris experiment we used the result of a k-means with 10 clusters over the feature view. We did either from having too few threads to learn from or from having a high ratio of users versus threads since we have too many user behavior coefficients to learn. Figure 5.3 shows how increasing the threads vs users ratio affects the accuracy of each model. When the number of threads is too low with respect to the number of users neither view has enough information and thus the three models make bad predictions the inference is difficult for the three models. Yet, dual-view models need less threads than the single model to make good inferences. When the number of threads is high enough, the three models tend to converge.

The number of users and threads in the experiments ranges from 10 to 100 users and from 10 to 100 threads. We avoided larger numbers to prevent the experiments from taking too long. 30,000 iterations of the Gibbs sampler described in Section 5.5 for 50 users and 100 threads take around three hours in a Pentium Intel Core i7-4810MQ @2.80GHz. Nevertheless, the ratio users/threads remains realistic. In the real forums that we analyzed from www.reddit.com a common ratio is 1/10 for a window of one month.

Disagreement between views

If each view suggests a different clustering z, dual models should find a consensus between them (recall Equation 5.4). We generated a new dataset (Figure 5.4) where there are four clusters according to the feature view and five clusters according to the behavior view.

Figure 5.5 shows the posterior distributions (over thread lengths and over pairwise clustering) when (a) the behavior view has more information (b) both views lack data (c) the feature view has more information. By having more information we mean that a view dominates the inference over the posterior of the clustering z. (a) Lack of information in feature view: If the number of users is low but they participated in a sufficient number of threads, the behavior view (which sees five clusters) will be stronger than the feature view (which sees four clusters) and will impose a clustering in five groups. User coefficients (used for thread length predictions) are also well estimated since the number of threads is high enough to learn them despite the lack of help from the other view (Figure 5.5a).

(b) Lack of information in both views: In the middle ground where neither view has enough evidence, the model recovers four clusters and the predictive posterior over thread lengths gets wider though still making good inferences (Figure 5.5b).

(c) Lack of information in behavior view: If the number of users is high and the number of threads is low, the feature view (four clusters) will have more influence in the posterior than the behavior view (five clusters), (Figure 5.5c). Predictions get worse because the model imposes a four clusters prior over coefficients that are clearly grouped in five clusters.

In order to compare between the performance in case of agreement and the performance in case of disagreement, we repeated the experiments of the last section with the current configuration. Figure 5.6 shows the performance of the models for 50 users and a different number of threads. While predictions and clustering improve with the number of threads, clustering with a small number of threads is worse in case of disagreement since the feature view imposes its 4 clusters vision. To recover the five clusters we would need either more threads or less users.

For the predictions, the dual models still outperform the single one because the feature view mostly agrees with the behavior view except for the users in one of the clusters. If all user features were in the same cluster, (no clustering structure) the performance of the predictions would be similar for the three models since the feature view would add no extra information. If we randomize the features so that, for instance, there are five clusters in the feature view that are very different from the clusters in the behavior view, we may expect the dual-view models to give worse predictions than the single-view one in those cases where they now perform better. In those cases, dual-models would be getting noise in the feature view (or very bad priors) and only a large enough number of threads could compensate for it.

Iris dataset

To reproduce a more realistic clustering structure we performed a last experiment based on the iris dataset. We used the iris data available in R, which corresponds to the original dataset reported in [START_REF] Anderson | The Irises of the Gaspe Peninsula[END_REF]. In our experiment, features correspond to three of the features of the iris dataset (Figure 5.7). We chose three out of the four features (sepal width, petal length and petal width) as well as a random subset of 50 observations so that the clustering task is harder if we only use the feature view. The coefficients of the behavior view are similar to those used in the former experiments. We where ρ n is the autocorrelation at lag n. The variable with the higher autocorrelation is µ (f) 0 which has an autocorrelation time of 79. Since we drop the first 15000 samples for burn-in, we get an Effective Sample Size of 189 independent samples.

The bottlenecks of the algorithm are computing the likelihoods of the features and the coefficients given a cluster assignment, and the sampling of the coefficients. The sampling of the coefficients is relatively slow because it implies sampling from a multivariate Gaussian distribution with a U × U covariance matrix (see Appendix). This is due to the fact that the coefficient of each user depends on the coefficients of the users who have co-participated in the same thread. Note that this bottleneck would disappear in other scenarios where the inference of the behavioral function of a user is independent from the other users.

Summary of the experiments

To summarize, the experiments show on the one hand that dual-view models outperform single-view ones when users can be grouped in clusters that share similar features and latent behavioral functions and, on the other hand, that even when this assumption is not true, as long as there is enough data, the inference will lead to a consensual 5.7. Summary partition and a good estimation of latent functions. Indeed, each view acts as a prior, or a regularization factor, on the other view. Good priors improve inference, while bad priors misguide the inferences unless there is sufficient amount of evidence to ignore the prior.

Summary

We presented a dual-view mixture model to cluster users based on features and latent behavioral functions. Every component of the mixture model represents a probability density over two views: a feature view for observed user attributes and a behavior view for latent behavioral functions that are indirectly observed through user actions or behaviors. The posterior distribution of the clustering represents a consensual clustering between the two views. Inference of the parameters in each view depends on the other view through this common clustering, which can be seen as a proxy that passes information between the views. An appealing property of the model is that inference on latent behavioral functions may be used to make predictions of users future behaviors. We presented two versions of the model: a parametric one where the number of clusters is treated as a fixed parameter and a nonparametric, based on a Dirichlet Process, where the number of clusters is also inferred.

We have adapted the model to a hypothetical case of online forums where behaviors correspond to the ability of users to generate long discussions. We clustered users and inferred their behavioral functions in three datasets to understand the properties of the model. We inferred the posteriors of interest by Gibbs sampling for all the variables but two of them which were inferred by Adapted Rejection Sampling. Experiments confirm that the proposed dual-view model is able to learn with less instances than its single-view counterpart due to the fact that dual-view models use more information. Moreover, inferences with the dual-view model based on a Dirichlet Process are as good as inferences with the parametric model even if the latter knows the true number of clusters.

There are some enhancements that can be applied to the model. On the one hand, we can make the inference faster and more scalable by using other inference methods such as Bayesian Variational Inference (for a comprehensible introduction see, for instance [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF]). On the other hand, it may be interesting to consider latent functions at a group level, that is, that users in the same cluster share exactly the same latent behavior (as we considered in Chapter 4). Not only it would reduce the computational cost but, if we have few data about every user, a group-level inference may also be more grounded and statistically sound.

6 Contributions and perspectives

Contributions

In this thesis we set out to automatically detect roles in online discussion forums. We tried to stick as much as possible to the sociological definition of role as the behavioral repertoire characteristic of a person or a position [START_REF] Biddle | Role Theory: Expectations, Identities, and Behaviors[END_REF]. Following this idea, we focused our efforts on conversational behaviors since conversations are the constituent behaviors of a forum. First, we have considered that two users hold the same role if they tend to participate in the same type of conversation. By taking into account their structural position in the motif of the conversation that embeds a post (a neighborhood), we aimed to capture the different ways users contribute to conversations where they participate. Indeed, we were able to showed that we can detect different types of conversationalists.

Secondly, in order to take a more functional approach-in the sense of capturing the functions that drive user behaviors-we considered that two users hold the same role if their replying behavior-their criteria for choosing a post to reply-can be modeled by the same function. Or, more specifically, if their choices can be modeled by the same probability distribution. We showed that not all users behave similarly and that indeed modeling users as members of different subpopulations with different behavioral functions leads not only to a better fit of the data compared to a model that does not consider differences between the individuals -the model is more flexible-but also to better likelihoods in unobserved behaviors. Yet we also showed that this improvement is not enough to make better predictions, which leaves room for improvement of the model.

In an attempt to integrate the former two approaches, we proposed a third dual-view method that opens the door to the integration of features and behavioral functions. In particular, we modeled users features and behaviors as generated from a mixture model of roles, where users in the same component -the same role-have similar features and similar behaviors. We used synthetic data to show the properties of the model. In particular, we showed that a dual-view model can learn with fewer examples than models that use one single view (features as in our first definition, or behaviors as in our second one.).

Roles or not roles?

The aim of this thesis was to detect roles and to prove that these roles can be used as predictors of a user behavior. We showed that conversational behaviors, regarded from a merely structural point of view, are different for different groups of users. We stated that, in order to give these clusters the category of role, they needed to prove their predictive power. There is some evidence in favor of this-an increase in the likelihood of unobserved behaviors-but the evidence is not strong enough and thus we do not dare to claim that we found roles from a grounded sociological basis.

Therefore, the question remains open. Are there predictive roles in online forums? There are certainly some users with a consistent extreme behavior, such as trolls, and specific methods have been proposed by some authors to detect them. Yet a finer-grained taxonomy might not be possible. One can blame the object-users are too random in online conversations, they have too much variance-or the measuring instrument-the method does not capture enough the non-random part. Or one can blame both.

As for the object, it might be good news that humans are not always that predictablealthough, in many aspects, they are; we would have otherwise an army of jobless sociologists, statisticians and machine learners. As for the measure instrument, we propose some possible improvements in the following section.

Perspectives

As mentioned before, the role detection machinery can be improved in many ways. These are left as paths for future research. We divide them in methodological and technical.

Technical

Clustering based on count data

In Chapter 3, we chose hierarchical clustering to compare the clusters for each type of neighborhood and forum. The main object was a matrix of discrete distributions, where each distribution indicates the tendency of a user towards each type of conversation. We recall that, before obtaining that matrix, we had a matrix of counts -how many times a user was seen in each motif. As such, some specific methods can be used to deal with count data. For instance, we might model the vectors of counts as draws from a mixture of multinomial distribution. Then, we would infer clusters of users where users in the same cluster draw their vectors of counts from the same multinomial distribution. This model-based clustering can be easily used as the feature branch of our dual-view model.

A scalable dual-view model

In Chapter 5, we faced a serious problem of scalability in our dual-view model. The reason was two-fold. On the one hand, the need to compute the inverse of a matrix with as many rows and columns as users. This was required during the Gibbs Sampling to get the covariance matrix of the Normal distribution that generates the user coefficients (the matrix Λ ′ -1 to sample from p(b u |•) in the Appendix A.3.1). This problem can be easily avoided if we choose to model individual behaviors instead of collective behaviors (the length of a thread), since the inference of a user parameters would be conditionally independent, given the clusters, of the other users. The behavioral model presented in 4 holds this condition. Unfortunately, its likelihood function has no conjugate priors and thus we could not use Gibbs Sampling to sample the behavioral coefficients (α, β, τ ). Instead, we may use other sampling methods that do not require conjugacy.

On the other hand, Gibbs Sampling and Monte-Carlo methods are easily beaten in speed by Variational Inference methods. Replacing our Gibbs Sampler by a Variational Inference would likely boost the speed considerably. Although we would obtain approximations to the posterior-Variational Inference approximates the posterior with a function that is analytically tractable-the gain in scalability might be worth it.

Methodological

A dictionary of conversations We showed in Chapter 3 that the different neighborhood definitions gave motifs that correspond, without much doubt, to the same type of conversation. Thus, some of them might be considered isomorphic. Even if we might apply a more agressive pruning, we think that a more reasonable solution is to do this task manually so that we obtain a dictionary of meaningful conversational motifs. In other words, an orthogonal-as much as possible-base of conversations.

A better tree growth model

Our model in Chapter 4 considers that each group of users behaves following this behavioral function, borrowed from [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF]: p(π t = i|π 1:(t-1) ) ∝ α z(a(t)) d i + β z(a(t)) r i + τ l i z(a(t)) (6.1) This model assumes that when a user chooses to reply to a post i over the set of posts in a thread, they consider the popularity i, its recency and whether i is the root of the thread. It seems reasonable to assume that the choice also depends on who the author of i is. Some authors, for instance, might have the ability to write particularly interesting posts. Thus, we might consider that clusters are also associated to an interestingness factor and that users in the same cluster write posts with similar levels of interestingness. The likelihood would be: p(π t = i|π 1:(t-1) ) ∝ α z(a(t)) d i + β z(a(t)) r i + τ l i z(a(t)) + η z(i) (6.2)

where γ k would be the interestingness of users in cluster k. Note, however, that this model would increase in K (the number of clusters) the number of parameters. Moreover, we might apply the idea of blockmodeling and consider that the interestingness depends on the groups of both users (the replier and the replied). For instance, everyone might be attracted by posts written by experts, and experts might only be attracted by posts from other experts. If we denote as η k,k ′ the interestingness of posts from group k ′ from the point of view of users in group k, we might express the likelihood as: p(π t = i|π 1:(t-1) ) ∝ α z(a(t)) d i + β z(a(t)) r i + τ l i z(a(t)) + η z(a(t)),z(a(i)) (6.3)

where the number of new parameters is K × K.

Combining structure and text

In this thesis, we took into consideration only the structural aspect of conversations. We claimed that the subtleties of user language are -often-difficult to capture by current algorithms. Yet some textual analysis might be helpful if we combine it with structural analysis presented in this thesis. We might, for instance, detect some basic textual features of the post and add them to the growth model of Chapter 4. An off-topic post, for instance, might be less attractive than a post that uses the key words of a particular forum. The length of a post might also be a good predictor. A basic sentiment analysis of posts to classify them into negative, neutral, and positive may give another feature. In Chapter 3, we might also add textual features to (carefully) increase our dictionary of motifs.

A.2.1 Component parameters

Components means p(µ where: where there is no conjugacy we can exploit. We will sample from this distribution with Adaptive Rejection Sampling.

Λ ′ = Λ a + KR

A.3.4 Regression noise

Let the precision s y be the inverse of the variance σ 2 y . Then:

  Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Online forums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 Vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Forums as graphs . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Role detection in online communities . . . . . . . . . . . . . . . . . . 5 1.3.1 Social sciences . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.2 Blockmodeling . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.3 Feature-based . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.4 Triads and motifs . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.5 Other methods . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Industrial context of the thesis . . . . . . . . . . . . . . . . . . . . . . 13 1.5 Outline of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Figure 2 . 1

 21 Figure 2.1 Posts by day (gaps in figures are missing data).

Figure 2 . 2

 22 Figure 2.2 Thread lengths by day

Figure 2 . 5

 25 Figure 2.5 Distribution of users age by month (boxplots). Means marked by red circles.

Figure 2 . 6

 26 Figure 2.6 User activity. (Top) Distribution of number of posts. (Bottom) Complementary Cumulative Distribution with MLE fits of Power Law (dashed) and Log-normal (solid) distributions.

Figure 2 . 7

 27 Figure 2.7 User lifespans (time between first and last post). (Top) Distribution of lifespans. (Bottom) Complementary Cumulative Distribution.

  a) Size of coparticipation communities. The five biggest communities are shown in the bars. The points indicate the total number of users. Spaces between bars and points correspond to users in smaller communities.

  Size of coparticipation communities when all participations are aggregated to the same graph regardless of their time.

Figure 2 . 8

 28 Figure 2.8 Copartipation communities for three of the forums.

  Figure 2.9 (Top) Threads size distributions. (Bottom) Complementary Cumulative Distribution with MLE fits of Power Law (dashed) and Log-normal (solid) distributions.

Figure 2 .

 2 Figure 2.10 Time from posts to root. Vertical lines mark the first hour, the first day and the first 30 days. Most posts arrive between the first hour and the first day. Conversations are practically over after the first day.

  Figure 2.11 Evolution of triad census over time

  Contents 3.1 Discussion trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2.1 Neighborhood extraction . . . . . . . . . . . . . . . . . . . . . 35 3.2.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3 Radius-based neighborhoods . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.1 Results for radius-based neighborhood . . . . . . . . . . . . . 39 3.4 Order-based neighborhoods . . . . . . . . . . . . . . . . . . . . . . . . 47 3.4.1 Pruning and coloring . . . . . . . . . . . . . . . . . . . . . . . 47 3.4.2 Results for order-based neighborhood . . . . . . . . . . . . . . 48 3.5 Time-based neighborhoods . . . . . . . . . . . . . . . . . . . . . . . . 51 3.5.1 Choice of radius . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.5.2 Results for time-based neighborhood . . . . . . . . . . . . . . 54 3.6 Comparative analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Figure 3 . 1

 31 Figure 3.1 Trees with different local conversation structures.

  (a) Dictionary of motifs sorted by median probability. Boxplots of the entries (probabilities) in the feature vectors (each dot is a user). The red solid line indicates the medians.

Figure 3 . 2

 32 Figure 3.2 Radius-based neighborhoods (r=1)

Figure

  Figure 3.3 Clusters with radius-based neighborhoods (r=1)

  (a) Dictionary of the first motifs sorted by median probability (out of 1269). of the entries (probabilities) in the feature vectors (each dot is a user). The red solid line indicates the medians.

Figure 3 . 4

 34 Figure 3.4 Radius-based neighborhoods (r=2)

  Heatmap of feature matrices re-arranged after clustering. Clusters are labeled by size (1 for the biggest) feature vectors by cluster (three most dominant features). Clusters are labeled by size (1 for the biggest).

Figure 3 . 5 Figure 3 . 6

 3536 Figure 3.5 Clusters with radius-based neighborhoods (r=2)

  Summary of clusters with order-based neighborhoods (r=3). Clusters with similar first and second motif, but different third motif, have been collapsed into a same group (the third motif is marked with an asterisk). The question mark corresponds to the others category.

  (a) Dictionary of the first motifs sorted by median probability Boxplots of the entries (probabilities) in the feature vectors (each dot is a user). The red solid line indicates the medians.

Figure 3 . 7

 37 Figure 3.7 Order-based neighborhoods (r=3)

Figure 3 . 8

 38 Figure 3.8 Clusters with order-based neighborhoods (r=3)

Figure 3 . 9

 39 Figure 3.9 Illustration of time-based neighborhoods. The time-based neighborhood has parameter r = 3. In the time-based neighborhood, horizontal changepoints (yellow) and vertical changepoints (orange) represent posts that are temporally far from their predecessors (siblings or parents) and therefore set the limits of the neighborhood. In this example N T 6 (3) is the subtree induced by {2,4,5,6,10,11,13,14,15,16,18,19}.

  Figure 3.11 Clusters with time-based neighborhoods (r=2)

  Growth models . . . . . . . . . . . . . . . . . . . . . . .

Figure 4 . 1

 41 Figure 4.1 An example of a thread and its parents vector π. π starts at t=1 (π 1 ) because the root (π 0 ) has not parent.

Figure 4 . 3

 43 Figure 4.3 Random graphs for discussion threads[START_REF] Gómez | Modeling the structure and evolution of discussion cascades[END_REF].

m∈Mα

  zn d m + β zn r m + τ lm zn

Figure 4 . 4

 44 Figure 4.4 BIC values in podemos and gameofthrones

Figure 4 . 5

 45 Figure 4.5 Properties of synthetic trees and real trees in podemos

Figure 4 . 6

 46 Figure 4.6 Mean negative log-likelihoods per cluster in the test set (lower is better)

Figure 4 . 7

 47 Figure 4.7 Hits per cluster in the test set

Figure 4 . 8

 48 Figure 4.8 Normalized Ranking Error per cluster in the test set. Boxplots and means (black points).

Figure 4 . 9

 49 Figure 4.9 Normalized Ranking Error by size of thread in podemos

  zu are component parameters common to all users assigned to the same component. The component parameters are given Normal and Wishart priors: µ common to all components. The hyperparameters themselves are given non-informative priors centered at the observed data 1 µ

k

  the indicators z and all the other variables of the two views.• Sample component parameters s conditional on the indicators z and all the other variables of the two views. the indicators z and all the other variables of the two views.

Figure 5 . 2

 52 Figure 5.2 Dataset for agreement between the views. User features (left) and user coefficients (right). Every group (shape) of users has a well differentiated set of features and coefficients.

Figure 5 . 3 Figure 5 . 4

 5354 Figure 5.3 Results for agreement between the views. Comparison of models under different threads/users ratios (50 users and variable number of threads). Means and standard errors over 5 runs.

Figure 5 . 5

 55 Figure 5.5 Posteriors for DP-dual when the two views see a different number of clusters. (a) 10 users and 100 threads. (b) 25 users and 25 threads. (c) 100 users and 10 threads. Figures on the left: examples of posterior distributions of thread length predictions over 100 test threads with 50% and 95% credible intervals in test set with 50 users and 10, 50 and 100 threads. x-axis correspond to threads sorted by their (true) length while yaxis correspond to predicted thread lengths. True lengths are plotted in red (smoothest lines). Figures on the right: examples of posterior pairwise clustering matrices π.x-axes and y-axes correspond to the users. A dark point means a high probability of being in the same cluster. The worst case is (c), which makes a similar clustering to (b) but worse predictions, because the feature view receives misguiding information from the behavior view and the number of threads is not high enough to compensate for it.

Figure 5 . 6

 56 Figure 5.6 Results for disagreement between the views. Comparison of models under different threads/users ratios (50 users and variable number of threads) when the two views see a different number of clusters. Means and standard errors over 5 runs.

Figure 5 . 7

 57 Figure 5.7 Iris dataset. User features (left) and synthetic user coefficients (right)

Figure 5 . 8

 58 Figure 5.8 Results for the iris dataset. Comparison of models under different threads/users ratios (50 users and variable number of threads). Means and standard errors over 5 runs.

Figure 5 .

 5 Figure 5.10 Left: histogram of the number of active clusters estimated by the DP-model in the iris scenario with 50 threads. Right: mean and standard deviations of the number of users assigned to each cluster during the chain. Most users are assigned to the three major clusters and a small group of users is assigned to a fourth cluster.

=

  N µ ′ , Λ ′ -1

N

  (y t |p T b, s y ) = G(υ ′ , ψ ′ ) ) ∝ (β -D + 1) -3/2 exp -D 2(β -D + 1)The Wishart likelihood is:W(S k |β, (βW) -1 ) = (|W|(β/2) D ) β/2 Γ D (β/2) |S k | (β-D-1)/2 exp -y|•) = y(K -3/2) -1/(2e y ) + ln Γ(e y )ln Γ(e y + U )which is a concave function and therefore we can use Adaptive Rejection Sampling. The derivative is: ∂ ∂y ln p(y|•) = (K -3/2) + 1/(2e y ) + e y Ψ(e y )e y Ψ(e y + U )

  Forum dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.1 Posting activity . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.2 Newbies versus oldies . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 User dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.1 Posting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.2 Lifespans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.3 Communities . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Conversation dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.1 Thread size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.2 Thread duration . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.3 Motifs of interaction in threads . . . . . . . . . . . . . . . . . 28 2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

	Forum	Threads	Posts	Users Posts/user
	TwoXChromosomes 120,231 3,690,732 335,740	10.9
	gameofthrones	156,937 3,326,169 278,748	11.9
	podemos	88,815 1,368,457 30,032	45.56
	france MachineLearning -Don't be scared ... it is me. Love you and miss you. 40,967 1,083,957 23,323 46.47 -Wow ... this is so cool! 11,509 114,407 14,572 7.8
	First AOL Instant Message, Jan. 6, 1993 Table 2.1 Datasets used in this thesis. All comments made between 2013 and 2016 in
	Contents five Reddit subforums.
	here are plenty of available datasets for social network analysis. However, forum 2.1 T datasets are mostly conceived for natural language processing, and most of them
	lack the metadata indicating which posts replied to which posts. In this thesis, we have
	explored several datasets:
	• IMDb (http://imdb.com): the IMDb dataset had been internally crawled by Tech-
	nicolor. It contains the discussion threads about the top 100 rated and the bottom
	100 rated films in 2013. Unfortunately, lots of posts on the site have been deleted
	under unknown criteria. In the dataset, these posts have neither text nor parent,
	leaving most trees disconnected and thus difficult to work with. We reported some
	initial research and a discussion around it in Lumbreras et al. (2013).
	• Boards.ie (http://www.boards.ie): boards.ie is an Irish forum organized around
	different subjects such as sports or politics. It was released by the owner company
	at the ICWSM 2012 conference and contains ten years of data. There is no meta-
	data indicating which post replied to which posts, and replies must be inferred
	from text quotations and user mentions in the posts. This is a challenge in itself
	because, among other reasons, the quotation and naming conventions in the forum
	are too open and changing through the years. Research with this dataset includes
	Kan et al. (2013); Angeletou et al. (2011); Chan et al. (2010).

Table 2

 2 Percentage of posts written by new users each month.

	0 6

.2 Number of users with more than 100 and 1000 posts.

  Structural properties . . . . . . . . . . . . . . . . . . . . . . . 74 4.3.4 Link prediction . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

. . 63 4.1.1 Barabasi-Albert (1999) . . . . . . . . . . . . . . . . . . . . . . 64 4.1.2 Kumar et al. (2010) . . . . . . . . . . . . . . . . . . . . . . . 65 4.1.3 Gómez et al. (2010) . . . . . . . . . . . . . . . . . . . . . . . 65 4.1.4 Gómez et al. (2012) . . . . . . . . . . . . . . . . . . . . . . . 66 4.2 A new role-based network growth model . . . . . . . . . . . . . . . . 67 4.2.1 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.2.2 Expectation-Maximization for the role-based growth model . 68 4.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.3.1 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.3.2 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.3.3

Table 4

 4 Table 4.2 and Table 4.3. All clusters have different parameters than gomez, meaning that not all users have behaved similarly in our training set. For instance, members of cluster 6 in podemos and members of cluster 8 in gameofthrones show a extremely high tendency to reply to root posts (high β). Another detected group with an extreme behavior is the cluster

	cluster α	β	τ	π	users
	0.03 1.48 0.69 0.12 121
	0.02 3.63 0.73 0.09	92
	0	3.92 0.95 0.02	21
	0.01 1.00 0.78 0.13 135
	0.14 4.31 0.95 0.02	23
	0.05 76.26 0.81 0.06	56
	0.1 13.24 0.83 0.12 118
	0.13 8.08 0.95 0.06	64
	0.03 4.22 0.87 0.13 129
	0.01 0.39 0.56 0.06	52
	0	1.35 0.9 0.02	21
	0	0.18 0.69 0.07	66
	0.03 1.29 0.88 0.07	69
	0.22 2.52 0.99	0	8
	0.01 0.83 0.96 0.01	16
	Gomez 0.00 3.58 0.93	-
	Table 4.2 Estimated paramaters for podemos
	cluster α	β	τ	π	users
	0.1 0.66 0.96 0.08	89
	0.14 2.27 0.93 0.06	59
	0.59 4.49 0.99 0.02	26
	0.03 0.81 0.98 0.12 114
	0.02 1.09 0.91 0.13 131
	0.1 2.70 0.78 0.06	62
	0.1 3.39 0.99 0.05	54
	0.01 81.89 0.98 0.03	26
	0.03 2.84 0.8 0.08	77
	0	4.12 0.99 0.04	39
	0.4 12.16 0.95 0.02	19
	0.07 9.05 0.85 0.05	54
	0	0.1 0.43	0	8
	0.02 0.93 0.76 0.13 128
	0.06 5.13 0.96 0.12 120
	Gomez 0.06 2.71 0.93	-

.3 Estimated paramaters for gameofthrones

Chapter 4 and Chapter 5 also include a State of Art specific to the chapter. We avoided presenting them in the current chapter in order to give them in their proper contexts.

We use Ward linkage, although it is possible to use other distances and clustering methods.

An implementation of this algorithm written by the authors themselves is available in the R library changepoint. We use their cpt.meanvar function.

We denote as zn the cluster of the author of post n in order to be consistent with the literature as well as with our following section and our following chapter. This should not be confused with Zt, which refers to the normalization factor. Nevertheless, this normalization factor will not appear any longer.

In general, f (E[X]) ≥ E[f (X)]where f is a concave function.

We also computed the Akaike Information Criteria (AIC), defined as AIC = -2L+2np and obtained similar curves.

Note that the expectation of a random matrix drawn from a Wishart distribution X ∼ W(υ, W ) is E[X] = υW. Our parametrization of the Gamma distribution corresponds to a one-dimensional Wishart. Its density function is therefore given by G(α, β) ∝ x α/2-1 exp(-x

2β ) and the expectation of a random scalar drawn from a Gamma distribution x ∼ G(α, β) is E[x] = αβ.

Remerciements

Authors p(π t = k|π 1:t-1 ) ∝ Parameters [START_REF] Barabási | Emergence of scaling in random networks[END_REF] d α k,t degree [START_REF] Gómez | Modeling the structure and evolution of discussion cascades[END_REF] (β k d k,t ) α k degree, root [START_REF] Kumar | Dynamics of Conversations[END_REF] αd k,t + τ t-k degree, recency [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF] β k + αd k,t + τ t-k degree, recency, root threads [START_REF] Kumar | Dynamics of Conversations[END_REF][START_REF] Gómez | Modeling the structure and evolution of discussion cascades[END_REF][START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF]. Then we present our model, which finds k sets of parameters for k types of user and is based on [START_REF] Gómez | A likelihoodbased framework for the analysis of discussion threads[END_REF].

In the following sections, we describe the growth models that have been proposed to explain the growth of online conversations. A summary is shown in Table 5.1.

4.1.1 Barabasi-Albert (1999) The preferential attachment model proposed by [START_REF] Barabási | Emergence of scaling in random networks[END_REF] is the best known growth model. The Barabasi-Albert model builds a graph by sequentially adding its vertices. Once a new vertex t is added to the graph it decides whether to create an edge to an existing vertex i with probability

where d i,t is the degree of the vertex i before vertex t is added. The particular cases of α = 1, 0 ≤ α < 1 and α < 0 are known as linear, sublinear and anti preferential attachment. This model reproduces a rich-get-richer phenomena controlled by the parameter α. Graphs generated by the Barabasi-Albert model reproduce some interesting properties of the real networks such as a power-law distribution of the vertices degrees.

Kumar et al. (2010)

In [START_REF] Kumar | Dynamics of Conversations[END_REF], the authors propose a model that combines both preferentialattachment and recency. The higher the degree of a post and the later it was published, the easier for this post to attract the incoming replies. Besides, at every time step, a decision is made to stop the thread or to add a new post. Every new post chooses its parent according to:

and the probability of stopping the thread is:

The authors report that when the alternative function d i,t τ t-i is used, the recency factor prevents the preferential attachment factor from generating heavy-tailed degree distributions. The normalization factor is:

where 2(t -1) is the sum of degrees (in-degrees and out-degrees) in a tree of size t and the third term is the result of a geometric series.

The authors also propose an improvement of the model to account for the identity of post authors. For a new post v replying to a post u, its author a(v) can be either a(u) (a self-reply), another author a(w) that has already participated in the chain from u to the root, or some other new author belonging to the set of authors A that have not participated in the chain:

with probability γ a(u)

with probability ǫ a ∈ A with probability 1γǫ (4.7)

The Maximum Likelihood Estimators of the parameters α, τ, γ, ǫ are found by a grid search. The authors show that this model properly reproduces the relationship between size and depth of the trees, the degree distribution at different depths, and the number of unique authors as a function of the thread size in Usenet forums.

Gómez et al. (2010)

In [START_REF] Gómez | Modeling the structure and evolution of discussion cascades[END_REF], the authors combine preferential-attachment with a bias towards the root. The probability of choosing an existing parent k is

Behavior view

In this section we specify the component parameters θ of the behavior view. Our choice corresponds to a Bayesian linear regression where coefficients are drawn not from a single multivariate Gaussian but from a mixture of one-dimensional Gaussians.

The thread lengths are assumed to come from a Gaussian distribution whose mean is determined by the catalytic power of users who participated in the first posts and whose variance represents the unknown level of noise:

where the precision s y is given a Gamma prior centered at the sample precision σ -2 0 :

The power coefficients b u come from a mixture of Gaussians:

(5.17)

where the mean µ

zu and the precision s

zu are component parameters common to all users assigned to the same component z u . The component parameters are given Normal and Gamma priors:

where the mean µ (f) 0 , the precision r (f) 0 , the variance w (f) 0 , and the degrees of freedom β (f) 0 are hyperparameters common to all components. Because the coefficients are not observed, we cannot center the hyperparameters in the data as we did in the feature view. Instead, we use their Maximum Likelihood Estimates, computed as b = (PP T + λI) -1 P T y, with a regularization parameter λ = 0.01, where P is the participation matrix P = {p 1 , ..., p T }. Then the hyperparameters are given non-informative priors centered at b:

where µ b and σ 2 b are the mean and the variance of the Maximum Likelihood Estimators b of the coefficients. Note that this choice is data-driven and, at the same time, the risk of overfitting is reduced since hyperparameters are high in the model hierarchy.

not systematically benchmark the two initialisation strategies. Nevertheless, this second strategy is, in general, more convenient in order to arrive to the true target distribution within less iterations.

Metrics

We used two metrics for evaluation, one for clustering (within dual models) and one for predictions of thread lengths (within the three models).

Metric for clustering: Clustering by mixtures models suffers from identifiability. The posterior distributions of z has k! reflections corresponding to the k! possible relabelling of the k components. Due to this, different MCMC samples of z may come from different reflections making it hard to average the samples. A common practice is to summarize the pairwise posterior probability matrix of clustering, denoted by π, that indicates the probability of every pair of users to be in the same component (no matter the label of the component). In order to obtain a full clustering z from π, [START_REF] Dahl | Model-based clustering for expression data via a Dirichlet process mixture model[END_REF] proposes a least-squares model-based clustering which consists of choosing as z the sample z (i) whose corresponding pairwise matrix has the smaller least-squares distance to π:

where δ i,j (z) indicates whether i and j share the same component in z. Finally, to assess the quality of the proposed clustering z LS we use the Adjusted Rand Index, a measure of pair agreements between the true and the estimated clusterings.

Metric for predictions: For predictions, we use the negative loglikelihood, which measures how likely the lengths are according to the predictive posterior:

p(y test |p test t , P train , y train ) (5.30) and that can be approximated from Equation 5.28. Negative loglikelihoods are computed on test sets of 100 threads.

Agreement between views

To set up the first scenario, for a set of U users and five clusters we generated an assignment z u to one of the clusters so that the same number of users is assigned to every cluster. Once all assignments z had been generated, we generated the data for each of the views. For the feature view, every user was given a two-dimensional feature vector a u = (a u 1 , a u 2 ) T drawn independently from: 5.31) where µ zu = cos(2π zu 5 ), sin(2π zu 5 )

T for z u = 1, .., 5 (see Figure 5.2). For the behavior view, every user was given a coefficient drawn independently from:

where coefficients for users in the same cluster are generated from the same Normal distribution and the means of these distributions are equidistantly spread in a [-200,200] interval (see Figure 5.2). To simulate users participations in a forum we generated, for each user u, a binary vector p u = (p u1 , ..., p uT ) T of length T that represents in which threads the user participated among the first m posts. We supposed each user participated in average in half the threads.

p ut ∼ Bernoulli(0.5) (5.33)

Finally, we assumed that the final length of a thread is a linear combination of the coefficients of users who participated among the first posts:

If both views agree and there is enough data for both of them, we expect dual models to find the true clusters and true latent coefficients, and the single model to find also the true latent coefficients. In this case, the feature view brings no competitive advantage when there is enough information in the behavior view (and conversely, dual models should not outperform simple IGMM and GMM for the clustering task since there is enough information in the feature view).

On the contrary, when one of the views lacks information, then dual-view models should outperform single-view ones. In our model, the lack of information may come A Conditional distributions for the dual-view mixture model

A.1 Chinese Restaurant Process

In this section we recall the derivation of a Chinese Restaurant Process. Such a process will be used as the prior over cluster assignments in the model. This prior will then be updated through the likelihoods of the observations through the different views.

Imagine that every user u belongs to one of K clusters. z u is the cluster of user u and z is a vector that indicates the cluster of every user. Let us assume that z u is a random variable drawn from a multimomial distribution with probabilities π = (π 1 , ..., π K ). Let us also assume that the vector π is a random variable drawn from a Dirichlet distribution with a symmetric concentration parameter α = (α/K, ..., α/K). We have:

The marginal probability of the set of cluster assignments z is:

where n i is the number of users in cluster i and B denotes the Beta function. Noticing that the integrated factor is a Dirichlet distribution with concentration parameter α + n but without its normalizing factor:

which expanding the definition of the Beta function becomes:

where U = K i=1 n i . Note that marginalizing out π we introduce dependencies between the individual clusters assignments under the form of the counts n i . The conditional distribution of an individual assignment given the others is:

To compute the denominator we assume cluster assignments are exchangeable, that is, the joint distribution p(z) is the same regardless the order in which clusters are assigned. This allows us to assume that z u is the last assignment, therefore obtaining p(z -u ) by considering how Equation A.1 before z u was assigned to cluster j.

And finally plugging Equations A.3 and A.1 into Equation A.2, and cancelling out the factors that do not depend on the cluster assignment z u , and finally using the identity aΓ(a) = Γ(a + 1) we get:

where n -j is the number of users in cluster j before the assignment of z u .

The Chinese Restaurant Process is the consequence of considering K → ∞. For clusters where n -j > 0, we have:

and the probability of assigning z u to any of the (infinite) empty clusters is:

where p is the number of non-empty components. It can be shown that the generative process composed of a Chinese Restaurant Process were every component j is associated to a probability distribution with parameters θ j is equivalent to a Dirichlet Process.

A.2 Conditionals for the feature view

In this appendix we provide the conditional distributions for the feature view to be plugged into the Gibbs sampler. Note that, except for β

where there is no conjugacy we can exploit. We may sample from this distribution with Adaptive Rejection Sampling.

A.3 Conditionals for the behavior view

In this appendix we provide the conditional distributions for the behavior view to be plugged into the Gibbs sampler. Except for β b 0 , conjugacy can be exploited in every case and therefore their derivations straightforward and well known. The derivation for β b 0 is left for another section:

A.3.1 Users parameters

Users latent coefficient p(b u |•):

Let Z be a K × U a binary matrix where Z k,u = 1 denotes whether user u is assigned to cluster k. Let I [T] and I [U] identity matrices of sizes T and U , respectively. Let

K ) Then:

where:

A.3.2 Component parameters

Components means p(µ

where:

Components precisions p(s

where:

A.3.3 Shared hyper-parameters

Shared base mean p(µ

where:

where:

Shared base degrees of freedom p(β

We multiply both equations, the Wishart likelihood (its K factors) and the prior, to get the posterior:

and its logarithm is: where Ψ(x) is the digamma function.

A.5 Sampling β (f ) 0

For the behavior view, if

the posterior of β is: where Ψ(x) is the digamma function.

A.6 Sampling α

Since the inverse of the concentration parameter α is given a Gamma prior

we can get the prior over α by variable transformation: p(α) ∝ α -3/2 exp (-1/(2α))

Multiplying the prior of α by its likelihood we get the posterior:

∝ α K-3/2 exp (-1/(2α)) Γ(α) Γ(α + U ) Then if y = ln α: p(y|•) = e y(K-3/2) exp(-1/(2e y ))

Γ(e y ) Γ(e y + U )