Nathalie Henry Riche

Bongshin Lee
email: bongshin@microsoft.com

Fanny Chevalier
email: fanny.chevalier@inria.fr

iChase: Supporting Exploration and Awareness of Editing Activities on Wikipedia

Keywords: H.5.2 [Information Systems]: User Interfaces -User-centered design; Wikipedia visualization, timeline visualization, interaction

To increase its credibility and preserve the trust of its readers, Wikipedia needs to ensure a good quality of its articles. To that end, it is critical for Wikipedia administrators to be aware of contributors' editing activity to monitor vandalism, encourage reliable contributors to work on specific articles, or find mentors for new contributors. In this paper, we present iChase, a novel interactive visualization tool to provide administrators with better awareness of editing activities on Wikipedia. Unlike the currently used visualizations that provide only page-centric information, iChase visualizes the trend of activities for two entity types, articles and contributors. iChase is based on two heatmaps (one for each entity type) synchronized to one timeline. It allows users to interactively explore the history of changes by drilling down into specific articles and contributors, or time points to access the details of the changes. We also present a case study to illustrate how iChase can be used to monitor editing activities of Wikipedia authors, as well as a usability study. We conclude by discussing the strengths and weaknesses of iChase.

INTRODUCTION

Since Ward Cunningham developed the first wiki [1] in 1994, wikis have been astonishingly successful, especially when used as collaborative knowledge building tools [START_REF]FoxPro Wiki[END_REF][1]. A famous example is Wikipedia, a free online collaborative encyclopedia consisting of millions of pages created by hundreds of thousands users in hundreds of languages. Since late 2004, several French contributors have been working towards releasing an offline version of Wikipedia to be distributed on DVD: Wikipedia 1.0 [4]. To make this first release of Wikipedia possible, a number of active contributors volunteered to administrate projects (sets of articles on a given topic) on core topics and ensure that key articles reach a good level of completeness and quality. To better monitor each project, administrators established a set of measures to rank the quality, importance and progress of each article [START_REF]Wikipedia 1.0/Core topics[END_REF]. However, even with these measures, maintaining an awareness of the activity of a project with dozens of articles and hundreds of contributors is a challenging task.

Wikipedia's great success has raised interests from many information visualization researchers. For example, History flow [START_REF] Viégas | Studying cooperation and conflict between authors with history flow visualizations[END_REF], WikipediaViz [START_REF] Chevalier | Conveying Article Quality for Casual Wikipedia Readers[END_REF], and JWikiVis [START_REF] Gawryjołek | The Analysis and Visualization of Entries in Wiki Services[END_REF] visualize the editing activity of given articles and depict their evolution. A couple of visualizations such as Chromograms [START_REF] Wattenberg | Visualizing Activity on Wikipedia with Chromograms[END_REF] show the editing activities of contributors, attempting to characterize different profiles. Surprisingly, only a few visualizations such as WikiDashboard [START_REF] Suh | Lifting the veil: improving accountability and social transparency in Wikipedia with wikidashboard[END_REF] focused on providing day-to-day awareness of the activity of articles and contributors. While WikiDashboard has been proven helpful to occasional contributors and readers to assess the status of individual articles [START_REF] Pirolli | So you know you're getting the best possible information: a tool that increases wikipedia credibility[END_REF], it fails to support the current needs of Wikipedia 1.0's administrators: since administrators need to monitor multiple articles and contributors at the same time, they are required to navigate from page to page to assess the most recent activities on the project (from both the articles' and contributors' perspective). Today, to maintain awareness of a project activity, these administrators' common practice is to review the textual list of revisions since they last logged in. They report this practice to be not only tedious but also difficult for them to maintain a mental map of the evolution of their projects and to decide where the effort should be directed.

To help administrators acquire a better awareness of the activity of their projects, we designed and developed iChase (Figure 1). iChase is an interactive multi-scale visualization of the editing activity of a Wikipedia project. It provides a general overview of the project activity to textual revisions and access to articles. The core contribution of iChase is to provide a dual-entity exploration for both articles and contributors in a single visualization. It is designed to ease back and forth navigation between articles and contributors, a crucial interaction for a number of scenarios. For example, an administrator identifies a surge of activities on one article, she explores the activities of each contributor for this article, validating most of the revisions, but detecting a potentially harmful contributor. The administrator can review the activities of this contributor, access each article edited by this user while keeping the article she was initially reviewing in view and further pursue her exploration.

In this paper, we first review the related work and describe the results of a participatory design workshop we ran with 16 administrators of Wikipedia 1.0. We describe our design goals and present iChase's user interface. We demonstrate how iChase fits our design goals through a case study and present the results of a usability study with 4 administrators and 4 occasional contributors. We conclude with the strengths and weakness of iChase and future work.

RELATED WORK 2.1 Visualizations of Editing Activities

There have been several efforts on visualizing editing histories on Wikipedia pages. Both History flow [6][12] and JWikiVis [START_REF] Gawryjołek | The Analysis and Visualization of Entries in Wiki Services[END_REF] visualize trends in revision histories by showing relationships between multiple versions of a page and the general evolution of its content. These visualizations are primarily page-centric and do not provide any awareness on the contributors' editing patterns.

WikiDashboard [START_REF] Suh | Lifting the veil: improving accountability and social transparency in Wikipedia with wikidashboard[END_REF] and WikipediaViz [START_REF] Chevalier | Conveying Article Quality for Casual Wikipedia Readers[END_REF] provide embedded visualizations of articles or users activity within each Wikipedia page. Their goal is to increase social transparency and help Wikipedia users to get a better awareness of the editing activities on pages and contributors. However, users have to navigate through multiple pages to understand editing patterns for a set of pages or a set of contributors. Moreover, these visualizations do not allow changes in activity granularity: WikiDashboard only shows daily activity of articles and user while WikipediaViz always visualizes the whole history of an article.

Chromograms [START_REF] Wattenberg | Visualizing Activity on Wikipedia with Chromograms[END_REF] is a more general visualization attempting to characterize the activity trends of highly active contributors by encoding the editing histories for a collection of pages into color bars through a simple color coding scheme. However, rather than providing awareness on contributors' activity to Wikipedia users, Chromograms is a researcher tool, aiming at discovering styles and general rhythms of editing activity on Wikipedia.

In summary, existing visualizations either provide awareness to regular Wikipedia users, reading or editing individual Wikipedia pages or focus on analyzing the global activity on Wikipedia. To our knowledge, there is no visualization supporting our administrators' needs: the exploration and monitoring of a set of pages and a set of contributors.

Visualizations for Bipartite Datasets

The Wikipedia data we wish to explore, contributors and articles, linked by revisions, constitutes a bipartite graph evolving over time. Many datasets are bipartite, i.e., contain two main entity types. Examples include papers written by authors, keywords included in documents or photos tagged by people. Traditional (bipartite) network visualizations (e.g., node-link diagrams [START_REF] Herman | Graph Visualization and Navigation in Information Visualization: a Survey[END_REF]) are not designed to represent links carrying a large amount of information such as a list of textual revisions. Moreover, while there have been several attempts at visualizing network evolving over time [START_REF] Erten | GraphAEL: Graph Animations with Evolving Layouts[END_REF][15], it still remains a challenge to provide users with an overview of the evolution and details of the changes.

Tackling these complex datasets from a different perspective, NetLens proposes a content-actor data model and visualizes the two entity types in symmetric coordinated views [START_REF] Kang | NetLens: Iterative Exploration of Content-Actor Network Data[END_REF]. NetLens allows users to explore the data by iteratively refining queries and interacting with visual overviews and sorted lists in either view.

While it provides similar features to iChase, there are several differences. First, NetLens uses an individual bar graph per entity element (e.g., for the Wikipedia data, one bar graph per article and one per contributor). While this fine grained level of details gives more explicit trends on each element, it requires significantly more screen estate, making NetLens not scale well. Second, NetLens provides iterative query refining by sending filtered elements from one view to the other. Although an interaction history is provided, it remains difficult to keep track of the current view content and of the exploration process. Finally, NetLens does not provide time exploration or multiple levels of details.

Focus+Context Table Visualization

TableLens first applied the Focus+Context technique to visualize large tabular data [START_REF] Rao | The table lens: Merging graphical and symbolic representations in an interactive focus+context visualization for tabular information[END_REF]. In addition to text representation, it used bar graphs for the quantitative variables and colored rectangle for categorical variables. Line Graph Explorer [START_REF] Kincaid | Line graph explorer: scalable display of line graphs using Focus+Context[END_REF] extended TableLens to support line graph data. LiveRAC is another system visualizing a large collection of time-series data organized as a table using Focus+Context technique for exploration [1]. In LiveRAC, rows and columns respectively represent devices and sets of device parameters. Neither rows nor columns are ordered according to time. Instead, the time visualization is represented inside each cell of the table. Thus, each cell contains a multiple line graph representing the evolution of a set of parameter values for a given device. The strength of LiveRAC is to provide a smooth transition from overview to details using the accordion drawing metaphor. While we use a similar Focus+Context technique in iChase, the design philosophy is different. iChase is centered on a unique timeline, each heatmap showing the activities of a set of elements (articles or contributors) over time rather than depicting their correlations with each other. We believe this perspective is better suited to provide general awareness of activity evolving over time.

Participatory design workshop

