Xiaoliang Fan
email: xiaoliang.fan@gmail.com

Patrick Brézillon

Ruisheng Zhang

Lian Li

Context-oriented scientific workflow system and its application in virtual screening

Keywords: Context, scientific workflow system, decision making, grid computing, virtual screening

Context-oriented scientific workflow system and its application in virtual screening

Introduction

Scientific workflow (SWF) system is a specific workflow management system applied to science arena, and it concerns with the automation of scientific processes in which scientific tasks are orchestrated based on their control and data dependencies [START_REF] Altintas | Kepler: an extensible system for design and execution of scientific workflows[END_REF][START_REF] Ca Goble | myExperiment: social networking for workflow-using e-scientists[END_REF]. For years, SWF systems are widely applied to many applications, namely in physics, climate modeling, drug discovery process, and disaster recovery simulation [START_REF] Yu | A Taxonomy of Scientific Workflow Systems for Grid Computing. In special issue on Scientific Workflows[END_REF][START_REF] Zhang | Extending BPEL2.0 for Grid-Based Scientific Workflow Systems[END_REF].

Computational science [START_REF] Roache | Verification and validation in computational science and engineering[END_REF], such as virtual screening [START_REF] Kitchen | Docking and scoring in virtual screening for drug discovery: Methods andapplications[END_REF], is an exploratory, flexible, and knowledge-intensive one that it is always re-done in an evolutionary pattern. However, contemporary SWF systems fail to address such dynamics and variables when scientists urge to deliver new outcomes through reproduction of SWF, including not only SWF representation and data provenance, but also its "context" of use. Main reason for such failure is due to the lack of representing and managing the context, defined in [START_REF] Brézillon | Characteristics of context[END_REF] as "which constrains something without intervening in it explicitly". For scientists, a new result modifies the context of their decision making process. Thus, it is important for them to accounting for context. If not handling the context during the scientific discovery, SWF system could not shift itself to a practice to address the specific focus and context of the scientist.

We propose a context-oriented SWF system along a user-centered approach. Context can be associated with SWF in three main ways. Firstly, in the usual way, there is a library of SWFs, and context acts as an interface (middleware, context-aware system, etc.) to determine which SWF should be chosen from the library under a specific focus of the user. In the second way, context supports the assembling of components of the SWF, which must be recompiled each time. Thirdly, context is expressed by context graphs (CxGs), combined with SWF representation according to contextual elements (CEs), which will enrich the SWF representation, enhance its flexibility, and help to make a better decision for scientists.

Making "context" explicit in SWF system would formalize scientists' research, strategies, and customization information, where elements of knowledge, of reasoning and of contexts are represented in a uniform way. We describe series of feedbacks from interviews of multi-national virtual screening scientists, and illustrate a case study in virtual screening. We generalize groups of contextualized information and model them by contextual graphs. Finally, we conclude that the potentials of intelligently sharing workflow with its context would make scientific workflow as a complementary of paper-based publications.

Hereafter, the paper is organized in the following way. Section 2 presents the problem addressed in scientific discovery and why current SWF systems fail to address the dynamic challenges. Section 3 discusses and comments briefly previous works on context-based applications in order to point out what are reusable while problems remain to solve for SWF flexibility. We then propose our context-orient SWF solution in Section 4. Section 5 presents a case study in virtual screening. The general conclusion and future work in Section 6 closes the paper.

Problem Addressed

We are in the era of data-centric scientific research, in which hypotheses are more and more generated by combining and mining the pool of data already available [START_REF] Hey | The Fourth Paradigm: Data-Intensive Scientific Discovery[END_REF]. However, current SWF systems fail to address such challenge for the following reasons:  Lack of "Context". Current SWF systems are not capable of making the "context" of the case (including task at hand, environment, user's mood, etc.) accessible to scientists. SWF shifts scientific procedural, but without representation and management of context, the procedural could not shift itself to a specific practice to address current focus of the scientist.  Inflexible decomposition of workflow representation. SWF is not atomic for the user, who needs to carry out the actual work at a much more "fine-grained" level, such as "changing the parameters whenever needed in real-time".  Push oriented perspective. Most SWF systems force scientists to do what they are obliged to do rather than what they are able to do in a unique context. Such a "push" way gives rise to inflexible practices, and blocks the decision-making process.  Sharing of SWF representation is far from enough. Smart and intelligent rerun of SWF automatically is urged by scientists to deliver new outcomes when fresh data with new context become available [START_REF] Hey | The Fourth Paradigm: Data-Intensive Scientific Discovery[END_REF].

Related Works

Context has been playing an important role in a number of decision making domains for a long time. Context-based intelligent assistant system, a new generation of system which combines the strengths of knowledge based system with those of intelligent decision-making assistant system, has successful applications in diagnosis of equipment for EDF, French national power company [START_REF] Brézillon | Diagnostic basé sur un modèle des systèmes de contrôle dans les postes des réseaux d'énergie: l'expérience SEPT[END_REF], incident management on the subway [START_REF] Brézillon | SART: An intelligent assistant for subway control, Pesquisa Operacional[END_REF], contextualization of a social network [START_REF] Brézillon | Context and virtual communities in a firm[END_REF][START_REF] Brézillon | Task-realization models in contextual graphs[END_REF], medical image retrieval [START_REF] Brézillon | A Context Model for Content Based Medical Image Retrieval[END_REF], etc.

The need for flexibility and dynamicity in scientific workflow have long been recognized as a critical issue to adapt to changing circumstances of scientific discovery. A variety of artificial intelligence techniques have been brought to bear for intelligent SWF representation and automation, while guaranteeing data quality:

 [START_REF] Gil | From data to knowledge to discoveries: Artificial intelligence and scientific workflows[END_REF] discusses the need to assist scientists at a higher level that requires capturing and exploiting scientific knowledge about the software and data used in computational experimentation. WINGS [START_REF] Gil | Wings for Pegasus: Creating Large-Scale Scientific Applications Using Semantic Representations of Computational Workflows[END_REF] also presents the idea of reasoning with SWF at the knowledge level using ontologies and rules.  myExperiment [START_REF] Ca Goble | myExperiment: social networking for workflow-using e-scientists[END_REF] enables social networking around SWFs in bioinformatics applications, builds up a SWF repositories, and provides community support for social tagging, comments, ratings and recommendations by adopting content-sharing tools and other Web 2.0 technologies.  DECLARE [START_REF] Van Der Aalst | Declarative workflows: Balancing between flexibility and support[END_REF] identifies three flexibility mechanisms for workflow, which could suspend the decision makings, change or ignore the workflow representation separately when needed in a flexible way.  MOTEUR [START_REF] Glatard | Flexible and efficient workflow deployement of data-intensive applications on grids with MOTEUR[END_REF] presents a novel scientific workflow system combining an userfriendly workflow representation with flexible and efficient execution strategies, such as enabling dynamic extension of the data sets.

However, it is more and more proven that the general approach doesn't work well, because of not closely working with the user. A context-oriented approach will not only make use of previous success of context-based intelligent assistant systems, such as capturing contextual information through context graphs, but also work closely with scientists to promote intelligently share of SWFs through the process of incremental knowledge acquisition. One contribution also embraces making available a tool for teaching virtual screening because students (Master and Ph.D) will know which methods can be used at one step and the rationale (i.e. the contextual elements) for the choice of any methods. Further more, this work has been carried out in an international-level cooperation with virtual screening scientists from both France and China.

Proposed Context-oriented Approach

We propose a context-oriented solution and believe that making "context" explicit in scientific workflow system could promote a SWF more adaptive to the dynamic environment and enhance its intelligence to facilitate an effective decision-making. This results following key features of context-oriented SWF system:

 "Context" is the essential element for each scientist to represent his/her own "practice" (which is considered as the contextualization of "procedure") in a SWF, to address a focus in a given context.

 An "experience-based knowledge base" is designed and built, and the knowledge base is enriched and modified through a process of incremental knowledge acquisition.  An interface is developed for acquisition and management of the "experiencebased knowledge base" .  The solution should be a user-centered one, that less "push" but more "participating" and "interactive" oriented SWF is represented. Applying scientific workflow to improve decision making outcomes in virtual screening is a very difficult issue. On one hand, workflow represents a compilation of well-established procedures, robust and usable in a number of domains. On the other hand, virtual screening is a domain where there is no unique solution but a very large number of solutions that depend on a number of factors specific of products, molecule, situation, software, environment, etc. Representing these factors as contextual elements, then assembling contextual elements as contextual graphs, seems to be the first priority for approaching a complete representation of SWF and make available an experiencebased knowledge base. Our recent achievement is mainly presented in a case study.

Case Study

Background

Virtual screening scientist published their finding on crystal structure of "Polymerase PA C -PB1 N complex from an avian influenza H5N1 virus" in Nature [START_REF] He | Crystal structure of the polymerase PA(C)-PB1(N) complex from an avian influenza H5N1 virus[END_REF][START_REF] Yuan | Crystal structure of an avian influenza polymerase PAN reveals an endonuclease active site[END_REF], considered as the first successful result of drug discovery research on avian influenza H5N1 virus. "PA C " is a protein, which is a kind of H5N1 virus, and its toxicity will only take effect when combining with a small molecule called "PB1 N ". In general, this research aims to find dozens of molecules from millions of molecules in ZINC database [START_REF] Irwin | ZINC:A Free Database of Commercially Available Compounds for Virtual Screening[END_REF], which could best block the binding between PA C and PB1 N . As a result, the viral replication of H5N1 is abolished, hereafter "dozens of molecules" become candidates for anti-H5N1 drug. Based on this finding, we are running a project entitled "Virtual screening research on polymerase PA C ", which aims to dock [START_REF] Chen | Molecular docking and ligand specificity in fragment-based inhibitor discovery[END_REF] about 7.7 million small molecules separately on PA C . The application is not only a time-consuming one in which millions of computings are expected to perform by docking software (such as Dock 6.0), but also a very flexible one that there is no unique solution for each computings because they vary from each other on selecting docking software.

In order to address such flexibility challenges, we believe the starting point should be a representation of scientists' workflow in formalism where elements of knowledge, reasoning and contexts are represented in a uniform way. Hence, we firstly generalize feedbacks on procedurals and decision making processes of virtual screening research, through questionnaires to scientists in Section 5.2. Then we make interviews to scientists on detailed information during their research, through which contextualized information, or known as contextual elements (CEs), are obtained in Section 5.3. Further more, we begin to use context graphs (CxGs) to model the CEs and preliminary result is presented in Section 5.4.

Feedbacks from Virtual Screening Scientists

Through questionnaires to several scientists, we get the knowledge that there are mainly two rounds of screenings for virtual screening research:

 First round screening aims to perform rigid docking between millions of molecules and the protein separately.  Second round screening selects higher-score molecules (about 10% of total molecules) after the first round screening, and performs flexible docking between selected molecules and protein separately.

More in detailed, we present the general steps, including decision makings process, of "protein preparation", which is a very important portion of virtual screening during the first round screening:

Step 1. Name the targeted protein (PA C ) and get its structure.

Step 2. Execute the necessary preparation works:

Step 2.1 remove unrelated molecular (such as water);

Step 2.2 add hydrogen and charge;

Step 2.3 optimize the protein (PA C ), etc. Step 3. Locate the binding site of protein (PA C ) iteratively:

Step 3.1

 Perform the docking calculation between the protein (PA C ) and PB1 N ,  Get its RMSD value (RMSD_0, in chemoinformatics, RMSD is a measure of the distance between a crystal structure conformation and a docking result),



Results Generalized through Interviews

Based on the feedbacks from scientists, we make interviews on detailed information during their research, through which two results are generalized:

1 st result: Virtual screening is an adaptive research, and computing is always redone in a repeatable and evolutionary pattern. There are two aspects for the 1 st result:

 Scientists always ignore or add a portion of SWF when re-executing the SWF. For example, during the first-round screening, scientists firstly do the "protein preparation" for PA C . But during the second-round, there is no need to repeat such step for the new SWF, because the same protein will be performed. Another example, second-round screening would be flexible docking. Thus, they add a new step in the second-round called "protein optimization".  Modifying the parameters is a necessity when performing a new-round of screening. For example, in the second-round, they change the parameter from "flexible = NO" to "flexible = YES", because it is the time to do a precise and flexible screening. The reason behind this sort of modification, is mainly due to updating the research objectives, such as computing budget, how much time they have, etc.

2 nd result: Sharing of SWF means not only to share of representation, but also to share of "context". There are two aspects for the 2 nd result:

 It is necessary to distinguish virtual screening computings under various "contexts". Once, we preform two computings, one to local computer in Lanzhou University, the other to a distributed computer in Tsinghua University in Beijing. We thought two computings should be finished at the same time. But it turned out that the latter one is finished 3 weeks after the former one, because the latter computer has only one CPU while the former one is a cluster with 64 CPUs. Similar accident happened when working on different version of software (Dock 5.0 works differently from Dock 6.0). Obviously, such lessons learnt indicates that the "context" of use is missing.  "Context" plays a very important role in two ways of SWF sharing.

Firstly, sharing of SWF with context is considered as a complementary part of the paper-based publication. Other scientists would evaluate your hypothesis in a much more precise way by re-executing the SWF when the context is met.

In second way, it enables the reproduction, transformation, and evolution of other's "old" SWF to your brand "new" one. Take virtual screening on H5N1 virus for example, since H5N1 virus shares a general structure with H1N1 virus (95% similarity, through the protein sequence analysis of RNA polymerase PAc between H5N1 and H1N1), it is possible to share SWF representation of H5N1 virtual screening with H1N1 researchers. These results generated through interviews, is vital to the extraction of contextual information as contextual graphs, which promotes a user-centered approach of decision-makings for virtual screening scientists.

Modeling SWF with Contextual Graphs

The piece of software Contextual Graphs (CxGs) is presented, explained and available at www.cxg.fr. A contextual graph represents the different ways to solve a problem. It is a directed graph, acyclic with one input and one output and a general structure of spindle. A path in a contextual graph corresponds to a specific way (i.e. a practice) for the problem solving, represented by the contextual graph. It is composed of elements of reasoning and of contexts, the latter being instantiated on the path followed (i.e. the values of the contextual elements are required for selecting a branch, i.e. an element of reasoning among several ones). Figure 1 provides the definition of the elements in a contextual graph (actions, contextual elements, sub-graphs, activities and temporal branching). A more complete presentation of this formalism and its implementation can be found in [START_REF] Brézillon | Task-realization models in contextual graphs[END_REF].

As a result, from Figure 2 to Figure 3, then to Figure 4 (right), contextual graphs in different granularities work together to represent the virtual screening process. Further more, through the comparison in Figure 4, we could easily conclude that contextual graphs provide a uniform representation of elements of knowledge, of reasoning, and of contexts, in which SWF dynamic and flexibility is expressed in a clear way:

 Before the contextual graphs was corresponding to SWF representation (Left picture of Figure 4), SWF is rigid as several pieces of components assembled with sequence of input data (Unprepared_protein), workflow component (Protein_preparation), and output data (Prepared_protein). However, the virtual screening research is a flexible one that scientists could not afford to re-design the representation every time when trivial changes (caused by the change of context) is urged for a reproduced SWF. By introducing contextual graphs (Right picture of Figure 4), scientists could easily model flexibilities and decision-makings in contextual elements, which would control the assembly of ignoring or adding a portion of SWF whenever needed.  Further more, when CxGs are included in the workflow compilation, the value of contextual element will lead to invoking a certain workflow component, which enables multi-outputs of decision-making process. For example, such outputs of whether to invoke Activity 13 (right picture of Figure 4) or not, is manipulated by Contextual element 7. The power of contextual graph has not yet come (at least not directly) in the designing phase of context-oriented SWF systems, but it is considered as an important and useful tool to assist the user in reacting quickly when facing with unexpected circumstances during the decision making process. To enhance this function, it is expected to immigrate the merits of contextual graphs with current scripts of SWF representation (such as BPEL [START_REF] Ca Goble | myExperiment: social networking for workflow-using e-scientists[END_REF]).

Conclusion and Future Work

Virtual screening research is an adaptive research, and decisions are always re-made in a repeatable and evolutionary pattern. Unfortunately, current scientific workflow systems fail to adapt such dynamicity and variables.

The potential benefits of making "context" explicit in SWF system will:  represent and formalize virtual screening scientists' idea, strategy, knowledge, and reasoning in a uniform way;  encourage "sharing of SWF and data under a specific context" within scientific communities, as a complementary form of research outcome, which should be curated and archived along with paper-based publications (see recent Nature's Editorials on "Data sharing" [START_REF] Paul | Post-publication sharing of data and tools[END_REF], and huge success of myExperiment project [START_REF] Gil | Wings for Pegasus: Creating Large-Scale Scientific Applications Using Semantic Representations of Computational Workflows[END_REF]).

Context-oriented SWF open the door to significant new capabilities for automated scientific discovery and reasoning over data, knowledge, and discovery. Applying scientific workflow to virtual screening is a very difficult attempt. Representing dynamicity and flexibility as contextual elements, then assembling contextual elements as contextual graphs, seems to be the first priority for approaching a complete representation of SWF. The association of such a context model with scientific workflows, would lead to an efficient use of a robust method in virtual screening once not formalized at all. As soon as we get enough contextualized information during virtual screening, next step would use contextual graphs to build up an experience-based knowledge base for the context-oriented SWF systems. It is also vital to get more and more computational scientists (such as virtual screening scientists) and distributed computing scientists (such as grid/cloud computing) involved in this inter-discipline area to promote collaborations in a shared context. We believe that, "data-centric" and "knowledge-intensive" are not competitive but complementary for accelerating the pace of scientific discovery, such as virtual screening.

  Compare the conformation of PB1 N before the docking, with the new one after the

		docking;
	Step 3.2
		Do the first round virtual screening of protein (PA C ) with 1000 ligands,
		Get the RMSD value separately (RMSD_1, … , RMSD_1000);
	Step 3.3 compare the value of RMSD_0 with RMSD_1, …, RMSD_1000;
	Step 3.4 Is the result good?
		If "YES" (two indicators: conformations of two PB1

N mentioned in Step 3.1 are similar, and the difference between the value of RMSD_0 and Minimum{RMSD_1, ..., RMSD_1000} is not huge), then choose this binding site as the one which will be used in the large-scale docking process later (with million of ligands).  if NOT, re-configure the parameters and re-do Step 3.1, Step 3.2, Step 3.3 (iteratively if necessary), until the answer of Step 3.4 is "YES".