To better understand the needs of administrators, we organized a one full day participatory design workshop with 16 members of Wikipedia 1.0. During the workshop, we collected their scenarios, discussed their current practice, introduced them to a wide variety of visualizations, and organized brainstorming sessions and video prototyping of their ideal system. From our discussion and the video prototypes, we extracted a set of 4 main tasks and 7 design goals for an interactive visualization.

Tasks and scenarios

To maintain awareness of the activity of a project, our participants currently parse the last revisions and rely on their knowledge of the contributors, articles and activity rhythm of the project to detect unusual activity. Following is a short scenario explaining their current exploratory practice. A large number of scenarios were collected and our discussions with administrators confirm the exploratory nature of their current practice and the serendipitous discoveries that help them build an awareness of the activity. While this makes it difficult to describe their strategy of exploration, we identified four main tasks.

(T1) Detection of unusual activity and tracking of vandalism: this task concerns day-to-day monitoring of the project. Project administrators' time is mostly spent in patrolling: detecting unusual activity and tracking vandalism. They control the content of new articles, of long or numerous revisions on a single article or from a single user, as well as revisions from new or unknown users. They consider this task very important as vandalism affects the credibility of Wikipedia.

(T2) Awareness of articles' status: to make Wikipedia 1.0 happen, administrators need to monitor the progress of all project's articles and to identify the ones requiring more effort.

(T3) Awareness of contributors' interests: project administrators need to be aware of contributor's interests to encourage them to contribute on specific articles or mentor new contributors. They also need to monitor the activity of new contributors.

(T4) Overview of project activity after a long period of absence: our participants reported that it was difficult for them to catch up with the overall activity of their projects after a long absence (e.g., a few weeks long vacation). They reported feeling overwhelmed by the amount of data to review to come back on track with the current state of the project when using existing watchlists.

General Design Goals

From the 5 video prototypes created by our participants and a number of comments, we formulated 7 design goals for iChase.

(G1) Getting an overview of the overall activity of both articles and contributors: providing a dual-focus overview of both articles' and contributors' activity to quickly assess the project activity for a given period of time.

(G2) Exploring revisions on a given article: showing the history of the activity for each article, including the list of contributors who worked on it and the text revisions.

(G3) Exploring revisions made by a given contributor: showing the history of the activity of each contributor, including the list of revisions of the articles she edited. In general, providing awareness of (new) contributors' activity and therefore getting to know their interests is important to invite them to work on specific articles or to collaborate with other contributors.

(G4) Accessing text revisions, whole articles' and contributors' details: providing detailed information and content of articles and revisions; providing information about contributors.

(G5) Identifying salient activity (e.g., outlier detection): supporting the identification of unusual, salient activity on the project is important to track vandalism and control the content of articles and revisions. Examples include excessive activity of a particular contributor on a particular article or numerous revisions.

(G6) Supporting iterative queries: back and forth navigation between articles and contributors. We named iterative queries the navigation our participants perform when successively exploring the activity of articles and contributors. An example scenario using iterative queries is provided in section 3.1.

(G7) Maximizing the recall: when monitoring dozens of articles and contributors, it is difficult to review all the changes and quickly assess the project's progress when logging in after a rather long period of time. The system should provide a stable visualization, maximizing the recall between each session.

iCHASE

The majority of participants in the workshop led towards augmenting existing Wikipedia pages with interactive visualization. While it would preserve their current practice, augmenting existing article and contributor pages (as do WikipediaViz [START_REF] Chevalier | Conveying Article Quality for Casual Wikipedia Readers[END_REF] and WikiDashboard [START_REF] Suh | Lifting the veil: improving accountability and social transparency in Wikipedia with wikidashboard[END_REF]) fails to support several goals (G5, G6 and G7). For example, administrators are required to navigate from pages to pages to gain awareness of what contributors have been doing or which articles have been edited for a given period of time. This makes the exploration process tedious as administrators need to remember some information while they are navigating the set of pages. It is also hard for them to keep track of their exploration paths. To avoid this tedious page to page navigation, we designed iChase as a stand-alone application.

User Interface

iChase (Figure 2) is built upon an augmented timeline designed to show the activity of two coupled entities at several levels of details. The novelty of iChase lies in the design of this dual-entity timeline and the interactions to navigate within and between two entity types. We considered the following three principles when designing iChase:

1. Simple and compact visual representation to limit the learning phase and provide a glanceable visualization.

2. Interactions to support iterative queries (G6) and to investigate specific activities of both contributors and articles.

3. Scalability to cover the wide range of the number of articles and contributors administrators monitor as well as the time duration they wish to investigate.

Visualization

iChase displays three distinct entities: articles, contributors and revisions (connections between articles and contributors). To help users easily identify each entity within all visual representations, iChase uses a consistent color-coding: green, blue, and purple represent articles, contributors, and revisions respectively. iChase supports two strategies to handle large heatmaps: one for exploration and the other for monitoring. To ensure access to all the data for exploration, iChase offers a scrolling panel for each heatmap. To help users monitor the activity of a project and provide everyday-awareness with minimal interaction, iChase allows users to fit the heatmap in a given view by letting them manipulate the height of rows that are not focused, to show more or less entities; or to aggregate rows that cannot fit in the view (Figure 1). This solution provides a summary of the project activity in a single screen, however there are obvious tradeoffs when aggregating items and summarizing activities. Indeed, it might be difficult to detect outliers and irregularities when using aggregated rows.

Aggregated row indicators (Figure 2(4))

. iChase provides additional visual representations to summarize activity in each row to help users detect and compare the editing activity of articles or contributors. For example, for the article row, the two rectangles in each row represent the number of active contributors and the total number of revisions, respectively, for a specific period of time. To remain consistent, iChase color-coded these cells according to their entity type. iChase also shows actual values to ease comparison as color intensities might be difficult to differentiate for small differences.

Activity line graphs (Figure 2(6)). The two line graphs placed opposite to each other show the number of edited articles and active contributors, respectively, over time. They help users understand the general trends and rhythms of editing activities over time.

Legend (Figure 2(5)). The legend summarizes the total number of articles, contributors, and revisions currently shown in iChase.

It also serves as a reminder of the color coding of each entity.

Interactions

Mouse over (Figure 2(9)). iChase offers visual and textual feedback when users place the mouse cursor over visual elements. For example, when users move the cursor over a purple cell, iChase highlights both the column of the corresponding time point and the row of the corresponding article or contributor. In

The time range and granularity of the data visualized are showed in (1). In iChase time is represented horizontally; timestamps indicated at regular intervals (2). The first heatmap (3) represents the set of articles monitored in this project including the total number of contributors and revisions for each article (4). A legend shows the number of articles, contributors and revisions active for the given time range (5). Two line graphs indicate the evolution of the number of articles and contributors active over time (6). The second heatmap contains an expanded row (7) representing a given contributor and the two articles he has edited. The rest of the heatmap is collapsed to provide context (8). A summary is provided for collapsed contributors on mouse over (9).

addition, iChase provides a tooltip showing the detail information (the time, the number of edited articles or active contributors, and the number of revisions the cell contains). When users move the cursor over the line graphs, iChase highlights the column of the corresponding time.

Drilling into time. iChase visualizes editing activity over a consecutive time range at different granularities. It provides interactions to drill down into time and display more details about these activities using a Focus+Context technique. Clicking on a column (either over the column header of the heatmaps or the activity line graphs) expands the corresponding time range by stretching the column to occupy the available screen width, and displays more information on the revisions.

Rather than allowing users to alter the content of Wikipedia pages through iChase, we chose to provide links towards pages.

Clicking on one of these links opens the Wikipedia page showing the difference between the original article content and its content after the revision in the default web browser. From this web page, users can reach the article content and its history of revisions if desired.

Drilling into entities (Figures 2(7) and 2(8))

. iChase supports exploration of the activity of a given article or contributor more in details. When users click on the corresponding row header, the selected row is expanded and the rest of the heatmap rows are collapsed into a minimum height. We decided to collapse nonselected rows instead of filtering them out to provide the user with contextual information. For example, the collapsed rows can convey the general trend of activity even with 1 pixel height. Placing the mouse cursor over a collapsed row shows a tooltip feedback, thus helping users decide whether or not to select the collapsed row. When expanding a row (e.g., an article), iChase displays more details about its activity by breaking down the row into several sub-rows representing the activity of each contributor on the selected article. When an article is in focus, the blue line graph is filtered and shows the number of contributors editing this article during that time span. In addition, the cells containing revisions on this article are highlighted with a green border in the contributors' heatmap. Similarly, when a contributor is in focus, the green line graph is filtered, showing the number of articles he has edited during that time span, and corresponding cells in the articles' heatmap are highlighted.

To support back and forth navigation (iterative queries), iChase provides an interaction on the sub-rows. When users click on the sub-row (e.g., a contributor of the focused article), iChase emphasizes the row (representing the selected contributor) in the other heatmap by highlighting its border. To further help users identify the focused row, iChase also fades out other rows. In addition, iChase expands the row to show the articles this particular contributor has worked on. When users click on one of the articles this contributor has changed in the second heatmap, iChase collapses the previously selected article (in the first heatmap) and expands the new corresponding article.

Collapsing rows and columns. As described above, iChase offers a two-level exploration: users can drill down into time (columns) and/or into rows (articles or contributors). Thus, users can reach the lowest level of a cell in two distinct ways (first expand time, then article/contributor or the inverse). To provide a consistent behavior, iChase uses left click on rows and columns to expand them. Left click on a cell expands the row and column together. Right click on rows and columns collapses them. Right click on a cell collapses the corresponding row and column at once.

Animations.

To help users understand the change of view when expanding a row or column, we provide animations inspired by accordion drawing [START_REF] Kincaid | Line graph explorer: scalable display of line graphs using Focus+Context[END_REF].

Implementation and Performance

iChase prototype is implemented in C# using the Windows Presentation Foundation (WPF) framework. iChase can handle thousands of revisions on hundreds of articles and contributors on a standard Pentium 4 PC. When disabling animations, iChase can handle more than 30,000 revisions in interactive response time.

CASE STUDY

We demonstrate how iChase supports our design goals using 4 WikiProjects: Louvre paintings (Figure 1), French Revolution (Figure 2), Mario Sports Games (Figures 3,4, and 6) and Winter Olympics (Figure 5).

Overall Activity (G1)

The activity line graphs, the repartition of the cells in the heatmaps and their color intensities are the primary elements depicting the overall activity of a project and help administrators catch up after a long period of absence (T4). For example, the line graphs in Figure 1 show that there was no activity on 8/6 and that the most active period was two days after. The overall symmetric shape of the activity lines indicates that the editions were mostly done on a 1:1 basis, i.e., generally one article was edited by one contributor. By glancing at the articles heatmap ordered by number of active contributors, the administrator can assess that Massacre at Chios was the main focus of this week's activity while the users heatmap reveals that Jonathanriley was the most active contributor. Figures 2 and3 show two additional examples. Figure 2 depicts a regular activity (mostly with a 1:1 pattern) whereas Figure 3 shows a burst of activity in the last third of the period, in which many users have been editing a few articles. Heatmaps in both pictures reveal a different everyday activity.

The French Revolution project (Figure 2) shows activity on many articles, whereas only two were active in Mario Sports Games (Figure 3). In addition to the activity line graphs, legend giving the raw numbers of active contributors, articles and revisions, help to detect unusual activity.

Exploring Revisions for an Article (G2)

By observing the article heatmap, users can detect a burst of activity and investigate the rhythm of edits of a specific article. For example, the first article of Mario Sports Games (Figure 3) suddenly shows a burst of activity: a succession of horizontally aligned dark squares after none activity. It actually corresponds to the creation of the article. By expanding this article, one can see revisions from multiple contributors each day (Figure 4). Figure 4 shows that only three contributors edited repeatedly over time while the others were punctual writers. In addition, the line graph is filtered and shows the activity of the contributors for the selected article (Figure 6(a)). One can immediately identify that the burst of contributor activity on the project was caused by this first article. As a comparison, Figure 6(b) shows the activity of the second article, exhibiting a more regular pattern. Finally, zooming in time and reviewing the revisions' details reveals that content was added mostly on sections -characters‖ and -development‖ during the first three days. Then information was suppressed by lack of reliable sources and finally, typos and formatting were fixed. This type of information helps administrators assess what are the states of given articles and their creation history (T2).

Exploring Contributors' Revisions (G3)

Glancing at the heatmap of the contributors of Mario Sports Games (Figure 4) reveals two distinct rhythms of activity for the two most active contributors. The second contributor edited a single article in a short period of time and gradually became less active. This is visually conveyed by a succession of dark squares. The first contributor (New Age Retro Hippie) has a much more regular activity as showed by the dashed pattern and worked on multiple articles. By expanding this contributor (Figure 3), one can notice that he mostly edited one or two articles at a time, except for a particular day where he edited 8 articles together.

Zooming into the revisions for this day reveals that he created a general page on Mario Sports Games and added a link towards it in each individual article.

Accessing Text Revisions (G4)

Some patterns detected in the heatmap can draw attention to particular revisions. For example, several contributors editing an article repeatedly in a short period of time may indicate that they have successfully collaborated or, on the contrary, that they disagreed on a particular section. The presence of vertically aligned dark squares on the same article depicts this salient activity (Figure 5). To identify if the activity rhythm of these contributors is fortuitous, positive or negative, one needs to access the comments and text of the revisions. On the Olympic village article (Figure 5(b)) for example, by clicking on the successive revisions to access the details, one can identify that both Dereckchang85 and Skookum1 edited at the same time period twice. Accessing text revisions shows that Dereckchang85 is adding content to the article while Skookum1 is fixing the formatting template. Further review of the revisions reveals a warning message from Skookum1 ordering Dereckchang85 to stop altering the template. This information is important since new contributors may feel rejected or offended by more expert contributors. By noticing this conflict, the administrator may contact Dereckchang85 and suggest him an appropriate mentor (T3) to keep him involved in the project.

Identifying Salient Activities (G5)

iChase attracts administrator's attention on salient activity (T1) in multiple ways. First, by looking at the activity line graphs, administrators can detect unusual or irregular activity patterns such as drop or peak of activities. A peak in the articles line indicates that many articles have been edited at that time. If the contributor line does not reflect this peak and shows a very small amount of active contributors, it may suggest suspicious or repetitive activity such as contributors or robots fixing format and typos. The burst of activity of the line graph of Mario Sports Games (Figure 3) is worth investigating. By clicking on the top most active article, the line graph shows that the burst is due to this article (Figure 6(a)). This information shows individual activity rhythms and helps detect salient patterns. As administrators have their own knowledge of the regular project activity rhythms and external information on the project contributors (such as vacation time), they can detect irregularity or outliers on the heatmaps. We identified a few patterns indicating a potential irregular activity (Figure 5). They mostly consist in several contributors editing in a short period of time possibly repeatedly. As administrators have previous knowledge of the contributors' activity, identifying the name of a given contributor in these patterns may also help them quickly assess the situation.

Supporting iterative Queries (G6)

iChase supports iterative queries by providing two different perspectives on the data (articles' perspective and contributors' perspective) and a simple mechanism linking them. Salient activity is the entry point of iterative queries; iChase provides interaction to track the suspicious activity of this contributor. iChase supports the scenario described in 3.1 in a couple of clicks.

Stable Visualization for Monitoring (G7)

To maximize the recall when logging multiple times and provide a stable visualization, iChase maintains the order of heatmap rows from session to session. To help monitoring, we also envision adding visual clues on the activity evolution (by adding an up and down arrow to show the article activity since the last logging).

USER STUDY

We collected feedback on iChase from 8 participants: 4 administrators and 4 occasional contributors. After presenting the visual encoding and interaction available in iChase, we asked our participants to analyze two datasets of our case study (Winter Olympics and Mario Sports Games). The administrators were also provided with one month activity of their own watchlist as an additional dataset. To collect maximum insights without over guiding our participants, we divided the study into three phases. First, we asked the participants to describe any insight that they found in the data. Second, we asked more guided but still highlevel questions (e.g., compare the editing rhythm of two given contributors). Finally, we asked specific questions (e.g., find contributors working on the same two articles) in order to cover all of iChase's features. During the session, we asked our participants to think aloud: 1) insights they found in the data, 2) describe their strategy and 3) point out usability issues. In addition, administrators had to fill out a questionnaire comparing iChase to their current monitoring tool that mainly consist of textual list of revisions.

Insights found with iChase

We collected about 50 insights from these datasets prior to the study. We made a note each time the participants found one of the 50 listed items. All 8 participants discovered them all, and mainly during the first two phases (without experimenters asking specific questions). All of the administrators agreed that iChase allows them to keep track of contributors and articles activity (T2 and T3), possibly after a long period of absence (T4), and help them detecting abnormal or suspicious activities (T1).

All administrators commented that it was especially easy to detect potential vandalism using iChase.

Usability

As many new visualization tools, iChase requires some learning time. It took occasional contributors the first half of the study (around 30 min) to learn to decode the heatmaps and discover the tight coupling between these. Only one occasional contributor did not take advantage of the iterative queries. However, she could still answer all the questions. The administrators were particularly fast in learning iChase (around 15 min) and used all of its functionalities. One of them was provided with the tool without any explanations and was able to use and describe all the features after only 10 minutes of practice. This reveals that iChase can be used by a wide audience with a reasonable learning time.

Overall, our participants reported a small number of minor usability problems. The major one concerned the right click to close rows and/or columns. Almost all of them commented that they got lost when closing a cell, and that they expected closing their last opened item (row or column) instead of closing both row and column. We agree and will fix this issue.

Comparison with existing tools