Acknowledgment

This work is supported by National Natural Science Foundation of China (90912003, 60773108, 90812001), Ministry of Science and Technology of China (2005DKA64001), and China Scholarship Council (2008618047).

We begin to use CxGs to model our case study in virtual screening. Generally speaking, as Section 5.2 indicated, there are two rounds of virtual screening. However, the exception exists, which is demonstrated in Figure 2. By interview, scientist first proposes a question whether there are less than 100 thousands molecules [START_REF] Altintas | Kepler: an extensible system for design and execution of scientific workflows[END_REF]. If so, scientist could ignore the first phase of rigid docking and directly move to the flexible docking [START_REF] Brézillon | Diagnostic basé sur un modèle des systèmes de contrôle dans les postes des réseaux d'énergie: l'expérience SEPT[END_REF]. Else, there are more than 100 thousands molecules, it is necessary to do the two rounds of screening separately (3, and 4). Finally, when the screening is finished, scientist will analyze the result [START_REF] Brézillon | Task-realization models in contextual graphs[END_REF]. In our case study, scientist has 7.7 millions molecules, so the path of "1→3→4→5" is followed. Figure 3 shows what happens inside "first-round rigid screening" (Activity 3 in Figure 2). In our case, scientist performs first-round screening between each molecule and Polymerase PA C , separately. Firstly, check if it is a rigid screening (2). If "No", quit for checking again (3); if "Yes" then do the following: prepare the protein (1), then locate the binding site [START_REF] Yu | A Taxonomy of Scientific Workflow Systems for Grid Computing. In special issue on Scientific Workflows[END_REF], and perform the docking [START_REF] Brézillon | A Context Model for Content Based Medical Image Retrieval[END_REF]. Later, by analyzing the result of first-round rigid screening (4), select the top-scorer molecules and store them for second-round screening (5). Figure 4 shows the comparison between SWF representation of "protein preparation" without introduction of context (Left), and contextual graph of "protein preparation" (Right, Activity 1 in Figure 3).


F Nel

M.-J Lesot

P Capet

T Delavallade

Information Propagation on the Web: Data Extraction, Modeling and Simulation

This paper proposes a model of information propagation mechanisms on the Web, describing all steps of its design and use in simulation. First the characteristics of a real network are studied, in particular in terms of citation policies: from a network extracted from the Web by a crawling tool, distinct publishing behaviours are identified and characterised. The Zero Crossing model for information diffusion is then extended to increase its expressive power and allow it to reproduce this variety of behaviours. Experimental results based on a simulation validate the proposed extension.

Introduction

The study of information diffusion on the Web is based on models of the information propagation mechanisms. Many are transpositions of biological models of disease propagation [START_REF] Gruhl | Information diffusion through blogspace[END_REF][START_REF] Adar | Tracking information epidemics in blogspace[END_REF][START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF][START_REF] Java | Modeling the spread of influence on the blogosphere[END_REF][START_REF] Leskovec | The dynamics of viral marketing[END_REF], others propose to imitate the process of information publishing in an intuitive and adaptable way, as the zero-crossing (ZC) model, based on random walks [START_REF] Goetz | Modeling blog dynamics[END_REF].

In this paper we propose a general information propagation model that goes beyond blogs, to the Web in general, following an imitation principle based on an extension of the ZC model. It aims at reproducing an observed variety of publishing behaviours, e.g. taking into account the differences between blogs and journal websites. Publishing behaviours are defined both in terms of general characteristics, e.g. the global publication amount, and more specifically in terms of citation policies, e.g. use and diversity of hyperlinks.

To that aim, as described in Section 2, we first identify and characterise four distinct and contrasted publication and citation patterns, from the study of a source network extracted from the Web by a crawling tool. Section 3 then presents the proposed model, defined as an extension of the ZC model: it describes additional parameters and their semantics, proposed to allow it to reproduce this variety of behaviours. Section 4 lastly presents the simulation performed to validate the proposed model through the comparison between the characteristics of the generated and the real networks.

Copyright c 2011, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Identification of Publishing Behaviours

Data Acquisition: Source Network Extraction

The publication behaviours we are interested in are defined in terms of general publication habits, e.g. the global publication amount, and in terms of citation policies derived from hyperlinks relations between the considered sources. Therefore the studied corpus is made of a source network, whose edges represent hyperlink citations.

This network is extracted from real data, using the usercontrolled Web crawling strategy and data cleaning method proposed in [START_REF] Nel | Detecting anomalies in open source information diffusion[END_REF]. It consists in gathering all articles published by sources automatically selected under a user control and identifying the relevant hyperlinks they contain, after the removal of commercial links, those being part of the website internal browsing structure, as well as those in the article comments.

We apply this methodology to 110 generalist information websites, including Web versions of traditional daily newspapers, specialised blogs, blog platforms and collaborative publishing tools (the list can be read from the leaves of the dendogram shown on Figure 1). From a daily crawling performed between February and November 2009, we collected a database containing 190,000 articles and 140,000 links.

Data Processing: Clustering Step

To characterise the publication habits of the considered sources, we use the following 7 descriptors: we take into account their publication amount, measured by their number of published articles (denoted nb a) and the average and standard deviation of the publication intervals (resp. pub avg and pub sd). The particularities of publication on the Web are measured through the total number of hyperlinks included in their articles (nb l). Lastly we consider the diversity and the recentness of their citations: diversity (div) is defined as the number of different cited sources divided by the overall number of cited links; the average and standard deviation of the recentness of the cited articles (resp. rec avg and rec ds) are derived from the intervals between the publication dates of a considered article and the articles it cites.

The identification of the publication behaviours is then obtained by clustering these data applying the robust stacked clustering method [START_REF] Kuncheva | Evaluation of stability of k-means cluster ensembles with respect to random initialization[END_REF].

Results: Obtained Publication Behaviours

An optimal number of 4 clusters is obtained for the corpus described in Section 2.1, and for an independent corpus built in the context of a competitive intelligence analysis in the defence area. This suggests that the value of 4 distinct publication behaviours is not specific to the considered corpus.

Figure 1 shows the dendogram and its partition in 4 clusters. To characterise the corresponding publication behaviours, Figure 2 shows the cluster centroids in parallel coordinates, scaled for each descriptor to have mean 0 and standard deviation 1.

The first cluster (blue diamonds) contains 8% of the sources, characterised by a very high number of links, a high number of articles, correlated to a low publication interval, and a low diversity measure. These characteristics are consistent with the fact that it is mainly composed of specialised blogs (techcrunch, pcword).

The second cluster (violet circles) contains 8% of the sources too, whose behaviour is characterised by a high publication interval and a low number of links. They are even more specialised than the first cluster (kassandre, laquadrature), which can explain their low publishing activity.

The third cluster (green crosses) has a middle size (27% of the sources) and is mainly characterised by its high reactiv-ity, shown by the high recentness; it shares its properties of low publication interval and medium number of links with the 4th cluster. It contains websites probably familiar with Web specific tools like blog platform or collaborative publishing (rue89, googleblog). This explains its high reactivity measure and the fact that even with a smaller publication frequency, it uses more hyperlinks than the 4th cluster.

The fourth cluster (red squares) that groups more than half the sources (56 %) has a rather high number of articles and a low reactivity. It mainly contains Web versions of existing traditional newspapers (e.g. timesonline, lemonde).

As a summary, the publication behaviours are mainly distinguished according to the publication frequency, the ability to exploit Web publication particularities and the source diversity. They can be characterised as i) very active specialised blogs with low publication interval and high number of links, ii) very specialised blogs with low publishing activity, iii) general websites familiar with collaborative publishing and iv) Web version of existing newspapers.

Proposed Formalisation of the Information Propagation Process

This section proposes a formalisation of information propagation capable of reproducing the previous variety of publication behaviours. To that aim, we extend the zero-crossing, ZC, model [START_REF] Goetz | Modeling blog dynamics[END_REF]) introduced to generate a blogosphere by imitating the process of information publishing in blogs. The proposed enrichment is based on additional parameters to increase its flexibility and its expressive power. We recall the initial definition of each step of the ZC model, and present the proposed parameters together with their semantics and expected effects, as summarised on Figure 3.

Article Publication

To decide whether at time t a website publishes, the ZC model uses a zero crossing criterion on a random walk: for each website, at each time step, the random walk value is in-Figure 3: Proposed extended model.

cremented or decremented with probability 0.5. Whenever it equals zero, the website publishes an article. We introduce a parameter called step defining the change frequency of the random walk value: by default, it equals one and the random walk value is updated at each time step. This parameter thus determines the maximum publication frequency.

A second parameter called bound controls the maximum and minimum value of the random walk: when the random walk value reaches the maximum (resp. minimum), it is automatically decremented (resp. incremented) at the next step. In the random walks theory, such a constraint, called reflecting boundary, is used to represent phenomena on finite domains bounded by barriers [START_REF] Khantha | Reflection principles for biased random walks and application to escape time distributions[END_REF]. In our model, it controls the non-publishing period of a source: it simulates the maximum symbolic distraction boundary that a blogger cannot cross, and consequently, the possibility of a source not to publish during a long period of time. For example, it can be applied to differentiate the publishing behaviours of an information website with daily constraints and a more-or-less active blogger.