Administrators participating in the study all used textual lists of revisions (a tool called LiveRC [START_REF]LiveRC (Live Recent Changes[END_REF] or watchlist). We asked them to rate iChase and their current tools for four aspects using a Likert scale from 1 to 5 (see Table 1). iChase received higher scores than their current tool in all aspects. When asked if they would use iChase to replace their current tools, all 4 administrators answered that they probably would but only with real time feeds (our study was done with archived files). Finally, they commented on the usability of iChase: -iChase is pleasant to use and to look at. 1: Administrators ratings from 1 (worst) to 5 (best) for iChase and their current tools. Average (Standard Deviation).

Missing features

All the experts asked for more information on the type of contributor (e.g., bot, IP address, registered, administrator, etc) and to mark revisions identified as revert. They also requested shortcuts to perform administrators' actions: revert a revision, block a contributor, access a discussion page, etc. Concerning the interaction, administrators were mostly interested in marking and filtering heatmap rows. They wanted to color regular, registered contributors (as supported by their current tools) and possibly hide them from the view. They also wanted to filter out articles already reviewed. Several administrators commented that filtering would allow them to refine their awareness of the project activity. They explained that they would probably be aware of highly active articles, but that filtering them out would help them assess the activity on the rest of the articles, which are more difficult to follow. Several participants also asked for more advanced sorting features, such as sorting by total length of revisions for a specific period. Overall, they did not consider these features essential for using iChase but commented on their additional benefits.

CONCLUSION AND FUTURE WORK

We presented a novel visualization called iChase designed and developed to provide Wikipedia administrators with better awareness of article editing activities. Unlike other visualizations that provide only page-centric information, iChase visualizes the trend of activities for both articles and contributors by using two heatmaps synchronized to one activity timeline. iChase makes it possible for administrators to interactively explore the history of changes by drilling into specific articles and contributors, or time points to access the details of the changes. To show the utility of iChase, we presented a case study and a usability study collecting feedback from administrators and occasional contributors.

In the future, we are planning to iterate on iChase to fix the minor usability issues raised by our participants and add the missing features identified by the administrators during our initial study. We plan to run longitudinal studies in situ with Wikipedia administrators to better understand their needs and assess how they use iChase. We also plan to organize a second participatory design workshop focusing on team awareness in order to provide WikiProjects members and administrators with tools to communicate and collaborate more effectively.

Figure 1 .

 1 Figure 1. iChase in monitoring mode of one week activity on the WikiProject Louvre Paintings

Timeline (Figures 2

 2 (1) and 2(2)). In iChase, time flows from left to right and each column represents a particular point in time. Users can set the start and end dates of the data to be visualized and select the granularity of the visualization.Activity heatmaps (Figure2(3)). Each entity type is represented by a heatmap in which rows are individual elements (articles or contributors) and columns are time periods. The cells of these heatmaps are color-coded by the number of revisions that occurred for the corresponding element on a particular time period. These heatmap representations convey general trends about a large quantity of data not by massively aggregating or summarizing them but by representing as many data items as possible in cells potentially very small but varying in color intensity. Therefore, heatmaps convey general project activity awareness while displaying activity at the almost finest level of details. By default, articles are ordered by their creation date. However, users can reorder rows by number of active articles (contributors) or number of revisions.

Figure 2 .

 2 Figure 2. iChase showing the WikiProject French Revolution (12 months). The time range and granularity of the data visualized are showed in (1). In iChase time is represented horizontally; timestamps indicated at regular intervals (2). The first heatmap (3) represents the set of articles monitored in this project including the total number of contributors and revisions for each article (4). A legend shows the number of articles, contributors and revisions active for the given time range (5). Two line graphs indicate the evolution of the number of articles and contributors active over time (6).The second heatmap contains an expanded row (7) representing a given contributor and the two articles he has edited. The rest of the heatmap is collapsed to provide context (8). A summary is provided for collapsed contributors on mouse over (9).

Figure 3 .

 3 Figure 3. Activity Rhythms of the WikiProject Mario Sport Games (4 months)

Figure 4 .Figure 5 .Figure 6 .

 456 Figure 4. Activity Rhythms of Mario Sports Games (4 months)

  For example, they quickly identified contributors editing multiple articles in a short period of time: "Either this user has updated the articles (e.g., updated the formatting) or a bot made these changes or this is an act of vandalism. [With iChase,] I can check the comments and then revoke all the contributions of this user in case he is a vandal." By exploring the activity of his own project, one administrator was able to identify a new contributor and quickly assess his

interests (T3): -This unknown contributor is interested in the same topics as I am! I would like to contact him, either to share sources, to synchronize or to discuss... With the current watchlist, I did not even notice this user has edited several times articles of my project. I would have had to wait for him to become a regular contributor." One administrator explained that he sometimes acted as an external reviewer to help solve conflicts in other projects. He commented on how iChase could help him assess the overall activity of an unfamiliar project: "With iChase, I can understand the overall situation at a glance: who and what articles are concerned, when the conflict started, …"

  The information is visually represented, which is easy to use compare to text lists.‖

		iChase	Current tools
	Overall project awareness	4.7 (0.6)	1.7 (0.6)
	Exploration of articles' activity	4.7 (0.6)	2.7 (0.6)
	Exploration of contributors' activity	4.3 (0.6)	2.3 (1.5)
	Support for iterative queries	4.7 (0.6)	3.0 (1.0)
	Table


Nathalie Henry
email: nathalie.henry@lri.fr.

Anastasia Bezerianos
email: a.bezerianos@nicta.com.au

Jean-Daniel Fekete
email: jean-daniel.fekete@inria.fr.

Improving the Readability of Clustered Social Networks using Node Duplication

Keywords: Clustering, Graph Visualization, Node Duplications, Social Networks

Exploring communities is an important task in social network analysis. Such communities are currently identified using clustering methods to group actors. This approach often leads to actors belonging to one and only one cluster, whereas in real life a person can belong to several communities. As a solution we propose duplicating actors in social networks and discuss potential impact of such a move. Several visual duplication designs are discussed and a controlled experiment comparing network visualization with and without duplication is performed, using 6 tasks that are important for graph readability and visual interpretation of social networks. We show that in our experiment, duplications significantly improve community-related tasks but sometimes interfere with other graph readability tasks. Finally, we propose a set of guidelines for deciding when to duplicate actors and choosing candidates for duplication, and alternative ways to render them in social network representations.

INTRODUCTION

Social networks analysis is becoming increasingly popular with online communities such as FaceBook, MySpace or Flickr, where users log in, exchange messages or pictures, and generally interact with friends or collaborators. Many sociologists perform statistical analyses on these networks, attempting to fit their data to existing models according to a priori hypotheses. However, visual analysis becomes more and more popular as it offers the opportunity to view the raw data in an exploratory manner, without bias or a priori formed analysis questions, and opens new perspectives for previously analyzed datasets.

The most popular visual representation of social networks is nodelink diagrams where persons (actors) are represented as nodes and their relationships as links. An important task when analyzing these networks is examining communities -i.e. groups of actors tightly connected to each other -to understand their relationship and roles. For example, communities clearly emerge when visualizing the coauthorship network of a conference, where nodes are researchers and links represent articles co-signed by other researchers. Different patterns are visible, such as student-advisor relationships or laboratory collaboration relationships. Studying these communities and patterns helps us understand for example who are the most connected/prolific authors and the boundary of their communities. When such communities are identified (for example by clustering algorithms), they can be grouped visually and structurally in a clustered graph (Figure 1a). This community representation suffers from two problems:

Clustering ambiguity: When an actor is connected to two or more communities: 1) most clustering algorithms place the actor in one of the communities (Figure 2 left,center); 2) others place shared actors between their communities, solving the unique assignment problem but increasing link crossings when several nodes belong to several communities; and 3) in few clustering algorithms, communities that share actors are visualized as overlapping clusters, increasing the visual complexity of the graph by introducing node overlap and link crossings due to the tight space packing. Visualizing the overlapping nodes is difficult or even impossible when the number of intersections increases.

Readability: When two communities share many connections, their links intersect and cross several nodes, hindering the identification of the particular actors connected. We qualify layouts with numerous overlapping nodes and edge crossings as having a high visual complexity.

Recently, a hybrid representation called NodeTrix [START_REF] Henry | NodeTrix: a hybrid visualization of social networks[END_REF] improved graph readability by representing clusters as visual adjacency matrices (Figure 1b). As actors are placed linearly on the four sides of the matrix, node overlapping is suppressed and intra-and inter-community edge crossing is reduced. However, when several actors connect two communities, the visualization still suffers from edge-crossings, reducing its readability. Moreover, deciding where to place an actor shared between communities remains a challenge.

To improve readability and solve ambiguous clustering, we propose using actor duplications: introducing new nodes to represent aliases of actors. We implement this idea in NodeTrix. Figure 1 shows a NodeTrix representation before (b) and after (c) duplication. Actor duplication provides flexibility by allowing clustering of shared actors in multiple communities (Figure 2) and may reduce the networks' visual complexity by suppressing links. Nevertheless, it alters the network structure and may affect the user's perception during analysis. This article discusses ways of representing duplications and, through a controlled experiment, examines how duplicating actors affects social networks analysis.

RELATED WORK

Social networks describe persons or organizations (actors) and their relationships. Examples include genealogical trees, disease transmission and communication networks. In this paper, we concentrate on visual analysis techniques to analyze social networks (detailed information on statistical and structural methods can be found in [START_REF] Wasserman | Social Network Analysis[END_REF]).

Exploring social networks involves tasks at several levels [START_REF] Plaisant | Task taxonomy for graph visualization[END_REF]. Low-level readability tasks include: finding if two actors are connected, how many actors lie between them, or if they are connected to the same set of actors. High-level tasks [START_REF] Wasserman | Social Network Analysis[END_REF] include: identifying communities (C), i.e. cohesive groups of actors that are strongly connected to each other; identifying central actors (CA), i.e. actors either linked to many other actors, or bridging communities together; analyzing roles and positions, i.e. interpreting groups of actors (positions) and connection patterns (roles).

Higher level tasks are performed through completion of low-level tasks. For example, if linked actors have a large number of common connections that are themselves interconnected, they most likely form a community. Thus, social network analysis is closely related to network visualization [START_REF] Herman | Graph visualization and navigation in information visualization: A survey[END_REF] and graph drawing [START_REF] Di Battista | Graph Drawing: Algorithms for the Visualization of Graphs[END_REF], and is affected by graph readability issues. However, the decomposition of high-level tasks into low-level tasks is very dependent on the actual visualization system: its visual representations, layout algorithms and provided interactions. Ideally, a good visualization system should allow most important tasks to be performed quickly and effortlessly through interaction and visual scanning, to help users gain insights on the social network they study.

A large number of systems exists for visually analyzing and representing social networks, the vast majority of which are based on node-link diagrams: 54 out of 55 according to INSNA1 whereas visualcomplexity2 lists more than 50 systems only using node-link diagrams. The readability of such diagrams has been studied by several authors: McGrath et al. [START_REF] Mcgrath | The effect of spatial arrangement on judgments and errors in interpreting graphs[END_REF] investigated the role of spatial arrangement of nodes in a node-link diagram and showed that node positions strongly affect the identification of central actors and communities. Other factors such as node overlapping or edge crossing affect the readability of node-link diagrams. Purchase [START_REF] Purchase | Which aesthetic has the greatest effect on human understanding[END_REF] and Ware et al. [START_REF] Ware | Cognitive measurements of graph aesthetics[END_REF] showed that edge bends, crossings number and angles affect the completion of connectivity tasks such as finding the shortest path.

Recent systems adopted other strategies to overcome node-link diagram readability problems: NetLens [START_REF] Kang | Netlens: Iterative exploration of content-actor network data[END_REF] and PaperLens [START_REF] Lee | Understanding eight years of infovis conferences using PaperLens[END_REF] abandoned node-link diagrams for simple interactive visualizations, like bars or tables. Albeit effective in performing visual queries on network attributes, they do not adequately reveal topological properties required to perform high-level tasks such as finding communities. Others merge or combine multiple network representations. TreePlus [START_REF] Lee | Treeplus: Interactive exploration of networks with enhanced tree layouts[END_REF] uses a tree layout centered on a node to visualize parts of a network without node overlapping or edge crossing. While effective for connectivity tasks (find paths), performing high-level tasks such as finding communities or central actors is difficult. MatrixExplorer [START_REF] Henry | MatrixExplorer: a Dual-Representation System to Explore Social Networks[END_REF] combines node-link diagrams and visual adjacency matrices to improve readability, but its authors underline the potential cognitive cost of switching back and forth between the two representations.

Clustered graph representation

Clustered graph representations reduce the visual complexity of graphs by grouping nodes, and are well suited to social networks as they highlight important structures, like communities and central actors linking them. A large body of methods [START_REF] Jain | Data clustering: a review[END_REF] exists to automatically identify communities in social networks (computing clusterings). In many cases, algorithms give different clusterings and human interpretation is needed to find a consensus. Social analysts often need to adjust the level of clustering or edit the groups a posteriori. Eades et al. proposed several solutions to draw clustered graphs [START_REF] Eades | Straight-line drawing algorithms for hierarchical graphs and clustered graphs[END_REF], eventually showing several levels of clustering [START_REF] Eades | Multilevel visualization of clustered graphs[END_REF] at the same time. Recently Ask-GraphView [START_REF] Abello | Ask-graphview: A large scale graph visualization system[END_REF] used aggregated graph representation to navigate Fig. 2: Ambiguous Clustering: actors shared among communities in red and green are ambiguously placed in only one community (left, center), or using duplication in all their communities (right).

within very large networks. These representations are particularly effective for small-world networks [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], a common category of social networks that are globally sparse but locally dense, i.e. communities are linked by a few connections and actors.

However, these representations suffer from lack of readability when clusters are connected with many edges. As nodes are grouped close together, it is hard to avoid edge-crossing or to ensure crossings with clear angles. Holten proposed a method to bundle edges together [START_REF] Holten | Hierarchical edge bundles: Visualizaiton of adjacency relations in hierarchical data[END_REF], improving global readability for tasks like determining the two most connected clusters, but losing detailed connectivity information, such as seeing if two nodes belonging to two different clusters are connected. An alternative approach aggregates the links between clusters [START_REF] Auber | Multiscale visualization of small world networks[END_REF], only displaying a single link when any node in one cluster is connected to any node in another. Visual complexity is thus reduced, but detailed connectivity is no longer visible.

Recently, Henry et al. [START_REF] Henry | NodeTrix: a hybrid visualization of social networks[END_REF] proposed merging node-link and matrix representations with NodeTrix. NodeTrix represents clusters as visual adjacency matrices: each node is placed as a column and row in a matrix and links between nodes are marked in the matrix. Note for example in Figure 1b, how the diagonal is "empty" of links, as nodes are not linked with themselves. Since nodes and their links are placed in a matrix, node-overlapping is suppressed and readability is improved inside the cluster. Outside, incoming edge crossing is minimized, as there are four incoming alternatives for each node (2 per column and row). However, ambiguous clustering remains unsolved. Auber et al. [START_REF] Auber | Multiscale visualization of small world networks[END_REF] envision a clustering in which some central actors are extracted in the center of the graph. However, this is based on human interpretation and cannot be done automatically. Although it only partially addresses ambiguous clustering, if many actors that are member of several communities are extracted, the number of edges dramatically increases (extracted actors are connected to almost every actor in all communities), degrading the representation readability.

Information visualization and duplications

To improve readability and cluster ambiguity, we propose the duplication of actors. In the literature the concept of "duplication" is not clearly defined. Several terms exist: duplicates, clones, mirrors or aliases. In graph drawing, duplication is named vertex splitting.

The presence of non-identified duplicates in a dataset is generally considered as noise. It might skew statistics and provide misleading information. However, when appropriately introduced into a network representation, duplications can improve its readability or ease its exploration. For example, Eades and Mendoca [START_REF] Eades | Vertex splitting and tension-free layout[END_REF] show that duplicating nodes can reduce edge-crossing and reveal symmetries, two important aesthetic criteria in graph drawing. In information visualization, examples are scattered among the literature where duplication appears among features of a system with few details given, if any. We particularly noticed duplication use in tools visualizing graphs as trees such as OntoRama [START_REF] Eklund | Ontorama: Browsing rdf ontologies using a hyperbolic-style browser[END_REF] or TreePlus [START_REF] Lee | Treeplus: Interactive exploration of networks with enhanced tree layouts[END_REF]. Thanks to duplications, graphs can be presented as trees by suppressing cycles. In these examples, duplicated elements are displayed using a specific color and, in TreePlus the user can click on an element to see its aliases highlighted. Other examples include genealogical tree visualization systems such as Geno-Pro [1]. Here, duplications are used as a presentation or exploration tool: for example by duplicating married couples, members of each side of the family can analyze their own family sub-tree. In GenoPro, a dash line links the orginial node to its alias.

While duplications are particularly used in systems visualizing trees or graphs represented as trees, to our knowledge, they have never been used or tested in clustered graph representations.

DUPLICATION VARIATIONS AND DESIGNS

As social networks evolve over time, they become denser, suffering more from readability and clustering issues. For example, in a network of twenty years of coauthorship for a specific conference, we observed two common behaviors that particularly challenge the network clustered representation: researchers moving across labs, and researchers co-supervising students. As we will discuss, duplications can provide a clearer picture of such relationships, but we must carefully consider subtle duplication variations and different visual designs.

When to duplicate?

As researchers move to new research labs they change coauthorship communities and become bridges between them. For example, George Robertson worked at Xerox PARC before moving to Microsoft Research. Should he be placed in PARC, MSR, or outside both of them? Considering ten or twenty years of collaboration, many researchers moved or collaborated with different labs (often more than 3), resulting in cluttered network representations that may be also suffering from arbitrary clustering. By duplicating these central actors, we can provide accurate views of the communities themselves (such as their size), while reducing the number of links displayed.

Another common problem is the representation of two senior researchers (from different research groups) supervising a group of common students. Should the students be placed in one group or the other, or should the two groups be merged? Here again we can use duplication in two ways: either by duplicating both senior researchers (to place each one in the community of the other), or by duplicating the group of students. In the second case, more actors are duplicated but it might be more relevant to show all students of each researcher.

Although these examples discuss coauthorship networks, duplication can be used in any type of social network where community assignment and clustering is ambiguous.

How to duplicate?

We investigated two different types of duplication for graph representations having different impacts on readability (Figure 3): Clone: An exact copy of the node and all its connections is created, increasing the number of links in the graph and potentially causing clutter. Split: The node is copied, but its connections are split between the original and the duplicated nodes. A visual connection between the original node and its duplicates is provided (directed link), but not between duplicates.

How to visualize duplications?

Understanding how central actors connect communities is important in social network analysis [START_REF] Wasserman | Social Network Analysis[END_REF], and thus the visual connection between a node and its duplicates should be clear and easily accessible.

Existing approaches color-code all duplicated nodes and use their labels as disambiguation mechanisms [START_REF] Eklund | Ontorama: Browsing rdf ontologies using a hyperbolic-style browser[END_REF], or interactively highlight the duplicates of a node when selected [START_REF] Lee | Treeplus: Interactive exploration of networks with enhanced tree layouts[END_REF]. Other approaches link duplicates [1] to provide more immediate visual connections. Our hypothesis being that visual links are helpful, we examined links that would be easily distinguishable from regular graph links, while minimizing interference. Different preattentive features [START_REF] Treisman | Preattentive processing in vision[END_REF] were considered as parameters in the design of duplication links. To minimize interference with the perception of regular links and create a subtle effect, we rejected early on visualizations attracting attention such as animated links [START_REF] Bartram | Filtering and brushing with motion[END_REF][START_REF] Bartram | Moticons: detection, distraction and task[END_REF], or curly and zig-zag type links such as the genogram of GenoPro [1]. Social networks contain a fair amount of regular links that often cross, thus dotted or dashed lines, or using angular changes or curvature in duplication links, would not be very effective as differentiation mechanisms.