Link Publication

When an article is published, the ZC model defines P l the probability for it to contain a link. We propose to extend this choice through the possibility to cite several articles instead of a single one. We define the associated probability as decreasing with the number of links: for any k ≥ 1, if (k -1) links are cited, the probability to cite a k-th link is P l /k.

Cited Source Choice

Once a link is chosen to be included, the next step is to select the source it points to. The ZC model proposes two strategies: in the exploitation mode, selected with probability P e , the website uses a Web source it has already cited in the past; in the exploration mode, selected with probability 1 -P e , it cites a Web source it has never used before. In the first case, the choice is made according to the number of past links it has already made to each source and in the second case, according to the total number of in-links of the source.

We introduce the reactivity of a website A, r A , that measures the limit of oldness that A admits to cite an article, and the visibility of an article a, v a , that reflects the potential interest of a reader for its informational content. v a does not depend on its source, its layout or recentness but evaluates the extent to which a stands out from other articles in terms of the attractiveness of its content. It thus differs from the topic visibility [START_REF] Kiefer | Visibility analysis on the web using co-visibilities and semantic networks[END_REF] that is used to describe topics instead of articles and is based on hit counts of a search engine for the search of the topic term.

The article visibility v a is then extended at the website level: v A (B, t), called source visibility, represents the visibility, or attractiveness, of B at time t for A, indicating the extent to which B appears important to A. It measures the compatibility between A reactivity and B article recentness: denoting t pub (a) the publication date of a, it is computed as

v A (B, t) = max{v a , a ∈ B and (t -t pub (a)) ≤ r A }.
We then propose to use the source visibility to weight the probabilities for A to cite B: in the exploitation mode, denoting h AB the number of links cited by A and pointing to B, we define

P AB (t) = (h AB × v A (B, t))/( C h AC × v A (C, t)).
In the exploration mode, h AB = 0 and it is replaced with B absolute influence, Λ B , that represents the probability for a reader to find B when wandering randomly on the Web. The probability for A to choose B is then

P AB (t) = (Λ B ×v A (B, t))/( C Λ C ×v A (C, t)). This defi- nition is valid if A has never cited B, otherwise P AB (t) = 0.

Cited Article Choice

Finally, the precise article that is cited is chosen. Instead of using the number of in-links and the publication date of the article, we propose, in a similar way, to define the probability to choose an article a as proportional to its visibility v a . If the article has already been chosen (in the case of multiple citation links) or if it does not fit the reactivity condition of the website, this probability is zero.

At this point, the generation process of an article is complete and a visibility value is randomly assigned to the newly published article, as an integer between 1 and 100.

Validation of the Proposed Model

This section discusses the validity of the proposed model, evaluated through its ability to generate a network whose characteristics are similar to that of a real network, i.e. its realism: we show how the "low level" parameters of the model make it possible to reproduce the "high level" descriptors extracted from the real data (see Section 2). We thus implement the proposed model and perform simulations. We then apply to the generated network the analysis described in Section 2 and show that the obtained partition and its characterisation are similar to the ones obtained with the real data.

Simulation run

The number of sources is set to 100. We allow ourselves to exploit the known proportion of sources of each type: the sites are splitted in groups of 8, 9, 28 and 55. For each source, we must set the parameters of the proposed information propagation model. To that aim, we propose to define 4 classes to model the 4 identified publishing behaviours. We associate each class with a range of possible values for each parameter, as indicated in Table 1. A source is then assigned values randomly drawn from the intervals, and a random absolute influence value.

We define the intervals manually, based on the semantic of each parameter as discussed in Section 3. For example, the probability P l that an article contains one link influences the descriptor number of published links. We thus give it a high value to simulate sites belonging to the first cluster. Similarly P e obviously influences the diversity descriptor.

The simulation consists in setting a time range, and applying, for each source at each time step, the process proposed in Section 3, determining whether it publishes an article, and if it does, whether it introduces one or several hyperlinks, and if it does, what are the cited sources and articles.

Comparison of the Real and Simulated Data

We then apply the clustering process presented in Section 2: the validation consists in studying the composition of the obtained partition.

First its consistency with the classes defined to set up the simulation parameters is measured: it is compared to the partition awaited according to the membership to the 4 classes defined in Table 1. The Rand index equals 0.628 which is satisfactory considering the manually setting of the parameters. The confusion matrix (not shown due to space constraint) shows that the biggest clusters are almost unchanged, whereas the small ones become somewhat bigger.

Second, the centroids derived from the real and the simulated data can be compared, from Figures 2 and4. It can be observed that the values from the generated data are similar to the ones from the real data and that the global characteristics of each cluster meet the publishing behaviours, even if they appear to be more extreme.

Conclusion

We proposed an information propagation model presenting the ability to reproduce various publishing behaviours. The first validation carried out through a manually set up simulation shows the relevance of the generation process and choice of low level parameters that make it possible to indirectly build an artificial source network reproducing the publishing behaviours experimentally identified from real data.

The proposed model relies on manually set parameter ranges. Future works aim at applying machine learning algorithms to automatically obtain their ranges according to the values of the attributes describing the behaviours. The absolute influence parameter could also be updated automatically, e.g. by a PageRank-like algorithm.

Another perspective aims at applying the proposed propagation model to the general issue of information propagation, exploiting the implemented tool to perform realistic simulations with parameters having a coherent and intuitive semantic. It therefore becomes possible to study e.g. amplification phenomena or rumours, artificially initiating or recreating anomalies in the informational dynamics.

Figure 1 :

 1 Figure 1: Dendogram of the hierarchical clustering with a cut at four clusters, obtained from the corpus described in Section 2.1.

Figure 2 :

 2 Figure 2: Identified publication behaviours: cluster centroids in parallel coordinates.

Figure 4 :

 4 Figure 4: Simulated publication behaviours: cluster centroids in parallel coordinates.

Table 1 :

 1 Value ranges of the simulation parameters.


François Nel
email: francois.nel@lip6.fr

Marie-Jeanne Lesot
email: marie-jeanne.lesot@lip6.fr

Philippe Capet
email: philippe.capet@fr.thalesgroup.com

Thomas Delavallade
email: thomas.delavallade@fr.thalesgroup.com

Rumour detection in information warfare: understanding publishing behaviours as a prerequisite

In the context of information warfare, rumour detection has become a central issue. From classical media-related campaign, to propaganda and indoctrination that lie at the core of terrorism, rumour is a mean widely used and thus a threat that must be identified as soon as possible, and in the best-case scenario, anticipated and curbed. The emergence of a new informational environment due to the adoption of the Internet as a massive information diffusion medium has led to a situation suitable to the creation and propagation of rumours. Indeed, the Web gives everyone not only the possibility to observe information flows but also the opportunity to influence and create them.

In order to tackle the issue of rumour detection, one has to understand the mechanisms underlying their propagation. In this perspective, we believe that it is essential to identify and understand the publishing behaviours of the sources. Therefore, we focus in this paper on the identification of groups of sources with similar publishing characteristics. We propose to tackle this problematic by using clustering methods on data extracted from Web sources. The four resulting clusters obtained from the clustering are then interpreted as groups of Websites behaving similarly and used to characterize publishing behaviours.

INTRODUCTION

The adoption of the Internet as a massive information diffusion medium has considerably modified information dynamics. The Web gives everyone not only the possibility to observe information flows but also the opportunity to influence and create them. With very little knowledge and few means any Internet user is able to send information to selected recipients or, more important, display it publicly, sharing it to potentially anyone logged on the Web. New tools available to publish information are invented regularly; a recent example would be Twitter. Forums, chatrooms and above all Weblogs are rapidly growing means to create and spread information. Thus, nowadays, information Websites based classically on the model of traditional media are now mixed with autonomous and personal publishing modalities.

Every publication means to publish information has its own technical characteristics and is adapted to specific practices; nevertheless they all have in common the ability to be interconnected. Thus, an information publisher or information source can not only play the role of an initiator, but also the role of an intermediary, regardless of the tool used to publish. Therefore every source is playing its share in the way information propagates on the Web.

As a consequence of these important changes, three observations can be outlined:

• The quantity of available open source information is considerably growing.

• Flows of information are speeding up in an uncontrolled way.

• Sources of information are branching out, wearing multiple and unsorted faces.

Information is now more than ever subject to amplification, modification and distortion as the number of possible sources takes off. This media environment is suitable to the emergence and propagation of rumours that are not limited to insignificant subjects: rumours can have major consequences on political, strategic or economical decisions. Increasingly, they are triggered off on purpose for various reasons: campaigns can be carried out in order to discredit a company, endanger strategic choices or question political decisions.