We thus decided on using combinations of color hue, saturation and width, key visual variables to help differentiate duplication links at a glance [START_REF] Bertin | Semiology of graphics[END_REF][START_REF] Card | The structure of the information visualization design space[END_REF], while creating a subtle effect that can be ignored when users are not interested in the duplication. Two designs were considered: representing duplication links as thick de-saturated lines (linkWidth) and regular width links of different color (linkColor). For the linkWidth lines we chose grey color for a subtle effect, but grey was hard to see in the thinner linkColor and was replaced with light orange (same as actor nodes).

In the case of clone duplication all duplicates of a node are exactly the same, but for split duplication, the original node and its duplicates differ, an aspect we highlight in our links. Duplication links in split nodes thus fade out from the original towards the copy. To minimize confusion, we feel that for split nodes all duplicates should be derived from a single original node (1 level duplication) and not from other duplicates, easing the identification of the original node. An experiment was performed to determine the effect of the different duplications types and designs described above. Two types of duplication were used: complete Clone duplication (actor and all its connections duplicated) and Split duplication (only actor node duplicated). For both types, two design variations were considered for expressing the duplication connection (link between duplicates and original actor): links of the same width as other graph links, but of different Color (orange); and links of larger Width and faint grey color. Thus the examined duplication visualizations were: cloneLinkColor, cloneLinkWidth, splitLinkColor and splitLinkWidth. These were compared against two base case visualizations: first, clone duplication with color coding (orange) of duplicated nodes [START_REF] Eklund | Ontorama: Browsing rdf ontologies using a hyperbolic-style browser[END_REF][START_REF] Lee | Treeplus: Interactive exploration of networks with enhanced tree layouts[END_REF], indicating their special nature cloneNode. No link between original actor and duplicates was present. And second, against noDuplication to explore potential issues in using any type of duplication.

During a pilot study, we found that the representation of duplication links using color (cloneLinkColor and splitLinkColor) performed somewhat worse than the visualization that represents duplication links as faint grey thick links (cloneLinkWidth and splitLinkWidth). This was especially true in tasks where duplication may hinder performance. As one participant noted "it is easier to perform tasks using the grey thick lines, because I can ignore them when I want to", indicating that grey links of larger width are easier to distinguish from other graph links and can be ignored more effectively. For our experiment we decided to use the grey thick links to visualize connections between duplicates, to limit interference with the remaining links of the graph.

Thus in the main study participants performed tasks using four visualizations: cloneLink and splitLink (links between duplicates are faint grey lines of large Width -Figure 3), cloneNode (no links between duplicates of actors -Figure 4a) and noDuplication. In all duplicated conditions (including cloneNode) participants could interactively select a duplicated node/actor to highlight all its duplicates in the graph in red [START_REF] Lee | Treeplus: Interactive exploration of networks with enhanced tree layouts[END_REF].

Tasks

We decided to first evaluate duplications against two commonly used graph readability tasks [START_REF] Plaisant | Task taxonomy for graph visualization[END_REF][START_REF] Ghoniem | On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis[END_REF][START_REF] Ware | Cognitive measurements of graph aesthetics[END_REF]. We selected an overview task (RO) and a low-level detailed task (RD).

Task 1 (RO): actorEstimation

Participants were asked to compare the size (number of actors) of two sub-networks. To encourage estimation over accuracy, participants selected one of three answers: larger, equivalent or smaller.

Task 2 (RD): actorConnectivity

Participants were asked to enter the (topological) shortest distance between two actors as a numerical value. In social networks analysis, it is important to identify community structures and their connections (C), as well as central actors and their influence on different communities (CA). To that end we selected another four commonly performed tasks [START_REF] Wasserman | Social Network Analysis[END_REF]:

Task 3 (C): communityConnectivity
Participants were asked to select the two communities that share the larger number of central actors (strongest cohesion).

Task 4 (C): communityCentrality

Participants were asked to select the most central community, the community that shares central actors with the largest number of other communities.

Task 5 (CA): articulationPoint

Participants identified an actor that lies between a community and the rest of the network. Articulation point are described as actors that, when removed, cause one or more communities to become disconnected from the network (graph cut-point). Task 6 (CA): mostConnected

Participants were asked to identify and select the most connected actor: the actor with most connections to other actors (equivalently the node with the largest degree).

These six tasks are representative of general purpose graph readability and social network practices. Moreover, they were selected so as to cover analysis tasks ranging in granularity from overview understanding (actorEstimation), intermediate community structure (com-munityConnectivity, communityCentrality) and central actors (artic-ulationPoint, mostConnected), to detailed tasks focusing on specific nodes or links (mostConnected, actorConnectivity).

Since duplication affects the general layout of the network, the selected tasks are relevant to the topology of the network, and not specific attributes of individual actors or links (another set of common social network analysis tasks [START_REF] Plaisant | Task taxonomy for graph visualization[END_REF]).

Dataset

Generating synthetic representative graphs is still a challenge. As explained in [START_REF] Henry | Matlink: Enhanced matrix visualization for analyzing social networks[END_REF], current small-world generators do not provide realistic models. Therefore, to conduct the experiment using realistic graphs that follow properties of small-world networks, we used subsets of actual datasets: nearly complete coauthorship data for twenty-five years of ACM CHI (Human Factors in Computing Systems) conferences and twenty years of ACM UIST (User Interface Software and Technology) conferences. The labels of actors in the dataset were replaced by codes to avoid interpretation issues. The subsets both contained 130 actors (out of 300 from UIST and 1500 from CHI) in order to fit the graphs on a single screen, suppressing any navigation issues and confounding factors. Subsets of the graphs were carefully chosen (but not altered to preserve the small-world properties) to provide a balanced design: we balanced the link density between graphs, the number of communities, the number of duplicated actors and ensured that communities of actors are always cliques (to make their identification in the noDuplication visualization easier).

Communities and duplications

In social networks, it is important to see both communities and central actors but existing automatic clusterings only give communities. For the experiment purposes, we ensured communities were all cliques and assumed that actors falling into two or more cliques (connected to all actors or the communities) were central actors. We used the edgebetweeness clustering algorithm [START_REF] Girvan | Community structure in social and biological networks[END_REF] implemented in the JUNG [START_REF] O'madadhain | Analysis and visualization of network data using jung[END_REF] package, and edited a few of the communities a posteriori to ensure they were all cliques. All actors belonging to two or more cliques were considered central actors and duplicated. In the splitLink, original actors are placed in the largest community. Similarly, in the noDuplication condition, central actors are placed in the largest community they belong to. We used NodeTrix [START_REF] Henry | NodeTrix: a hybrid visualization of social networks[END_REF] to represent the topological structure of the social network. The graph layout was performed using a manual layout minimizing edge-crossing, tuned from an initial LinLog [START_REF] Noack | Energy-based clustering of graphs with nonuniform degrees[END_REF] algorithm layout.

Density

In order to better understand the effect of duplication, participants were asked to perform the mentioned tasks in graphs of two types of density (Sparse and Dense). We selected graph density as this attribute has been proven to affect task performance in graph understanding [START_REF] Ghoniem | On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis[END_REF]. The density (ratio of existing number of links over all possible links in a graph, a ratio that is fairly small in small world networks [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]) was 0.14 for the sparse, as opposed to 0.19 for the dense one. As both networks had small-world properties, they had a high clustering coefficient (0.86 in both cases).

Participants and apparatus

Twelve participants (1 female) took part in the study. Aged from 23 to 40, they were all researchers or students of a graph drawing research group, to ensure familiarity with computers and graph representations.

We used a 3GHz Pentium IV computer with 1GB of RAM and one 19" screen during the controlled experiment. Participants entered their answers using mouse or keyboard.

Experimental design

A repeated measures within-participant full factorial design was used. The independent variables were Task (actorEstimation, actorConnectivity, communityConnectivity, communityCentrality, articulation-Point, mostConnected), visualization Vis (noDuplication, cloneNode, cloneLink, splitLink), and density Dens (sparse, dense).

Participants were randomly assigned to 4 groups of 3. In each group participants used all 4 visualizations, in an ordering balanced using a Latin square. For each visualization participants completed a single block, containing 2 trial repetitions for all combinations of task (6) and density (2). To reduce memorization of graph layouts between trials, graph labels were randomly generated and the entire graph layout was rotated randomly. The experiment consisted of: 4 visualizations x 2 densities x 6 tasks x 2 repetitions x 12 participants = 1152 trials Before the experiment, participants were interviewed to gather information about their previous experience with graphs and visual representations. A tutorial sheet introduced the NodeTrix representation, the duplications designs and each of the six tasks to complete. An experimenter was present to answer all questions. Participants could then practice with the experimental system for random trials on a training dataset. Training was also given at the beginning of each visualization block. The training sessions lasted 10 minutes on average and ended when the experimenter ensured all tasks and visualizations were understood. At the end of the experiment, participants completed a questionnaire eliciting their visualization preference per task and overall, and commented on the use of the visualizations.

Participants were asked to perform the task correctly as fast as possible. To prevent random answers, if participants felt unable to answer a question, they were allowed to skip it. To limit the experiment duration, task completion time was limited to 60 seconds. Neither of these events occured.

HYPOTHESES AND RESULTS

Task 1: actorEstimation (RO)

H: The use of duplication will degrade the accuracy and performance time for comparing the size of two graphs, as duplicated actors result in larger number of nodes in a graph.

Success Rate (SR): Surprisingly, the Friedman's chi square test showed no significant effect of Vis. This task was very error prone for all visualizations: cloneNode (33% success rate), splitLink (45%), cloneLink (50%) and noDuplication (56%).

Performance Time (PT): A significant effect of Vis on time was present (F 3,33 = 7.43, p < .05), as well as a significant Vis x Dens interaction (F 3,33 = 9.94, p < .0001). Mean times were: splitLink (12.17sec), no duplication (14.18sec), cloneNode (15.16sec) and cloneLink (17.01sec). Post-hoc pairwise mean comparisons showed cloneLink to be significantly slower than splitLink but all other pairs were not statistically significant (all adjustments Bonferonni). Contrary to our prediction, duplications did not degrade performance time and accuracy for this task.

User Preference (UP): Not surprisingly 9 of 12 participants preferred noDuplication for this task, explaining that "the networks to compare feel more different when there are duplications". The remaining preferred either cloneLink or splitLink. However several reported that they "usually overcompensate the number of duplications" and had low confidence in their answers. 7 out of 12 thus ranked this task as the most difficult.

Task 2: actorConnectivity (RD)

H: The introduction of duplication will negatively affect the performance time and accuracy of counting the distance between two actors, as extra duplication links are introduced between actors.

SR: The Friedman's test showed a significant effect of Vis (p < .05) on Success Rate. Pairwise comparison using the Wilcoxon's test showed that noDuplication (69% success rate) was more accurate than cloneNode (53%) and cloneLink (55%), but not splitLink (65%). For this unique task, we avoid memorization effects by using two different distances to count for each trial: 3 (D3) and 4 (D4). Thus we varied the tasks difficulty and added this independant variable to our analysis. The Wilcoxon's test reveals a significant difference between the task difficulty: D4 (25% success rate) is far more error prone than D3 (95%). If we split the results by task difficulty, the Friedman's test reveal a significant difference for the most difficult task D4 (p < .05). The Wilcoxon's test shows that noDuplication and splitLink perform both better than cloneLink (17% success rate). No significant difference is revealed betwen noDuplication (42%) and splitLink (33%).

PT: A significant effect of Vis on Time was present (F 3,33 = 5.99, p < .05), as well as a significant Vis x Dens interaction (F 3,33 = 10.31, p < .0001). Mean times were: noDuplication (21.13sec), splitLink (23.96sec), cloneLink (24.90sec) and cloneNode (27.66sec). Posthoc pairwise mean comparisons showed cloneNode to be significantly slower than both cloneLink and noDuplication. Analysis split by task difficulty showed that there was no difference in Vis in the sparse graphs. In the dense graphs cloneNode was significantly slower than all other visualizations, whereas noDuplication was faster than clo-neNode and cloneLink, but not from splitLink (all adjustments Bonferonni). Although we expected duplications to degrade time performance, this was only true in the clone duplication cases (cloneNode and cloneLink). SplitLink did not significantly degrade the performance time or success rate compared to noDuplication.

UP: Surprisingly only 4 out of 12 participants preferred the noDuplication condition for counting the distance between two actors, saying it was easier "as you did not need to go through an extra link of cost 0". From the duplication conditions, splitLink was generally preferred (4/12 ranked it first, 5/12 second). Several participants reported that it could be "tricky to see where the link goes" in noDuplication whereas "duplications cleans the graph" and "makes it easier to see the shortest path".

Task 3: communityConnectivity (C)

H: The introduction of duplications (especially using links) will allow for faster and more accurate identification of the two communities that share the larger number of actors.

SR: The Friedman's test showed a significant effect of Vis (p < .0001). As expected, the Wilcoxon's test showed that all three duplication visualizations performed better than noDuplication (only 33% sucess rate). Identifying actors (nodes) that are clustered in one community but belong to others is a harder task than counting duplicated actors. SplitLink was the most accurate visualization (96% success rate), followed by cloneNode (86%) and cloneLink (82%). splitLink was also significantly more accurate than cloneLink (p < .05). The better accuracy of splitLink is due to the "cleaner" resulting graphs, where links of the duplicated actors are not duplicated themselves.

PT: There was a significant main effect of Vis on Time (F 3,33 = 22.63, p < .0001) and a significant Vis x Dens interaction effect (F 3,33 = 6.5, p < .0001).

Mean times were: splitLink (20.28sec), cloneLink (20.72sec), cloneNode (31.07sec) and noDuplication (35.58sec). Post-hoc mean comparisons showed splitLink and cloneLink to be significantly faster than both cloneNode and noDuplication. This behavior was present in sparse graphs, but in the dense graphs noDuplication was significantly slower than all the duplication techniques. Indeed times in the case of duplication using links (splitLink and cloneLink) were generally faster, as it is easier to notice the width of the duplication link bundle going to different communities to identify the two communities that share the most actors. Nevertheless, in dense graphs even simple cloneNode outperformed noDuplication, as looking for duplicated actors is easier than counting links from actors to other communities.

UP: 11 of 12 participants preferred duplication techniques for this task, with splitLink and cloneLink being the most preferred (5/12 each). Participants reported that "grey lines tell the story", that it was easy to estimate the width of the grey lines to see communityConnectivity. They described splitLink as "cleaner", but as grey lines between multiple duplicates of the same actor were missing, they their confidence was lower. No one preferred noDuplication.

Task 4: communityCentrality (C)

H: Duplications (especially using links) will allow for faster and more accurate identification of the most central community, that shares actors with the most other communities.

SR: Friedman's test showed a significant effect of Vis (p < .0001). Wilcoxon's test showed cloneNode, (25% sucess rate) as more errorprone than the remaining techniques. Also splitLink (92%) performed significantly better (p < .05) than noDuplication (69%), with no difference between cloneLink (82%) and noDuplication (69%).

PT: There was a significant main effect of Vis on Time (F 3,33 = 3.07, p < .05) and a significant Vis×Densinteractione f f ect(F 3,33 = 6.78, p < .05). Mean times were: cloneLink (20.01sec), splitLink (21.13sec), noDuplication (25.83sec) and cloneNode (27.26sec). Posthoc pairwise mean comparisons showed cloneLink to be significantly faster than cloneNode in all graph densities. All other pairs were not significantly different. Contrary to our expectations, the duplication conditions using links did not yield significantly faster times (although their mean times were faster overall), indicating that the normal links between shared actors in the noDuplication condition are enough to identify central communities. Nevertheless, duplications using links make this identification more accurate.

UP: Not surprisingly 11 of 12 participants preferred duplication techniques for this task, with cloneLink and splitLink being the most preferred (often ranked at the same position)(6/12 for each). A participant commented the grey links helped a lot as "you can stop paying attention to the blue (regular) lines and concentrate on the grey only". Several participants reported that splitLink could be misleading as they thought the choice of the original node was decisive. Almost all of them reported that the cloneNode "required exploration" and "many clicks and memorization".

Task 5: articulationPoint (CA)

H: Duplications using links will help in the identification of articulation points (actors bridging two communities), as fewer links are present between communities.

SR: Friedman's test showed no significant effect of Vis on Success Rate: noDuplication(92% success rate), splitLink (90%), cloneLink (88%) and cloneNode (82%).

PT: There was no significant effect of Vis on time, with mean times for duplication techniques being slightly faster: cloneLink (11.32sec), splitLink (12.18sec), cloneNode (13.53sec) and noDuplication (13.85sec).

UP: Almost all participants considered the representations equivalent for this task. 8 of 12 participants reported that this task was the easiest. When asked about their strategy, almost all replied that they "look at the network periphery to find a community linked by a few or single connection". Several reported that splitLink was confusing as they "wondered about missing links".

Task 6: mostConnected (CA)

H: The introduction of duplications will make the identification of the most connected actor (larger number of connections) harder, as the actors are now in multiple communities.

SR: Contrary to previous studies [START_REF] Ghoniem | On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis[END_REF], where datasets were artificially generated and the most connected actor degree increased of 5% between trials, we did not modify our datasets. In the sparse graph, two actors were candidates with only a small degree difference between them, therefore they were both considered as a right answer. Friedman's test showed a significant effect of Vis (p < .01). The Wilcoxon's test revealed a significant difference between noDuplication(94% success rate) and cloneNode(75%) but no difference between noDuplication and cloneLink(90%) or splitLink(81%). CloneLink performed significantly better than cloneNode and splitLink(p < .05).

PT: There was no significant main effect of Vis on Time (F 3,33 < 1), but a significant main effect of Dens (F 3,33 = 46.21, p < .0001) and a significant Vis x Dens interaction effect (F 3,33 = 6.49, p < .001). Mean times were: cloneNode (27.88sec), noDuplication (27.55sec), cloneLink (27.62sec) and splitLink (31.46sec). Post-hoc pairwise mean comparisons showed splitLink and duplication cases tend to be slower than noDuplication in the sparse graph, likely due to the ambiguous couple of candidates as it does not occur in the dense one.

UP: 8 of 12 participants preferred duplication techniques for this task. They explained that they roughly estimated the most connected actor as one that is part of many communities. They also reported that splitLink looks cleaner but that the missing links greatly lower their confidence. Half of the participants reported this task as most difficult.

Overall user preferences and comments