One of the specificity of the rumour is to be widely spread. An inaccurate, excessively modified, or from start to end made up information can be considered as a rumour only if it has reached a considerable amount of people. Therefore, in order to be able to detect rumours, one has to understand the mechanisms underlying their propagation. We believe that these mechanisms, which are related to the dynamics of information flows, can be revealed by studying changes in publishing behaviours. In this context, it seems essential to identify and understand these behaviours. This paper focuses on the identification of groups of sources with similar publishing characteristics. We propose to tackle this problematic by using clustering methods on data extracted from Web sources. The resulting clusters obtained from the clustering are interpreted as groups of Websites behaving similarly and used to characterize publishing behaviours. This study is grounded on the use of real observed data extracted from Web publications. It does not need any a priori knowledge on the data as the proposed methodology is based on the computation of raw data. Nevertheless, some choices and hypotheses were made to be able to extract and structure Web publications, notably we introduce a model to formalize simply sources citations thanks to a network structure. This paper is organized as follows: in section 2, we first depict the problem of rumour detection as a defence and security issue, and how it is related to our process of identification of publishing behaviours. Section 3, describes the methodology we used to obtain publishing behaviours from real data. In section 4, we present the conditions of our experiments and the obtained results.

RUMOUR DETECTION

Defence and security issues

Beyond classical media-related campaigns, that may turn out to have crushing effects, the propagation of rumours on sensitive subjects may boost militant vocation or lead to criminal or terrorist actions in the physical sphere. As a security issue, this threat must be identified as soon as possible, and in the best-case scenario, anticipated and curbed.

In the specific context of a military intervention, rumours detection is a relevant issue in at least two situations. First of all, nowadays, in order to act, an armed force in democracy cannot ignore public opinion support of its root country, of the theatre of operations and sometimes of the international community. Secondly, complementary to the physical force used by an army in operation, psychological operations are conducted in order to neutralize opposing influential operation. A military victory goes through imposing peace and making opposing forces accept defeat. In an asymmetrical context, during an operation of stabilisation, opposing forces initiate rumours and use disinformation methods in order to discredit the operational forces within the local population.

Finally, rumours spreading is a vector of propaganda and indoctrination that lies at the core of terrorism. Indeed, terrorist organizations are becoming real expert in communication strategies. Usually, they start with a warning, then act and claim responsibility for the action, and finally conduct disinformation campaigns. They have learned how to use up-to-date information technologies and try to exploit the new media environment to influence and manipulate public opinion.

In this context, rumour detection has become a central issue in information warfare.

Related work

The study of rumours is a classical theme in social sciences. Case studies on specific rumours are conducted in order to reveal their context of formation and the common characteristics between rumours [START_REF] Froissart | Rumor[END_REF]. Some models inspired from physics have been introduced in order to grasp the social context of a rumour formation [START_REF] Galam | Modeling Rumors : The No Plane Pentagon French Hoax Case[END_REF].

Work on rumours is related to information spreading. Many studies on the problem of information propagation are inspired from the more common issue of contagion and generally uses models based on the standard model for viral epidemics in populations: the susceptible-infected-recovered (SIR) model [START_REF] Dodds | Universal behavior in a generalized model of contagion[END_REF]. On this subject, research has focused on the effects of the topological properties of the network on the propagation of infection [START_REF] Newman | The spread of epidemic disease on networks[END_REF] or on inferring the source of a rumour in a network [START_REF] Shah | Rumors in a Network: Who's the Culprit ? In Neural Information[END_REF].

We believe that one method to detect rumours is to analyse the informational content. Statistical and linguistic analysis like the method presented in [START_REF] Leskovec | Meme-tracking and the Dynamics of the News Cycle[END_REF] to track meme could be use to detect rumours. Another lead to detect rumours is the analysis of the publication network through which rumours might propagate. A study of the variations of such a network has been conducted in [START_REF] Nel | Detecting Anomalies in Open Source Information Diffusion[END_REF].

Most of these works consider the network and its reaction to the propagation model. However, nodes in the network usually have the same behavior defined by the propagation model. Sources are not differentiated and there has been no work on how to include multiple publishing behaviours. In the perspective of detecting rumours, it seems central to understand the publishing behaviours of the information sources. Our contribution to this subject is the identification from real data of typical behaviours of sources publishing and propagating information on a network. RTO-MP-IST-091

IDENTIFYING PUBLISHING BEHAVIOURS

We choose to use a clustering method to identify classes of publishing behaviours. This section describes the different steps of the methodology we propose to apply. It starts with the choice of a series of descriptors that could differentiate behaviours of publication. These descriptors derive directly from real data extracted from Website publications and therefore are linked to what we are able to extract. We present in this section the choices of the extraction process based on a simple model of information propagation. Then we describe the stacked clustering method that starts with the choice of the number of clusters and eventually identifies a partition of sources.

Defining descriptors from extracted data

In order to define some descriptors to characterize publishing behaviours, we first need to choose a model to represent the mechanisms of publishing behaviours. This model for information propagation guides the strategies we chose to extract the data and the final definition of the descriptors.

A model for information propagation

Ideally, a model of information diffusion on the Web should be able to simulate the state of awareness of Web users about a specific piece of information. Nevertheless, from a practical point of view, it seems difficult to have access to such data. Moreover, in such a study, only Web users who may have an impact on information diffusion (in other words who routinely publish information on a Website) could be taken into account.

We propose in [START_REF] Nel | Detecting Anomalies in Open Source Information Diffusion[END_REF] a simple model of information representation that can be implemented and used with real data and from which characteristics of publishing behaviours can be derived. Indeed, for practical reasons, we focus on the visible and extractable data that is to say Websites publications.

The model is based on a graph of Websites. Each node of the graph represents a Website. The nodes are linked to each other by directed edges meaning "is a source of information for". This way, information propagation can be easily monitored following the directed edges on the network. We base our representation of the source network on the following hypothesis: when a publisher explicitly refers to another Web page using a hyperlink, the Website pointed by the cited link is considered as one of the information sources for the publisher.

Extraction strategies