Almost all participants reported that cloneNode, used often in practice, would be useless without node highlighting. Even with it, they describe their strategy as "a trial and error process", tedious and cognitively demanding. Surprisingly, 6 out of 12 participants counted splitLink as their preferred visualization overall (2 for noDuplication, 1 for cloneNode and 3 for cloneLink). When asked why (as splitLink was not ranked first in most tasks), roughly all participants reported that "it looks cleaner" but they feel less confident, as links between multiple duplicates are not present (only between the original and duplicates). However, they all commented that this feeling would probably disappear with more pratice.

Our experiment showed that the most common technique for duplications (cloneNode) performed very poorly, even when coupled with interactive feedback, and that visual duplication links were more effective. Our design choices attempted to create two types of links easily distinguishable by using a subtle combination of color, intensity and width. We hoped that users could pre-attentively identify and ignore the duplication links when needed, thus not affecting the performance of readability tasks (RD and RO) and similarly ignore the regular links while performing community tasks(C). The good performance of duplication across tasks and qualitative results of our experiment indicate that this was achieved. Indeed most of our participants clearly stated that they could ignore one or the other type of links, which was helpful when performing the tasks.

Readability tasks (RO, RD)

We expected duplications to degrade the success rate and performance time of overview and detailed readability tasks, but results from our experiment proved that split duplication was as effective as noDuplication for both tasks.

As our overview task (RO) was particularly error prone, results showing no significant impact of duplications on the performance time and success rate must be interpreted carefully. Previous studies [START_REF] Ghoniem | On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis[END_REF] also showed that counting nodes or links is a particularly error prone task. Some participants reported that the visualization was not familiar and thus estimating the number of nodes was hard. During the pilot, one participant noted that "the matrices increased the visual effect of the number of nodes (because you compare areas larger than the actual number of actors they contain)". This could be considered an artefact of the NodeTrix representation, but should have affected noDuplication and duplication cases similarly.

Interestingly, duplications do not strongly affect the detailed task(RD). Participants even reported the task was easier to perform with splitLink as it suppressed a number of link crossing, making it easier to follow the connections. For clone duplications, the detailed task seems more affected in denser networks, where clone duplication results in multiple copies of regular connections for all duplicates.

Community tasks (C)

Our experiment showed that duplications helps identifying the connections between communities. The visual design showing links has been proven more efficient and almost all participants reported the grey lines were really helpful. Qualitative results from the pilot showed that using a grey thick line instead of a thin line of a different color provides two levels of readability. All participants of the pilot reported that it was easier to concentrate on grey lines and ignore other types of links (and vice versa).

The introduction of duplications also helps to find more accurately a central community, especially using splitLink. Here it is easier to follow the direction of the different duplication links (leaving the most central community), than in cloneLink or noDuplication which suffer from regular link clutter. CloneNode performs really poorly, as the only way to identify central communities is to select all the duplicated actors of a community and identify (through highlighting) the other communities it is connected to.

As duplications solve the problem of ambiguous clustering, they display the true size of communities, providing more accurate comparisons between communities. This task was not part of our experiment, but part of our motivation.

Central actors tasks (CA)

The concept of central actors in a social network is intuitive but hard to perform in a controlled experiment. In practice, it requires several measures (such as computing several centrality metrics) and the interpretation of the actors' attributes. For our experiment, we selected two common tasks that are simple to explain and validate: finding an articulation point and identifying the most connected actor. We expected that these tasks would be positively and negatively affected respectively by duplications. Our predictions were wrong, as no difference was shown for the articulation point while duplications were preferred for the most connected actor.

While using duplications, we expected that summing up all duplicates and their links to identify the most connected actor, would degrade the overall performance, but it only did for the ambiguous case (Figure 5, T6 (sparse)). Most participants reported that they considered the most connected actor as one part of many communities. Duplications were thus preferred, as participants counted the outgoing grey lines or the highlighted duplicates of an actor. This is the only task where cloneNode performed well, as participants directly clicked only duplicated nodes (that are of a discrete color) to find one disseminated across many communities, instead of trying to identify the directions of the grey links.

Although we expected a positive effect of duplications on the articulation point identification, no difference between visualizations was found. All participants stated that they looked at the periphery of the network to find an isolated community, searching for a single grey or blue line connecting it to the rest of the network. This strategy yields good performance in an experiment framework (where participants are required to be fast), but results are to be interpreted carefully. In practice, the most interesting articulation points are the ones which disconnect larges parts of a graph and are usually placed in the center of the graph (where there is far more clutter than on the periphery). As this is a lengthy task to perform (finding an articulation point that disconnects the graph in two maximal subgraphs) and far more cognitively demanding (comparing the impact of several articulation points), we did not include it in our controlled experiment. Thus our results may not reflect the real impact of duplications on the identification of "important" articulation points. Further experimentation is needed to validate our hypothesis that duplications reduce visual complexity, making important articulation points easier to find.

Duplication guidelines

Based on our experimentation, we propose the following general guidelines for node duplications in clustered graph representations:

When to duplicate? (1) To reduce visual complexity in graphs that have many actors shared among communities.

(2) To emphasize central actors that connect multiple communities. To highlight their importance, such actors may also be extracted from their communities when duplicated.

(3) To provide accurate community-centered views, an important aspect of many social network analysis tasks.

How to duplicate? (4) Using either split or clone, but not a combination of the two, as they are both complex representations.

(5) Clone can be used as base case, as it requires less practice (at the expense of cluttering the network). (6) Split reduces visual complexity, but interactive highlighting of the duplication links may be required for novice users.

How to visualize duplication? (7) Simple colored nodes are not enough for representing duplications. Links between duplicates are more effective. (8) To increase readability, visual links that connect duplicates should be easily distinguishable from other graph links. (9) Interactive highlighting of duplicated nodes and links is desirable.

Applicability to node-link diagrams

Our results apply to NodeTrix representations and more generally to clustered node-link diagrams. The difference between these representations lies in how communities are visualized but both suffer from the same readability and ambiguous clustering problems. While Node-Trix improves intra-community readability by removing links crossings, both representations could benefit from duplications to improve inter-community readability (by reducing the number of links) and to provide more accurate views of the communities, showing their actual size and highlighting shared actors.

Concerning standard node-link diagrams (without concrete circled clusters), node duplication requires further investigation as its impact directly depends on the graph layout. Eades and Mendoca presents an early example of duplication to reduce edge crossing [START_REF] Eades | Vertex splitting and tension-free layout[END_REF]. In the context of social network analysis, node duplication would be particularly suited for layouts making clusters emerge. For instance, spring layout algorithms make clusters of nodes appear, shared actors being naturally placed between them. This may cause clutter as these actors have many links towards the communities they belong to. Duplicating shared actors should impact the spring layout, potentially placing each duplicate in a community and thus reducing the inter-community clutter. However, further experimentation is required to understand how duplicating impact these layouts.

CONCLUSION AND FUTURE WORK

Social network visualization is becoming increasingly important with the creation of new online communities and the need to monitor and analyse their evolution and structure. Major challenges facing social network visualization and analysis include the lack of readability of the resulting large graphs, and the often ambiguous assignment of actors shared among multiple communities to a single community. In this paper we propose using actor duplication in social networks in order to assign actors to multiple communities without greatly affecting the readability. After investigating different design alternatives for representing duplications, we conducted a controlled experiment using 6 tasks relevant to both graph readability and social network analysis.

Our results are summarized as a set of design guidelines applicable to clustered node-link diagrams and the recent NodeTrix representation; and useful to both analysts trying to communicate theirs findings using graphs with duplications, as well as visualization experts attempting to create automatically generated layouts using duplication.

Our exploration showed actor duplication to be very promising in social network analysis and representation: community centered tasks were greatly benefited, whereas other tasks were affected little, if at all. Although these tasks were chosen to be representative of current practices, further analysis on a larger set of tasks needs to be performed. Furthermore, duplicating actors presenting other properties than being shared (highly connected or high betweeness centrality actors for instance) provides also interesting prospects.

In the future, we plan to investigate how interaction can support the creation, edition and visualization of node duplications. Our participants already suggested a couple of interesting directions: providing interactive feedback on links, by mousing over them and highlighting all links of the duplicated actor; showing several levels of duplication detail, with a default state in which duplications links are grouped in a bundle between communities (estimation), but become independent (countable) on mouse over; and finally a smooth animation to merge back all duplicates of a node into a single one, to improve the understanding of duplications effects and the impacted network areas.

Fig. 1 :

 1 Fig. 1: Clustered graph representation of the same portion of a co-authorship network. Orange marks represent authors, blue coauthorship and grey duplication links. (a) Clustered node-link diagram with communities circled. (b) NodeTrix representation with communities being adjacency matrices (authors are placed in rows and columns; blue squares indicate co-authorship). Missing intra-community links appear. (c) NodeTrix where actors shared among communities are duplicated in each. Missing inter-community links appear.

Fig. 3 :Fig. 4 :

 34 Fig. 3: Clone and Split duplications examples. (3c) and (3d) represent the same sub-set of a coauthorship network, a single central actor being duplicated in both cases.

Fig. 5 :

 5 Fig. 5: Success rate and time per task per visualization. Significant differences are indicated by * (p < .05), ** (p < .001) and *** (p < .0001).

http://www.insna.org

http://www.visualcomplexity.com

ACKNOWLEDGEMENTS

This work was supported in part by the joint Microsoft-Research/INRIA ReActivity Project.