We developed a tool to extract the data needed for our analysis. We named our tool ONICS (Outils de Navigation, d'Indexation et de Classement des Sources), which stands for browsing, indexing and sorting tool for sources. The specificities of this piece of software are to extract every publication of a list of sources chosen by the user and to identify the hyperlinks cited in the published articles. A more detailed description of the crawling choices and extraction process is available in [START_REF] Nel | Detecting Anomalies in Open Source Information Diffusion[END_REF]. Basically, this tool is able to store in a database the text of articles, their publication date and the hyperlinks cited for all the publications of a list of sources. From this data we are able to build the source network described above.

Extracted descriptors

We choose to derive the descriptors from our model of information propagation. Therefore, they do not to take into account the content and themes of the articles published but only the structure of the source network. We use the following descriptors for each source:

• The average and standard deviation of the publication intervals

• The number of published articles and links

• The diversity of the cited sources defined as the ratio between the number of different sources and the overall number of cited links

• The average and standard deviation of the recentness of the cited articles. The measure of recentness is defined as the interval between the publication date of the studied article and the publication date of the cited articles.

We believe that these seven descriptors characterise the publication habits of a source as well as its criteria to select its own sources of information. Thus, we will be able to extract publishing behaviours by using a custering method on these data.

Using a stacked clustering method

The choice of the clustering method is central in the process. suppose that we do not have a priori knowledge on the awaited results, in particular, the precise number or size of the clusters are unknown. Therefore, we choose to use a clustering method robust enough not to question the validity of the resulting clustering. Preliminary tests with k-means and hierarchical clustering algorithms gave useless results: the k-means algorithms gave very unstable partitions due to random initialization whereas hierarchical clustering gave very different results with different linkage strategies making the choice of selecting a final partition quite arbitrary. To tackle this issue, we choose to apply a stacked clustering method [START_REF] Dodds | Universal behavior in a generalized model of contagion[END_REF] using multiple k-means iteration and a hierarchical clustering.

This section describes how the results of the k-means iterations are used, firstly to choose the number of clusters and secondly as an input of a hierarchical clustering. We decided not to take into consideration the result for k equals 2, because we believe that identifying only two kinds of behaviours presents very little interest. The k-means algorithm has some restrictions as it takes the number of clusters k as an input parameter and its result heavily depends on the initial clusters. Nevertheless, the algorithm is usually very fast, and we choose to run it multiple times (1000 times for each k, with k defined from 3 to 10) with random initial clusters. The results presented in the following sections are based on the analysis of the 9000 obtained partitions.

Choosing the number of clusters

From the results of the k-means clustering, we use a measure introduced in [START_REF] Kuncheva | Evaluation of Stability of k-Means Cluster Ensembles with Respect to Random Initialization[END_REF] to choose the number of clusters. The idea is to define the best number of clusters as the integer k for which the partition resulting of the k-means is the stablest.

Let I k be a set of partitions of k clusters. Let P i ∈I k a partition. We then look for the number k for which the stability of I k is maximum. For that we need a similarity measure to evaluate the degree of match between two partitions, and a stability measure for I k that acts as an aggregator of the similarity measure for all the partitions of I k . We used the adjusted Rand index [START_REF] Hubert | Comparing partitions[END_REF] for the similarity measure and the pairwise individual stability [START_REF] Kuncheva | Evaluation of Stability of k-Means Cluster Ensembles with Respect to Random Initialization[END_REF] for the stability measure.

The adjusted Rand index

The adjusted Rand index is used to compute the similarity between two data partitions. This index takes values between 0 (for partitions drawn independently of one another) and 1 (for identical partitions). For two partitions A and B, let n be the total number of points in the dataset; a the number of point pairs in the same cluster under both A and B; b the number of point pairs in the same cluster under A but not B; c the number of point pairs in the same cluster under B but not A; d the number of point pairs in different clusters under both A and B. The measure is defined as follows: RTO-MP-IST-091

( ) ( ) ( ) ( )( ) ( )( ) ( ) ( ) ( )( ) ( )( ) (
)

d b d c c a b a n n d b d c c a b a d a n n B A AR + + + + + -       - + + + + + - +       - = 2 2 1 2 1 ,

Pairwise individual stability

The pairwise individual stability S(k) uses the adjusted rand index of each pair of partitions of I k (i.e. 0,5|I k |(|I k |-1) pairs). It computes the sum of the adjusted rand index for all the pairs of partitions

( ) ( ) ( ) ∑ < ∈ = j i I j i j i k k P k P AR k S , , , ) (
The chosen number of clusters is then the value of k where S(k) is maximum.

Choosing a final partition

After having chosen the number of clusters k, we use the overall results of the k-means clustering in order to select one final clustering. To do that, we first derive the co-association matrix for each of the 9000 partitions. The co-association matrix M (P) for partition P is defined as: From the 9000 co association matrices, we then derive the consensus matrix M defined as :

M (P) = { }
M = M (P1) + M (P2) + … + M (P9000)
The consensus matrix contains the number of times where points are in the same cluster. From this observation, we note that if the number is high for two points, it means that they belong usually to the same cluster and on the opposite, if it is low, they do not probably belong together. Therefore, it seems natural to consider the consensus matrix M as a similarity matrix between the points [START_REF] Kuncheva | Evaluation of Stability of k-Means Cluster Ensembles with Respect to Random Initialization[END_REF]. Finally, after having converted the similarity measures into distance measures (by substracting the maximum value to each similarity measure), we are able to apply a hierarchical algorithm.

We choose to use an average linkage strategy for the hierarchical clustering as we consider that a high distance value between two points should be given the same importance as a small distance value. Indeed, in our opinion, both values present some interest and we do not want to give more importance to one value at the expense of the other.

Finally, the chosen partition is the result of this hierarchical clustering obtained by cutting the dendogram at the best value of k computed in the last section.

EXPERIMENTS 4.1 Data

To conduct our experiments, we use a database containing 190000 articles and 140000 links for a total of 110 Websites crawled daily between February and November 2009 using the ONICS tool. For this database was created for testing purposes, we chose to crawl a series of generalist information Websites. The database forms our main corpus that we used to establish the publishing behaviours. For further tests we used a secondary corpus which has been originally built in the context of a competitive intelligence analysis within the defence area.

Results

In this section, the result of the overall methodology of the identification of publishing behaviours is presented.

Figure 1 shows the results of the stability measure S(k) for the main corpus (in blue with squares) and the secondary corpus (in red with circles). We give the result for k defined from 3 to 10. We obtain an optimal number of clusters of 4. The test for the secondary corpus seems to confirm that the probable number of different publishing behaviours is 4.

INTERPRETATION OF THE CLUSTERING RESULTS

From the result of the final partition, we try to extract the main characteristics of each cluster in order to identify the main aspects of the different behaviours. Figure 3 represents for each cluster the average value (scaled for each descriptor to have mean 0 and standard deviation 1) of each of the initial descriptors. The descriptors, from the left to the right are: the standard deviation and the average of the publication intervals (resp. pub_sd and pub_avg), the number of article and links published (resp. nb_a and nb_l), the diversity of the cited sources and the average and standard deviation of the recentness of the cited articles (resp. rec_avg and rec_ds). On the following, we present a few observations derived from these results:

• The first cluster (in blue and diamonds) is small (it contains 8% of all the Websites) and is characterized by a low publication interval and a high number of links. This cluster is mainly composed of specialised blog (techcrunch, pcword) with the particularity to be very active.

• The second cluster (in violet and circles) is small (8% of the Websites) and on the opposite is characterized by a very high publication interval and a low number of links. It is worth pointing that this is the cluster with the highest diversity measure which is however not very representative because the websites within this cluster publish rarely. They seems to be even more specialised than the first cluster (kassandre, laquadrature) which may explain their very low publishing activity.

• The third cluster (in green and crosses) and fourth (in red and squares) have respectively an average size (27%) and big size (56%) and have quite the same characteristics (low publication interval and medium number of links). The difference lies in the descriptor of recentness of the cited articles. At first sight they seem composed of quite similar type of Websites. When exploring in more details the composition of these two clusters, we note that the third cluster contains Website probably more familiar with web specific tools for publication like blog platform or collaborative publishing (rue89, googleblog) whereas the fourth cluster contains mainly Web version of existing newspapers (lefigaro, lemonde, liberation…). This interpretation is confirmed by the very high reactivity measure of the third cluster and the fact that even with a smaller frequency of publication, the third cluster uses more hyperlinks then the fourth cluster.

The sizes of the clusters give a precise idea of the composition of the network observed in our extracted data. This is an important knowledge in the case we want to study rumours within this perimeter of this precise network. However, it is worth noting that there is no reason to conclude that these proportions are representative of any network extracted from Web publications or even less the general composition of the Web.

CONCLUSIONS AND FUTURE WORKS

This paper presented a methodology to identify groups of sources with similar publishing characteristics. We chose not to take choices based on a priori knowledge concerning the awaited results and based our choices on the use of real data extracted from Web sources publications.

We used a robust stack clustering methodology in order to select a possible partition. It is based on multiple results of k-means clustering, at first, to choose a number of clusters and then to feed a hierarchical clustering. The methodology is very robust but cannot be apply to very large sets of data because it is very demanding in computational resources. This disadvantage that must always be kept in mind, does not worry us unduly because in the case of competitive intelligence, the number of interesting sources rarely exceeds a thousand.

This study provides interesting results in the establishment of publishing behaviours. Notably, we identified four different groups and more important the aspects on which they differentiate. Moreover, this work reveals the proportion of each group in a real network of sources. Because it is extracted from observed data, these results should be very useful for future works on information propagation and particularly studies on rumour detection.

As an extension of this work, we suggest to validate the choice of our descriptors with experts in intelligence analysts. At the same time, other interesting descriptors may be defined to confirm our results or even identify other underlying behaviours among the four groups we presented. These may be based for example on the article itself (size or structure) or on more sophisticated topological measures of the RTO-MP-IST-091

network. The difficulty of the task remains in the ability to extract the value of these descriptors from real web publication data.

In a perspective of research on rumour detection, we plan to use these results to calibrate a model simulating dynamics of citation between web sources. Simulation gives numerous possibilities to understand the evolution of rumours in a network by controlling the parameters that could initiate or on the contrary terminate a rumour. We believe that publishing behaviours are well established among these parameters. Therefore by adding distinct publishing behaviours derived from observed data in such a model, we hope to achieve better understanding of the reality of this complex phenomenon.

  element i and element j are in the same cluster in partition P element i and element j are in different clusters in partition P

Figure 1 :

 1 Figure 1: Results of the stability measure for two different corpora

Figure 2 Figure 2 :

 22 Figure 2 shows the final result of the hierarchical clustering. It is the dendogram cut for a number of clusters of 4. We can note, as a first observation that the sizes of the clusters are really unbalanced.

Figure 3 :

 3 Figure 3: Centroids visualization on parallel coordinates

RTO-MP-IST-091

RTO-MP-IST-091

Processing Systems (NIPS), 2009


Rumour detection and monitoring in open source intelligence

Keywords: Publishing behaviours, rumour detection, Web sources, stacked clustering

In the context of information warfare, rumour detection has become a central issue. From classical media-related campaign, to propaganda and indoctrination that lie at the core of terrorism, rumour is a mean widely used and thus a threat that must be identified as soon as possible, and in the best-case scenario, anticipated and curbed. The emergence of a new informational environment due to the adoption of the Internet as a massive information diffusion medium has led to a situation suitable to the creation and propagation of rumours. Indeed, the Web gives everyone not only the possibility to observe information flows but also the opportunity to influence and create them. In order to tackle the issue of rumour detection, one has to understand the mechanisms underlying their propagation. In this perspective, we believe that it is essential to identify and understand the publishing behaviours of the sources. Therefore, we focus in this paper on the identification of groups of sources with similar publishing characteristics. We propose to tackle this problematic by using clustering methods on data extracted from Web sources. The resulting clusters obtained from the clustering are then interpreted as groups of Websites behaving similarly and used to characterize publishing behaviours.

Introduction

The adoption of the Internet as a massive information diffusion medium has considerably modified information dynamics. The Web gives everyone not only the possibility to observe information flows but also the opportunity to influence and create them. With very little knowledge and few means any Internet user is able to send information to selected recipients or, more important, display it publicly, sharing it to potentially anyone logged on the Web. New tools available to publish information are invented regularly; the emergence of social networks, like Twitter, is a recent example. Forums, chatrooms and above all Weblogs are rapidly growing means to create and spread information. Thus, nowadays, information Websites based classically on the model of traditional media are now mixed with autonomous and personal publishing modalities.

Every publication means to publish information has its own technical characteristics and is adapted to specific practices; nevertheless they all have in common the ability to be interconnected. Thus, an information publisher or information source can not only play the role of an initiator, but also the role of an intermediary, regardless of the tool used to publish. Therefore every source is playing its share in the way information propagates on the Web.

As a consequence of these important changes, three observations can be outlined:

• The quantity of available open source information is considerably growing.

• Flows of information are speeding up in an uncontrolled way.

• Sources of information are branching out, wearing multiple and unsorted faces.

Information is now more than ever subject to amplification, modification and distortion as the number of possible sources takes off. This media environment is suitable to the emergence and propagation of rumours that are not limited to insignificant subjects: rumours can have major consequences on political, strategic or economical decisions. Increasingly, they are triggered off on purpose for various reasons: campaigns can be carried out in order to discredit a company, endanger strategic choices or question political decisions.

One of the specificity of the rumour is to be widely spread. An inaccurate, excessively modified, or from start to end made up information can be considered as a rumour only if it has reached a considerable amount of people. Therefore, in order to be able to detect rumours, one has to understand the mechanisms underlying their propagation. We believe that these mechanisms can be revealed by studying changes in publishing behaviours. In this context, it seems essential to identify and understand these behaviours.

This paper focuses on the identification of groups of sources with similar publishing characteristics.

We propose to tackle this problematic by using clustering methods on data extracted from Web sources. The resulting clusters obtained from the clustering are interpreted as groups of Websites behaving similarly and used to characterize publishing behaviours. This study is grounded on the use of real observed data extracted from Web publications. It does not need any a priori knowledge on the data as the proposed methodology is based on the computation of raw data. Nevertheless, some choices and hypotheses were made to be able to extract and structure Web publications, notably we introduce a model to formalize simply sources citations thanks to a network structure.

This paper is organized as follows: in section 2, we first depict the problem of rumour detection as a defence and security issue, and how it is related to our process of identification of publishing behaviours. Section 3 describes the methodology we used to obtain publishing behaviours from real data. In section 4, we present the conditions of our experiments and the obtained results.

Rumour detection

Rumours and terrorism

The link between rumours and terrorism is strong on many levels. A high level of rumour propagation is usually the expression and the indication of a global state of emotional tension like fear or anxiety among a population. For example, warfare or conflict situations are known to provide optimal conditions for rumour dissemination [START_REF] Allport | The Psychology of Rumor[END_REF].

Similarly, besides the loss of human lives and infrastructures, a terrorist attack induces psychological trauma at both individual and collective level that leads to a general situation of group anxiety and fear. Thus, a terrorist attack usually goes with multiple rumours that can be purposely created in order to affect the national morale and the trust in the government in power.

Terrorist organizations are becoming real expert in communication strategies. Terrorist attacks are planned in conjunction with a communication strategy: they usually start with a warning and are obviously claimed afterwards. Moreover, the core of terrorism is based on indoctrination and propaganda that are conducted by disinformation campaigns and manipulation of information. The efficiency and impact of these campaigns on the public opinion is closely related to the critical sensibility of the population and its level of anxiety and fear. The use of obnoxious rumours by terrorists is a very efficient method to maintain and worsen such a situation.

In this context, rumour detection has become a central issue in anti-terrorism activities for two main reasons: firstly because they are indicators of a situation where terrorism propaganda is the most efficient and secondly because they are created purposely by terrorist organization to manipulate public opinion and legitimate their actions.

Related work

The study of rumours is a classical theme in social sciences. Case studies on specific rumours have been conducted in order to reveal their context of formation and the common characteristics between rumours [START_REF] Froissart | Rumor[END_REF]. Some models inspired from physics have been introduced in order to grasp the social context of a rumour formation [START_REF] Galam | Modeling Rumors: The No Plane Pentagon French Hoax Case[END_REF].

Work on rumours is related to information spreading. Many studies on the problem of information propagation are inspired from the more common issue of contagion and generally use models based on the standard model for viral epidemics in populations: the susceptible-infected-recovered (SIR) model [START_REF] Dodds | Universal behavior in a generalized model of contagion[END_REF]. Studies on information propagation are usually based on a network where a node is an information source and an edge an information exchange between two nodes. On this subject, research has focused on the effects of the topological properties of the network on the propagation of infection [START_REF] Newman | The spread of epidemic disease on networks[END_REF] or on inferring the source of a rumour in a network [START_REF] Shah | Rumors in a Network: Who's the Culprit ?[END_REF].

We distinguish two methods to detect rumours. The first one is based on the analysis of the informational content. Statistical and linguistic analysis like the method presented in [START_REF] Leskovec | Meme-tracking and the Dynamics of the News Cycle[END_REF] to track meme could be use to detect rumours. The second method focuses on the strucutre of the publication network through which rumours might propagate. A study of the variations of such a network has been conducted in [START_REF] Nel | Detecting Anomalies in Open Source Information Diffusion[END_REF].

Most of these works consider the network and its reaction to the propagation model. However, nodes in the network usually have the same behaviour defined by the propagation model. Sources are not differentiated and there has been no work on how to include multiple publishing behaviours. In the perspective of detecting rumours, it seems central to understand the publishing behaviours of the information sources. Our contribution to this subject is the identification from real data of typical behaviours of sources publishing and propagating information on a network.

Identifying publishing behaviours

The objective is to identify groups of homogeneous sources, by considering publishing characteristics.

We propose to tackle this problematic by using a clustering method. This section describes the different steps of the methodology we propose to apply. It starts with the choice of a series of descriptors that could differentiate behaviours of publication. These descriptors derive directly from real data extracted from Website publications and therefore are linked to what we are able to extract. We present in this section the choices of the extraction process based on a simple model of information propagation. Then we describe the stacked clustering method that starts with the choice of the number of clusters and eventually identifies a partition of sources.

Defining descriptors from extracted data

In order to define some descriptors to characterize publishing behaviours, we first need to choose a model to represent the mechanisms of publishing behaviours. We based our strategies to extract the data and to choose the final definition of the descriptors on this model.

A model for information propagation

We propose in [START_REF] Nel | Detecting Anomalies in Open Source Information Diffusion[END_REF] a simple model of information representation that can be implemented and used with real data and from which characteristics of publishing behaviours can be derived. Indeed, for practical reasons, we focus on the visible and extractable data that is to say Websites publications.

The model is based on a graph of Websites. Each node of the graph represents a Website. The nodes are linked to each other by directed edges meaning "is a source of information for". This way, information propagation can be easily monitored following the directed edges on the network. We base our representation of the source network on the following hypothesis: when a publisher explicitly refers to another Web page using a hyperlink, the Website pointed by the cited link is considered as one of the information sources for the publisher.

Extraction strategies

We developed a specific Web crawler to extract the data needed for our analysis. We named our crawler ONICS (Outils de Navigation, d'Indexation et de Classement des Sources), which stands for browsing, indexing and sorting tool for sources. The specificities of ONICS are to extract every publication of a list of sources chosen by the user and to identify the hyperlinks cited in the published articles. A more detailed description of the crawling choices and extraction process is available in [START_REF] Nel | Detecting Anomalies in Open Source Information Diffusion[END_REF].

Basically, this tool is able to store in a database the text of articles, their publication date and the hyperlinks cited for all the publications of a list of sources. From this data we are able to build the source network described above.

Extracted descriptors

We choose to derive the descriptors from our model of information propagation. Therefore, they do not to take into account the content and themes of the articles published but only the structure of the source network and its dynamics. We use the following descriptors for each source:

• The average and standard deviation of the publication intervals • The number of published articles and links • The diversity of the cited sources defined as the ratio between the number of different sources and the overall number of cited links • The average and standard deviation of the recentness of the cited articles. The measure of recentness is defined as the interval between the publication date of the studied article and the publication date of the cited articles.

We believe that these seven descriptors characterise the publication habits of a source including the criteria each Website relies on to select its own sources of information. Thus, we will be able to extract publishing behaviours by using a clustering method on these data.

Using a stacked clustering method

The choice of the clustering method is central in the process. We suppose that we do not have a priori knowledge on the awaited results, in particular, the precise number or size of the clusters are unknown. Therefore, we choose to use a clustering method robust enough not to question the validity of the resulting clustering. Preliminary tests with k-means and hierarchical clustering algorithms gave useless results: the k-means algorithms gave very unstable partitions due to random initialization whereas hierarchical clustering gave very different results with different linkage strategies making the choice of selecting a final partition quite arbitrary. To tackle this issue, we choose to apply a stacked clustering method [START_REF] Kuncheva | Evaluation of Stability of k-Means Cluster Ensembles with Respect to Random Initialization[END_REF] using multiple k-means iteration and a hierarchical clustering.

This section describes how the results of the k-means iterations are used, firstly to choose the number of clusters and secondly as an input of a hierarchical clustering. We decided not to take into consideration the result for k equals 2, because we believe that identifying only two kinds of behaviours presents very little interest. The k-means algorithm has some restrictions as it takes the number of clusters k as an input parameter and its result heavily depends on the initial clusters. To circumvent theses problems we chose to run it multiple times (1000 times for each k, with k defined from 3 to 10) with random initial clusters. The results presented in the following sections are based on the analysis of the 8000 obtained partitions.

Choosing the number of clusters

From the results of the k-means clustering, we use a measure introduced in [START_REF] Kuncheva | Evaluation of Stability of k-Means Cluster Ensembles with Respect to Random Initialization[END_REF] to choose the number of clusters. The idea is to define the best number of clusters as the integer k for which the partition resulting of the k-means is the most stable.

Let I k be a set of partitions of k clusters. Let P i ∈I k a partition. We then look for the number k for which the stability of I k is maximum. For that we need a similarity measure to evaluate the degree of match between two partitions, and a stability measure for I k that acts as an aggregator of the similarity measure for all the partitions of I k . We used the adjusted Rand index [START_REF] Hubert | Comparing partitions[END_REF][START_REF] Santos | On the Use of the Adjusted Rand Index as a Metric for Evaluating Supervised Classification[END_REF] for the similarity measure and the pairwise individual stability [START_REF] Kuncheva | Evaluation of Stability of k-Means Cluster Ensembles with Respect to Random Initialization[END_REF] for the stability measure.

The adjusted Rand index

The adjusted Rand index is used to compute the similarity between two data partitions. This index takes values between 0 (for partitions completly independent of one another) and 1 (for identical partitions). For two partitions A and B, let n be the total number of points in the dataset; a the number of point pairs in the same cluster under both A and B; b the number of point pairs in the same cluster under A but not B; c the number of point pairs in the same cluster under B but not A; d the number of point pairs in different clusters under both A and B. The measure is defined as follows:

( ) ( ) ( ) ( )( ) ( )( ) ( ) ( ) ( )( ) ( )( ) (
)

d b d c c a b a n n d b d c c a b a d a n n B A AR + + + + + -       - + + + + + - +       - = 2 2 1 2 1 ,

Pairwise individual stability

The

( ) ( ) ( ) ∑ < ∈ = j i I j i j i k k P k P AR k S , , , ) (
The chosen number of clusters is then the value of k where S(k) is maximum.

Choosing a final partition

After having chosen the number of clusters k, we use the overall results of the k-means clustering in order to select one final clustering. To do that, we first derive the co-association matrix for each of the 8000 partitions. The co-association matrix M (P) for partition P is defined as: From the 8000 co association matrices, we then derive the consensus matrix M defined as :

M (P) = { }
M = M (P1) + M (P2) + … + M (P8000)
The consensus matrix contains the number of times where points are in the same cluster. From this observation, we note that if the number is high for two points, it means that they belong usually to the same cluster and on the opposite, if it is low, they do not probably belong together. Therefore, it seems natural to consider the consensus matrix M as a similarity matrix between the points [START_REF] Kuncheva | Evaluation of Stability of k-Means Cluster Ensembles with Respect to Random Initialization[END_REF]. Finally, after having converted the similarity measures into distance measures (by subtracting the maximum value to each similarity measure), we are able to apply a hierarchical algorithm.

Finally, the chosen partition is the result of this hierarchical clustering obtained by cutting the dendogram at the best value of k computed in the last section.

Experiments

Data

To conduct our experiments, we use a database containing 190000 articles and 140000 links for a total of 110 Websites crawled daily between February and November 2009 using the ONICS tool. For this database was created for testing purposes, we chose to crawl a series of generalist information Websites. The database forms our main corpus that we used to establish the publishing behaviours. For further tests we used a secondary corpus that has been originally built in the context of a competitive intelligence analysis within the defence area.

Results

In this section, the result of the overall methodology of the identification of publishing behaviours is presented.

Figure 1 shows the results of the stability measure S(k) for the main corpus (in blue with squares) and the secondary corpus (in red with circles). We obtain an optimal number of clusters of 4. The test for the secondary corpus seems to confirm that the probable number of different publishing behaviours is 4.

Figure 2 shows the final result of the hierarchical clustering. It is the dendogram cut for a number of clusters of 4. We can note, as a first observation that the sizes of the clusters are really unbalanced.

Interpretation of the clustering results

From the result of the final partition, we try to extract the main characteristics of each cluster in order to identify the main aspects of the different behaviours. Figure 3 represents for each cluster the average value (scaled for each descriptor to have mean 0 and standard deviation 1) of each of the initial descriptors. The descriptors, from the left to the right are: the standard deviation and the average of the publication intervals (resp. pub_sd and pub_avg), the number of article and links published (resp. nb_a and nb_l), the diversity of the cited sources and the average and standard deviation of the recentness of the cited articles (resp. rec_avg and rec_ds). From these results, the following observations can be derived:

• The first cluster (in blue and diamonds) is small (it contains 8% of all the Websites) and is characterized by a low publication interval and a high number of articles; these measure are the expression of a very substancial publishing behaviour. A high number of links and low diversity measure is consistent with the fact that this cluster is mainly composed of specialised blog (techcrunch, pcword). • The second cluster (in violet and circles) is small as well (8% of the Websites) and on the opposite is characterized by a very high publication interval and a low number of links. It is worth pointing that this is the cluster with the highest diversity measure that is however not very representative because the Websites within this cluster publish rarely and uses few links. They seems to be even more specialised than the first cluster (kassandre, laquadrature) which may explain their very low publishing activity. • The third cluster (in green and crosses) and fourth (in red and squares) have respectively an average size (27%) and big size (56%) and have quite the same characteristics (low publication interval and medium number of links). The difference lies in the descriptor of recentness of the cited articles. At first sight they seem composed of quite similar type of Websites. When exploring in more details the composition of these two clusters, we note that the third cluster contains Websites probably more familiar with Web specific tools for publication like blog platform or collaborative publishing (huffingtonpost, googleblog) whereas the fourth cluster contains mainly Web version of existing newspapers (timesonline, lemonde, elpais…). This interpretation is confirmed by the very high reactivity measure of the third cluster and the fact that even with a smaller frequency of publication, the third cluster uses more hyperlinks per article than the fourth cluster.

The centroids visualization shows that the standard deviation and the average (for both measures: publication intervals and recentness) are two descriptors with the same impact on the final clustering. It should be considered not to use both in future implementations.

The sizes of the clusters give a precise idea of the composition of the network observed in our extracted data. This is an important knowledge when studying rumours within the perimeter of this precise network. However, it is worth noting that there is no reason to conclude that these proportions are representative of any network extracted from Web publications or even less the general composition of the Web.

Conclusions and future works

Initiating rumours is a powerful mean for terrorists to affect public opinion and legitimate their actions. Moreover, the emergence of all kinds of rumours is an indicator of a situation favouring the impact of terrorist communication campaigns. Thus the detection, monitoring and curbing of rumours is an important challenge for counter-terrorism organizations.

The monitoring of communication campaigns of terrorist organizations in open source is a case study very promising in the context of research on rumour detection.

The method presented in this paper can be directly applicable on a predefine network of sources in close contact or managed by terrorist activists. By giving a categorization of the sources according to their communication habits, it improves the knowledge that counter-terrorism organizations have on the sources and may help to assess their level of toughening or relation to the terrorist organizations.

Nevertheless, the monitoring of open sources on which this method is based is only one possible perspective to tackle the issue of information manipulation by terrorist communication campaigns.

This paper presented a methodology to identify groups of sources with similar publishing characteristics. We chose not to take choices based on a priori knowledge concerning the awaited results and based our choices on the use of real data extracted from Web sources publications. We used a robust stack clustering methodology in order to select a possible partition. It is based on multiple results of k-means clustering, at first, to choose a number of clusters and then to feed a hierarchical clustering. The methodology is very robust but cannot be applied to very large sets of data because it is very demanding in computational resources. This disadvantage that must always be kept in mind, does not worry us unduly because in the case of strategic intelligence, the number of interesting sources rarely exceeds a thousand.

This study provides interesting results in the establishment of publishing behaviours. Notably, we identified four different groups and more important the aspects on which they differentiate. Moreover, this work reveals the proportion of each group in a real network of sources. Because it is extracted from observed data, these results should be very useful for future works on information propagation and particularly studies on rumour detection.

As an extension of this work, we suggest to validate the choice of our descriptors with experts in intelligence analysts. At the same time, other interesting descriptors may be defined to confirm our results or even identify other underlying behaviours among the four groups we presented. These may be based for example on the article itself (size or structure) or on more sophisticated topological measures of the network. The difficulty of the task remains in the ability to extract the values of these descriptors from real Web publication data. Moreover, it would be interesting to experiment the presented methodology on other corpora in order to see if new behaviours can be identified.

In a perspective of research on rumour detection, we plan to use these results to calibrate a model simulating dynamics of citation between Web sources. Simulation gives numerous possibilities to understand the evolution of rumours in a network by controlling the parameters that could initiate or on the contrary terminate a rumour. By adding distinct publishing behaviours derived from observed data in such a model, we hope to achieve better understanding of the reality of this complex phenomenon.

  pairwise individual stability S(k) uses the adjusted Rand index of each pair of partitions of I k (i.e. |I k |(|I k |-1)/2 pairs where |I k | is the number of partitions of k clusters). It computes the sum of the adjusted Rand index for all the pairs of partitions

  element i and element j are in the same cluster in partition P element i and element j are in different clusters in partition P

Figure 1 :

 1 Figure 1: Results of the stability measure for two different corpora

Figure 2 :

 2 Figure 2: Dendogram of the hierarchical clustering with a cut for 4 clusters

Figure 3 :

 3 Figure 3: Centroids visualization on parallel coordinates