Dustin Freeman
email: dustin@dgp.toronto.edu

Stephanie Santosa
email: ssantosa@dgp.toronto.edu

Fanny Chevalier

Ravin Balakrishnan

Karan Singh

LACES: Live Authoring through Compositing and Editing of Streaming Video

Keywords: Video editing, video production, compositing. ACM Classification H.5.2 [Information Interfaces and Presentation]: User Interfaces -Graphical user interfaces

Video authoring activity typically consists of three phases: planning (pre-production), capture (production) and processing (post-production). The status quo is that these phases occur separately, with the latter two having a significant amount of "slack time", where the camera operator is watching the scene unfold during capture, and the editor is re-watching and navigating through recorded footage during post-production. While this process is well suited to creating polished or professional video, video clips produced by casual video makers as seen in online forums could benefit from some editing without the overhead of current authoring tools. We introduce LACES, a tabletbased system enabling simple video manipulations in the midst of filming. Seamless in-situ integration of video capture and manipulation forms a novel workflow, allowing for greater spontaneity and exploration in video creation.

INTRODUCTION

Ever since consumer camcorders were introduced to the mass market, video has become a powerful way of capturing and sharing personal experiences. The current pervasiveness of recording devices and social media sites such as YouTube and Facebook has further increased casual video creation and distribution. However, unlike still photography, for which there are reasonable tools for quick, convenient editing, video manipulation typically requires a tedious and cumbersome offline process with tools that are often too complex or unsuited for casual video. This mismatch between the ease at which video can be captured and the difficulty of making edits is evident in the rawness of much of the videos posted in online forums today.

Whether documenting an event, performing surveillance, or recording takes for a scene of a film, the ratio of captured video to useful content is always high. During editing, a great deal of off-line time is devoted to sorting through the corpus of video content to recall, analyze and make cuts. On the other hand, there is often a fair amount of downtime for the camera operator during capture while passively watching the scene unfold. We refer to these two periods of low user activity as "slack time", and explore how overlapping production with pre-and post-production can make video authoring a more spontaneous and less timeconsuming experience. Applying this strategy, we propose the seamless integration of video capture and manipulation operations into the same phase of a fluid workflow to make the authoring of videos more spontaneous and accessible.

We start with a few motivating scenarios of modern casual video production which we feel are under-served by current techniques, and we follow with a related work review. We next examine limitations and issues in the traditional video production workflow, and discuss how the live workflow with LACES addresses these shortcomings, as well as the associated new challenges and opportunities it introduces. We then describe the LACES system and present several use cases brought forth by users in an informal evaluation.

MOTIVATING SCENARIOS

Below are three scenarios where we feel traditional video tools are lacking. These examples target casual video makers collecting footage to be post-processed off-line. This footage can have a range of uses from reviewing and extracting information to producing video creations, which extend beyond short single-clip segments. We aim to demonstrate that the realization of such scenarios should be possible with low overhead.

Scenario 1. Curating Content

Isa is a parkour artist visiting Toronto. At High Park, she encounters another parkour group with a unique style. Isa has a social media following, and wants to upload a highlights compilation of their stunts from her phone. She starts recording the group and collects a series of clips, each focusing on different members as they make numerous attempts at each trick. Even after catching a good stunt, Isa continues recording through breaks and failed attempts to avoid missing anything. She ends up with half an hour of footage which she will review and patch together offline.

Scenario 2. Annotating Content

Jane is a primatologist; Taz is her assistant. They are examining how chimpanzees grasp objects while completing puzzles. Jane is standing behind a camera, and Taz sits across from a chimpanzee. Taz presents the puzzles to the chimpanzee, and helps prompt them when they get stuck or distracted. Jane's goal is to get the timestamp of the beginning and end of each grasping activity, for further analysis by herself as well as others. This is difficult to do precisely -she writes down the timestamp that she thinks is nearest to the start of a grasping activity. She will have to review the video later to refine these timestamps.

Scenario 3. Coordinating Content

Jill and Pradeep are high school students working on a film. The film will have a shot of Jill, dressed as a gorilla, climbing Toronto's CN Tower. Pradeep goes out and films the tower from an arbitrary vantage point on a windy day. Later, they film Jill making climbing motions in a studio. These two videos get passed to an editor, Cheryl, and while compositing, she finds it too hard to line up Jill's motions with the tower. She also points out that it would be nice to have a shot of Jill grabbing the top of the tower from just the right angle. Pradeep is sent out to film the tower from a different angle, and Jill records a few more takes, hoping that Cheryl can make it work in editing.

In the above scenarios, we see opportunities to improve workflows by integrating video capture and postprocessing. This would provide a means for on-the-fly adjustments and spontaneity in the video making process.

RELATED WORK

This section reviews related work in manipulation techniques aiming at improving video authoring, as well as video tools designed for live usage.

Video Authoring

A key component of video authoring lies in the diverse manipulations of raw footage, such as browsing, cutting, assembling and compositing input segments to create a refined output clip. Goldman [START_REF] Goldman | Schematic storyboarding for video visualization and editing[END_REF] and Borgo [START_REF] Borgo | State of the Art Report on Video-Based Graphics and Video Visualization[END_REF] both provide comprehensive reviews of the space. In particular, the latter divides the space into video manipulation, the browsing, editing and compositing of video segments, and video visualization, the visual representation of the segments. We are primarily interested in ad hoc video authoring, and therefore manipulation techniques that are quick and easy to perform in the midst of capturing, as well as visualizations that facilitate understanding or further decision-making about the video at a glance.

Video Navigation

A large body of research has explored video navigation. Scrubbing provides a real-time update of the current frame of the video as the user moves the slider along the timeline [START_REF] Li | Browsing digital video[END_REF][START_REF] Matjeka | Swift: Reducing the effects of latency in online video scrubbing[END_REF]. ZoomSlider [START_REF] Hürst | Interactive Audio-Visual Video Browsing[END_REF] and PVSlider [START_REF] Ramos | Fluid interaction techniques for the control and annotation of digital video[END_REF] explore different dynamics of playback sliders for finer control while scrubbing. Victor demonstrates a comic strip view of the video that may be scratched [START_REF] Victor | Inventing on Principle[END_REF]. We later describe how we apply scratching within our live context. Several projects have explored video navigation through direct manipulation, where the user directly drags objects in the video rather than relying on the timeline [START_REF] Dragicevic | Video browsing by direct manipulation[END_REF][START_REF] Goldman | Schematic storyboarding for video visualization and editing[END_REF][START_REF] Karrer | Draglocks: handling temporal ambiguities in direct manipulation video navigation[END_REF].

Another approach to facilitate browsing exploits visual cues for video content. Most common are thumbnail visualizations, which provide an overview of the entire video stream [START_REF] Hürst | Quantity versus quality: The role of layout and interaction complexity in thumbnail-based video retrieval interfaces[END_REF], or summaries, where duplicate content has automatically been discarded [START_REF] Ma | A User Attention Model for Video Summarization[END_REF][START_REF] Truong | Video abstraction: A systematic review and classification[END_REF]. Enhanced timelines, which augment the seeking bar to make it content-aware, have also been explored to aid quick retrieval of content of interest [START_REF] Alexander | Revisiting read wear: analysis, design, and evaluation of footprints scrollbar[END_REF][START_REF] Pongnumkul | Content-aware dynamic timeline for video browsing[END_REF]. Videotater [START_REF] Diakopoulos | Videotater: an approach for pen-based digital video segmentation and tagging[END_REF] and Swifter [START_REF] Matjeka | Swifter: Improved Online Video Scrubbing[END_REF] are two examples of seamless combination of interaction and visualization, displaying near-context thumbnails during navigation. All of the above navigation techniques have the common goal of facilitating quick access to segments of interest through enhanced interaction or visualizations that spare the user from passively watching the entire stream at normal speed. While they have primarily been designed for offline manipulation, similar approaches are suitable in the context of live manipulation.

Video Manipulation: Editing

We refer to video editing as the act of cutting and joining pieces of one or more sources together in time to make one edited movie [START_REF]The VES handbook of visual effects: industry standard VFX practices and procedures[END_REF].

Effectively collecting video segments of interest is made difficult by the current crude nature of the play/pause status of cameras-they can either be recording, or not. Vine [START_REF]Vine Labs[END_REF] allows for a more fluid time control, where the video only records when the user is touching their finger on the screen, functioning as a quasimode [START_REF] Raskin | The humane interface: new directions for designing interactive systems[END_REF]. In the status quo and with Vine, the captured videos are immutable in that recording applications usually do not support editing, which is therefore performed off-line.

Several techniques support fully automated video editing based on content analysis of the footage, such as the sound track [5,[START_REF] Shrestha | Automatic mashup generation from multiple-camera concert recordings[END_REF][START_REF] Sumner | [END_REF], or by leveraging meta-data captured during recording, such as geographical location [START_REF] Tompkin | Videoscapes: exploring sparse, unstructured video collections[END_REF]. All of these works reinforce the idea that video editing is usually tedious and painstaking, especially when performed separately from and long after the actual capturing. Fully automating the editing process eliminates this problem but is lacking in flexibility and control.

In contrast to prior work, we propose a seamless integration of manual editing capabilities with video capture, enabling quick cutting and slicing of segments of footage on set, in the midst of recording the scene.

Video Manipulation: Compositing

In contrast to editing, video compositing refers to the assembling of video segments together in space to make one composite video, mainly by combining different areas of each source frame [START_REF]The VES handbook of visual effects: industry standard VFX practices and procedures[END_REF].

Live compositing has been addressed for still photographs, with projects such as Group Shot [21], that allow the combination of several pictures of the same scene by rubbing to remove parts of the photo that are undesired. In a similar vein, Cinemagram [START_REF] Factyle | Cinemagram[END_REF] allows users to create hybrid photo and video, instilling dynamics to still images, similar in the spirit of Cliplets [START_REF] Joshi | Cliplets: juxtaposing still and dynamic imagery[END_REF], but more instantaneous.

Live compositing of several video inputs, however, remains an open problem. Some works have explored compositing the present and the near-past together, where a person can directly compose themselves with their own shadow, played with a few seconds delay [START_REF] Snibbe | Body, screen and shadow[END_REF]. Similar systems include Dancing with myself [START_REF] Bartneck | Dancing with myself: the interactive visual canon platform[END_REF], DELEM [START_REF] Jimenez | DELEM -Delayed Mirror[END_REF] and Social Comic [START_REF] Lapides | Social comics: a casual authoring game[END_REF]. These approaches involve specific settings, including a video projector or a green screen, and are limited to a single, pre-determined compositing style. We propose to extend such approaches to any video stream, by supporting simple yet rich compositing capabilities of the live stream with recently recorded videos, while providing instant feedback of the result.

Live Video Authoring

Progress in digital technologies has yielded a new form of movie pre-production: virtual production enables filmmakers to interactively visualize and explore digital scenes using CGI pre-visualizations [START_REF]The new art of virtual moviemaking[END_REF]. Such techniques afford a visually dynamic, non-linear workflow, blurring the barriers between planning, capturing and editing. We bear similar motivation to this process, but with live streaming video.

In the realm of live manipulation of videos, video jockey (or VJ) interfaces have captured researcher and artist attention [START_REF] Hook | A short film about vjs: using documentary film to engage performers in design[END_REF][START_REF] Hook | Waves: multi-touch vj interface[END_REF][START_REF] Taylor | Turning the tables: an interactive surface for vjing[END_REF]. However, these interfaces only allow for live editing of pre-recorded video segments, and do not support compositing operations. In contrast, systems for live broadcasting as traditionally used by television networks do support live capture and editing, but these are typically targeted to professionals and require extensive training, planning and human coordination. Dedicated camera operators and editors are typically working together in such cases, whereas we propose interactions that a single casual operator can perform.

Vaucelle and Ishii [START_REF] Vaucelle | Play-it-by-eye! Collect movies and improvise perspectives with tangible video objects[END_REF] demonstrate a video storytelling interface for children, where several toys have attached cameras. Video recording is toggled by physical gestures. The authors delineate separate video-making activities of rehearsing, recording, and playback. Ryokai et al. explored instantaneous re-use of captured video for artistic purposes in I/O Brush [START_REF] Ryokai | I/O brush: drawing with everyday objects as ink[END_REF][START_REF] Ryokai | Designing the world as your palette[END_REF]. A physical brush records images of real-world texture, and allows users to "paint" these textures onto a special canvas. These are targeted for production of abstract artworks and do not support video authoring in the traditional way. We first describe the traditional video production workflow and discuss the issues and challenges associated with it. We provide a broad workflow description here, encompassing both casual and professional video creation. We identify several limitations, and thus opportunities for exploration. In the subsequent section, we will introduce our proposed workflow within this unexplored space.

The traditional workflow for video production, shown in Figure 1, consists of 3 stages: pre-production, production, and post-production [START_REF]The new art of virtual moviemaking[END_REF][START_REF]The VES handbook of visual effects: industry standard VFX practices and procedures[END_REF]. Pre-and post-production typically take place separately and with different tools, enforcing a linear, forwards-only process and leaving little opportunities for back-and-forth iteration between the different stages.

Pre-production concerns the planning of the video. In professional environments, it includes activities such as brainstorming, designing, and pre-visualizing. The outcomes can be storyboards and scripts, to be used for the controlled, planned capturing of the video segments. In the context of casual or spontaneous usage, planning is not as thorough as in professional filming. An example of this is illustrated in Scenario 3 above, where desired shots are roughly planned out prior to execution.

Production concerns capturing the raw files, which are either informed by planning, as in Scenario 3 or ad hoc recording of live moments, as in Scenario 1. User interaction during capture is mainly passive, where the sole task of the operator simply is to observe the video as it is being shot. If a specific shot is needed, there may be many takes of a single scene before an adequate one is captured, possibly involving re-watching for verification Post-production concerns manipulation of the raw files to generate ready-to-share movies. As with planning, this stage may be bypassed completely for casual users that consider the raw camera data the final product. The level of interaction can then range from minimal clip alteration to extensive, professional production. Actions during this stage include navigation, editing, and compositing.

Video navigation is performed to review footage and locate key moments, in support of editing and compositing. We refer to video editing as manipulating video segments tem-porally. This involves slicing and removal of clips to isolate segments of interest, and assembling clips together. In contrast, video compositing concerns the manipulation of video segments spatially, where all or portions of the image from one clip are mixed or layered with those of other clips.

Editing and compositing are typically off-line processes, in both casual and professional cases. Tool support for video editing can vary in complexity from simple trimming of the start and end of each clip to joining multiple clips together with different transition effects. Video compositing tends to be an advanced practice, and tools supporting such actions are not generally targeted towards casual users. However, as shown in all three motivating scenarios, there can be a wide range of situations which require off-line processing.

Limitations and Opportunities

There are several limitations we perceive with the current workflow that highlight problem areas we seek to address in the design of our workflow.

Slack Time: In the traditional workflow, we observe that both production and post-production have "slack time"periods of low-intensity user activity. Overlapping operations from production and post-production stages allows slack time during capture to be used more efficiently for performing editing and compositing. This makes video authoring a more spontaneous, flexible, and less timeconsuming experience. For example, we see in Scenario 1 that there is opportunity for Isa to cut out footage of failed stunts while the group is not doing anything of interest.

Precision Timing: Desired editing operations are often reactive to precise events in video. For example, a user may want to add a bookmark to a clip when an exciting event occurs, but would not know to do this until the event has passed. Jane from Scenario 2 needs to review footage in order to achieve precision in event time markers. In another case, an interesting event may start before the user is able to turn the camera on-the operator intending to be parsimonious about recording to avoid having to sort through excess video content later.

Workflow Phase Separation: Since the toolsets for each phase of the traditional workflow are separate, a clear choice must be made when transitioning from one phase to another. In Scenario 3 for example, all footage must be captured on site first, and an off-line compositing process follows elsewhere. Since going back to shoot more footage when you have moved on to the post-production phase can be frustrating and costly [START_REF]The VES handbook of visual effects: industry standard VFX practices and procedures[END_REF], the ability to visualize raw video with some rough editing and compositing effects would be beneficial.

Coordination: In the final outcome of a traditional workflow, several different clips may contribute to a scene, whether alternating in time or composited together as with the CN tower scene in Scenario 3. While large production studios can afford to use multiple cameras, with one camera a scene must be recorded twice, inevitably with different timing due to real-world variation. The changes in timing must be later fixed by an editor.

Figure 2. Our proposed live authoring workflow

LACES: A FLUID WORKFLOW

We propose a workflow which blurs the boundaries of the traditional phases of video production, by allowing the colocated, simultaneous and seamless operation of planning, capturing, navigating, and manipulating in the same, fluid, flexible workflow (Figure 2). Our fundamental question is: How can a user interact with a live video stream? The live workflow we propose addresses many issues we find with traditional tools. We will now present the new challenges it presents, as well as design goals for a system supporting it.

Challenges in working with a live stream

Performing manipulation on a live stream while new video content is coming in presents several challenges.

Conflicting operations:

Capturing and manipulating the same video are interfering operations a priori, and traditional video manipulation tools have expected video to be immutably stored in a file. While manipulating requires freeform temporal navigation, capturing will continually extend the file of interest-the meaning of "present time" will be constantly changing.

Catching up: Bezerianos et al. [START_REF] Bezerianos | Mnemonic rendering: an image-based approach for exposing hidden changes dynamic displays[END_REF] discuss the difficulty of interacting with changing content, and techniques to "catch up" when the user did not observe a visual change. Silva et al. [START_REF] Silva | Real-time annotation of video objects on tablet computers[END_REF] present the Hold and Speed Up technique so users may apply annotations to the current frame of a live video. For a user to be able to edit while also paying attention to capture, the system must allow these two activities to share focus effectively-neither one can consume the full attention of the user.

No preview mode: While the saved video output from the system could conceivably be sent through a traditional postproduction workflow, for the purposes of our exploration, the output is live. This means that there will be decreased opportunity to fine-tune a manipulation before it is applied to the live video. However, we see this as a trade-off: the traditional workflow applies video manipulations separate and off-line, whereas our workflow aims to apply these manipulations at the time of filming. We implemented LACES, a live video editing and compositing system supporting our fluid, live workflow (Figure 3). The interface contains three main interactive components: the main viewer, displaying the current video frame, the timeline layers, a stack of timelines featuring the captured live stream and additional layers for compositing, and the workspace, a library area where the user can save and arrange assorted video clips. We provide a set of tool palettes on both sides of the interface, for easy access while holding the tablet with two hands [START_REF] Wagner | BiTouch and BiPad: Designing Bimanual Interaction for Handheld Tablets[END_REF].

Overview

LACES is characterized by the continuous recording of the input video from the tablet. As the user launches the application, the recording of the live stream automatically starts. As time progresses, the associated movie strip progressively builds up in the input timeline layer (Figure 4). Videos clips on LACES timelines move right to left. In the middle of the timelines is a black vertical marker indicating the "present".

The main viewer shows the real-time view of the camera. When passively capturing, the user can use LACES as a traditional recording device. At any moment, the user can interact with the live stream and assorted clips in the workspace. Video clips can be dragged to and from the workspace or the timeline layers.

There are 3 timeline layers, ordered from top-to-bottom as foreground, input, and background (see Figure 3). The foreground and background timeline layers start empty, while the system continually adds new frames from the camera to a clip on the input timeline layer.

Video can be sliced at the input and dragged to the workspace or to other layers, in which case the viewer outputs the blended view of all clips including the input overlapping at the present marker. The real-time input stream can be blended with other camera footage, displaced it into the past, or even hidden from view to place focus on a prerecorded video clip in one of the other layers.

LACES provides several features to users, with interactions that can be performed while capturing: clip control, frame editing, clip transform control, layer control and saving.

Clip Control

Slicing and Bookmarking

A typical feature of video editing is the chunking of video into clips that may be sliced and arranged into sequence. We provide slice and bookmark buttons. The slice button separates the current clip into two clips on either side of the slice, and the bookmark button adds a marker to that frame within the clip. By default, if the user presses the slice or bookmark button, the corresponding operation is applied to the current real-time frame in the input layer clip-cutting it into two segments, or placing a frame mark for future reference. Slices are colored to provide additional visual cues for recall and organization.

Sorting

Clips can be dragged from the input to the workspace. We think of the input timeline layer as a queue of clips to be sorted. If not dealt with by dragging to the workspace, they move off the timeline to the left. However, removing a clip from the input closes the gap between its neighbouring clips, so all clips may eventually be retrieved.

Re-using

Clips can be dragged from the workspace, or even directly from the input timeline layer, to the foreground or background layer. The display of several clips underneath the present time marker is, by default, an alpha blend in the viewer. The meaning of foreground or background only comes into play with different blending styles, which we will discuss later. We support snapping when the ends or bookmarks of clips are dragged near those of other clips.

Navigating

Inspired by "scratching" as it appears in disc jockey (DJ) performance, the user can move both the background and foreground timeline layers left or right using their finger. If the user simply holds their finger still on a layer, it stops that layer from playing forwards and freezes it on a specific frame (Figure 5a-b). We refer to scratching as moving the medium while the play marker stays fixed, as in our interface or with a vinyl record and a needle. The term "scrubbing" is used when a user moves a player marker while the medium remains fixed, such as with most digital video player interfaces. This is a subtle but important difference-especially if multiple media are playing and one marker indicates the present-time position in all of them, as with our interface.

To support the typical video editing activities of slicing and bookmarking described earlier during capture, but it is very difficult to anticipate the correct time to slice or bookmark a live video stream until after the key event has gone past. To this end, we support scratching the input.

To apply a slice or bookmark operation to a specific time in the recent past, the user places their finger on the input layer. By holding it still, the viewer's display will be frozen at the exact time the user began the scratch. The user can scratch the input layer right to left to tune the exact timing of the desired slice or bookmark, and then press the desired operation's button to apply it to the frame underneath the present time marker.

Since LACES is a live interface, the camera is still recording while the user is performing this operation. We provide a visualization of how new, unviewed video builds up during this operation (Figure 5b). When the user releases their hold on the input timeline layer at the end of any operations they want to perform, the input layer plays at an accelerated rate to catch up to the real time display of video (Figure 5e). The high-speed play is a useful alternative to a sudden transition to real time, giving the user a summary of the video they missed while focusing on their editing operation [START_REF] Bezerianos | Mnemonic rendering: an image-based approach for exposing hidden changes dynamic displays[END_REF].

The user can slice or bookmark previously-recorded clips using a similar technique, with the operation button applying to whatever layer the user is currently touching, or to the input if none are currently touched. We find it possible to perform this bimanual operation without an obvious disruption in the filmed video [START_REF] Goldman | Schematic storyboarding for video visualization and editing[END_REF].

When a user drags a clip from the workspace to a layer, it is possible to lose that clip when it progresses off the timeline. Thus, references each clip are maintained the workspace. Excess clips can be removed from the workspace by dragging them to the recycle bin. Frames in each clip are visualized as a comic strip, with a default frequency of one frame every three seconds. With longer clips, this scale can get cumbersome, so a scale slider is provided to increase the amount of time each displayed frame represents.

Examining our first two motivating scenarios, these simple clip controls would allow Isa to cut discard uninteresting parts and, during such times, recombine shots of cool stunts, which she can add bookmarks for, into a final highlights reel. Similarly, Jane would be able to review footage during capture by scrubbing back to determine precise timestamps corresponding the chimp grasping activites, eliminating the need to review all footage offline.

Frame Editing

Here we discuss options to control the input coming from the camera. First, note that we have a camera flip button that controls whether we use the tablet's back or front camera. Other frame edit controls are applied to frames as they come in from the input: ink annotations, and a variety of methods for creating. Annotations persist on the frame they are drawn over and on subsequent frames. Masking operations are also supported. The results from multiple different masks are merged into a final mask. If a clip has a mask and is blended with another layer, the mask replaces the default alpha blend with a direct pixel overwrite.

To perform background subtraction, the user must ensure the camera's scene will be stable and clear of any foreground objects. As the user taps the button, LACES captures a background frame and immediately begins masking out the background from any foreground. We used a basic hue-based discriminant on a Gaussian-blurred image, followed by an erosion and dilation pass. While this occasionally worked sufficiently in a carefully prepared environment, it did not in real world examples.

To create a user-defined polygonal mask, the user taps the polygonal mask button, and then sketches the mask outline directly on the main viewer. All pixels not belonging to the mask are hidden. This is useful to grab specific portion of a video that is not likely to move significantly.

The magic wand removes all pixels that closely match a given hue. To do this, the user taps the magic wand button and then taps a location on the viewer. The hue in a small region around the tap is averaged, and subsequent pixels that closely match that hue are masked out. This worked well with solid colors. In contrast to the user-defined polygonal mask, this suits objects that will change shape significantly, such as moving limbs and hands.

Multiple masks can be combined-for instance, a magic wand to remove all elements in the frame with a certain colour, and then a user-define polygonal mask to remove the remainder. All annotations and masks can be removed from subsequent frames using the clear button.

Clip Transform Control

We provide traditional panning and zooming capabilities. This is particularly useful when we have multiple video clips playing simultaneously, and want to create a spatial relationship between them for compositing.

Pan and zoom operations are performed directly on the viewer. Similar to the slice and bookmark operations, pan and zoom transformations are applied to the input timeline layer by default, or any currently scratched timeline layer. These operations are keyed to the frame they are performed on, allowing the user to "act out" a pan and zoom sequence as they scratch through a video clip, and then replay the transformations at regular speed as many times as desired.

The user applies a pan by dragging their finger in either dimension on the viewer. While zoom is typically performed with two fingers on touch interfaces, in most of our scenarios the user is holding the interface with both hands and can only operate it with their thumbs [START_REF] Wagner | BiTouch and BiPad: Designing Bimanual Interaction for Handheld Tablets[END_REF]. Thus, we provide a zoom handle on the left side of the viewer. Pulling this handle upwards or downwards increases or decreases the zoom of the current video clip. A tap on the handle resets the pan and zoom.

Layer Control

Each timeline layer can hold a collection of clips. In the input layer, incoming frames will always be added to the last clip. We provide a few simple layer controls.

The foreground and background layers have a loop toggle button. When the button is activated and the present marker reaches the end of a clip on that timeline layer, the timeline layer will shift back to the start of that clip.

The input timeline layer has a hide toggle button. The user can use this to view previously-recorded video on the foreground or background layers, without it blending with the input layer. Input is still recorded even if it is hidden.

We provide a layer link toggle button. By default, scratching any layer moves it independently of the other layers. When the layer link button is activated, a scratch on any of the layers scratches all layers together, preserve intra-layer timing relationships.

In Scenario 3, Frame Editing, Clip Transforms and Layer control as described above could be used to isolate Jill as she performs her climbing motions, scale her as required while filming the CN tower, and layer her climbing clip over this background footage.

Saving

We provide two modes to save the resulting video: saving out, and live saving. Saving out renders all video clips on the timeline, similar to a traditional nonlinear video editor.

Live saving records the stream as seen on the viewer. In contrast to saving out, this preserves any live performance components, such as scratching back and forth.

Device and Platform Information

We implemented LACES on a Microsoft Surface Pro tablet, which provides high performance and memory capacity in a tablet that could be comfortably held in two hands, or one for short periods of time. For video processing, we use Emgu, a C# wrapper of OpenCV. We capture frames from the camera at 30 fps with 424x240 resolution.

INFORMAL EVALUATION

Designing a suitable evaluation was difficult -we could either assess quality of video outcomes from traditional versus LACES workflows, or we could perform a usability study of specific areas of the system (i.e. simultaneous scratching and cutting). The former is difficult, as our motivation for LACES was to enable editing where it did not occur before, and the latter would miss evaluation of the concept of capturing and editing in one interface.

We gave the LACES system to 4 people to use in a selfdetermined manner for extended periods (2 hours to several days each) in their own environments. Our goal was to observe their use cases and creations without imposing specific use scenarios on them, and to observe whether the interaction techniques we presented would be effective in fostering creativity in opening up new options for expression with video.

We found that our informal evaluation participants invented many interesting uses. One collected all clips from a comedy show of a performer laughing, intending to create a long track of her continually laughing. Another prototyped a two-view guitar lesson one could imagine broadcasted on social media. Another notable use case we observed is tracing; tracing is typically done over a still image, and if done over a moving image with a longer duration, it is called rotoscoping. However, our participant noted that tracing over a short, looping clip of a few seconds could lead to sketches that capture the movement sequence.

Participants also saw value of LACES as an improvement over traditional video capture-one referred to it as "organized taping" and noted that "[what] I hate most about [video capture] is getting rid of the chaff because at the end of taping I have all this video I have to go through."

DISCUSSION

We have presented an instance of a fluid video workflow that seamlessly integrates video authoring tasks usually performed at separate phases with different tools. We discuss the performance of this relative to our motivating scenarios, the challenges we identified in working with a live stream, and the potential issues with cognitive load.

Our scenarios motivated a tool that enabled in-situ Curating, Annotating and Coordinating of video content. The LACES workspace, being adjacent to the live timeline layers, affords collecting and arranging video clips without having them disappear, and without committing them to a location on the timeline. LACES' compositing on multiple layers supports coordinating.

The input timeline layer clip was effective in providing access to live footage. One of the subjects described the movement as "initially stressful", but relaxed after recognizing he could collect clips in the workspace instead of having to use them immediately. In terms of the anticipated design challenges of conflicting operations and catching up, we have addressed these with scratching and accelerated playback. For the design challenge of no output preview, the lack of an additional viewer to preview changes is a trade-off to maintaining focus on the live action.

There is potential for the cognitive load of performing capture and editing together to be overwhelming if the user is required to divide focus on both operations at once. LACES accounts for this by providing flexibility in the timing of editing. Interactions such as scratching input and workspace clip pooling allows for editing to be performed when appropriate. We found users naturally edited during slack time-moments of low interest, during or immediately following capture: ideal opportunities where low cognitive load can be capitalized on to perform quick edits.

USE CASES

We present a few use cases, some developed by users in our informal evaluation, to illustrate the design principles and features in this interface, starting with the simple case of collecting interesting sub-clips for later use during capture, and building to complex compositing scenarios. Our accompanying video demonstrates some of these use cases, as well as other interesting examples. At one point, Karim turns to talk to his wife, and shortly after, both of his children sit down to take a break. Karim notices his children stopped dancing and wants to discard this part of the video. He scratches the input timeline layer back to the beginning of the break and slices it, and then scratches to the end of the break and slices again. He drags the sliced clip containing the break from the input timeline layer to the recycle bin. As the input video quickly plays back the live events that occurred while he was editing, he sees that one of his children jumps in a funny way. He scratches the input again to this exact point and sets a bookmark-this would be a good still to send in an email.

Storytelling With Props

Derek is a big fan of the Star Wars movies. His favourite sequence is the floating air speeders navigating through the forest moon Endor in Star Wars VI. This was filmed by compositing a green-screen scene on vehicle models in a studio with footage of a camera moving through a forest.

Derek takes a tablet with LACES and films a "flying" view by walking through wooded area in his local park. He slices and drags the scene clip to the workspace. He then drags the forest clip to the background layer, which now is blended with the live view of the tablet's rear camera. He takes out the speeder toy he brought and puts it in front of the rear camera (Figure 6).

He then moves it around so it appears to be steering to avoid trees. Since the forest clip was filmed at a walking pace, he scratches the layer to increase the playback speed, making the flight appear much faster. As Derek is moving the speeder toy around live, blended with the forest clip, the movement of the speeder toy is itself being recorded. He can slice this clip and overlay it on the live view for yet another walkthrough of the forest. The ability to keep one source of a compositing constant while adjusting the other is very compelling as a prototyping tool.

Overlaying Faces

With a user-sketched polygonal a user can overlay parts of their face on other objects or people in fun and interesting ways. This is seen in popular online videos as The Annoying Orange or the Quebecois Têtes à claques.

When Flint is at a fruit market and comes across a stall of oranges, he is reminded of the funny Annoying Orange videos, and is inspired to use LACES to put his face on an orange. He starts off by using the front camera and makes a few funny faces in anticipation of placing them on a fruit.

Flint presses the polygonal mask button and draws a mask carefully around the boundaries of his eyes and mouth. Once finished, everything outside the mask is blacked out, and he only sees his eyes and mouth. He makes funny faces for a few seconds, looking left and right and wiggling his tongue. He needs to capture a good section of his performance to use as an overlay on the fruit, so he scratches the input layer to the start of his performance, slices it, then scratches it to the end and slices it again. He drags the face-making video clip onto the workspace, then removes the polygonal mask from the input.

Flint presses the "flip camera" button so the viewer shows the stall of oranges in front of him. Flint drags the facemaking clip from the workspace to the foreground layer. He presses the loop button on the foreground layer so that this short clip will loop continuously. The masked part of his funny faces clip is overlaid on to the live view. However, it is not aligned with any fruit in particular, so Flint uses pan and zoom controls to align it spatially. Flint holds his finger on the foreground layer to indicate operations will be applied to it. First, he uses the zoom handle to scale his face down so it will fit inside a fruit. Next, he pans his face so it appears on a fruit by direct dragging on the viewer.

CONCLUSION AND FUTURE WORK

We have presented LACES, a system that combines video capture, editing and compositing to make video production more accessible to everyone. We have presented techniques to perform operations on live, moving media, methods for compositing live action with recently-recorded video, and several compelling use cases for LACES. We believe that that ability to operate on and annotate live, incoming data is important, whether video or not, as it closes the gap between capture and usage of media for any application.

While we have presented several short video authoring use cases, we have not explored scenarios of extended video activities, such as using the tool to help document a live event or produce a finished film, both of which expect a traditional video file as output. Our interactions can be extended for such cases, and we leave this to future work, and limit our exploration of live video manipulation to a smaller scale here.

Figure 1 .

 1 Figure 1. Traditional workflow TRADITIONAL VIDEO PRODUCTION WORKFLOW

Figure 3 .

 3 Figure 3. The LACES user interface, comprising the interactive main viewer (top left panel), timeline layers (top right) and workspace (bottom). Clip modifications can be performed through bi-manual interaction on the layers and side toolbar THE LACES SYSTEM

Figure 4 .

 4 Figure 4. Capturing the live stream as seen in LACES. The main viewer (top picture) shows the real-time view of the camera. The recorded clip is visualized as a comic strip, progressively building up as time passes

Figure 5 .

 5 Figure 5. Manipulating clips on the input timeline layer. The user places a finger on the input timeline layer, which freezes the current frame (a); portions of the clip the user has not seen yet are shaded yellow (b). She scratches the clip into the past (c) then slices it at the desired frame (d). When she releases her finger, the input clip plays back to the present at an accelerated rate

Figure 6 .

 6 Figure 6. Storytelling with props, mimicking a speeder run from Star Wars VI. Demonstrates blending a live and recently-recorded video. The user scratches the previously-recorded video so it runs at a higher speed.

Figure 7 .

 7 Figure 7. Overlaying face on objects. Demonstrates the use of a user-defined polygonal mask.Fighting with YourselfPatrick and his friend Felicity want to play a game where Patrick fights a video version of himself. They find a large wall with a uniform pink colour and Patrick stands in front of it. While Felicity films Patrick, she selects the magic wand and taps a pink part on the wall in the viewer. This masks out any pink pixels in subsequent frames.Patrick turns to the side and makes a punch, pauses, and then makes a kick. Felicity uses our input scratching technique to isolate this clip form the input layer, and drags it to the workspace then clears the wand. The clip of Patrick now consists of a first part where he punches, a brief neutral rest in the middle, and a second part where he kicks.Next, Felicity turns the tablet around, reversing the camera at the same time so Patrick can see himself. She drags the punch and kick clip to the foreground layer and holds it so the middle of the clip, where Patrick is neutral, straddles the present-time marker. This freezes Patrick's previous video in time. Real-time Patrick takes up a position opposite his pre-recorded self. Felicity can choose to play a punch or a kick by scratching the video in one direction or the otherforwards to play the punch section, or backwards to play the kick section, always returning to the middle (Figure8).

Figure 8 .

 8 Figure 8. Self-fighting scenario: From a neutral frame in the centre, scratching right and back produces a kick; scratching left and back produces punch.

  Karim turns on music at home and his two children start dancing to it enthusiastically. He wants to film this to share with friends. Traditionally, he would take out his smartphone and record the entire moment. This results in a large video file, tens of minutes long. Karim could edit this video down to key moments, but this is very time consuming, as after transferring it to his computer he will need to re-watch it to retrieve the interesting segments. If he shares the entire unedited video, it can be boring to watch and cumbersome to upload. Karim needs to be always recording video, but have an ability to mark key moments, and remove uninteresting sections. This ability to edit while recording is what our interface is designed to support. Karim holds the tablet running LACES with both hands and films his children. He is able to see the live view in the viewer, but he can also see a comic strip view of previous frames. As the music changes in style, Karim can press the slice button to segment the input video into separate clips for each style. He drags these to the workspace and arranges them based on the different styles of music.

	Editing during Capture


Giovanni Neglia

Xiuhui Ye

Maksym Gabielkov

Arnaud Legout

How to Network in Online Social Networks

Keywords: Twitter, social network, influence

, where K influential individuals have to be selected. First, even if the user follows or proposes its friendship to the most influential individuals, there is no guarantee that they will follow back or accept the friendship request, i.e. they may not reciprocate. Second, following or proposing friendship is a quite cheap operation in OSNs so that the user can easily change dynamically its set of connections. A third difference in comparison to the classic formulation is that we quantify the influence not only by the number of individuals who actively replicate the information but also who can see the information. We show that, despite these three differences, greedy algorithms have the same theoretical guarantees than in the standard influence maximization problem, i.e. they reach a (1 -1/e) approximation ratio. These greedy algorithms require the knowledge of the whole topology and are computationally expensive because of the inherent cost of evaluating the effect of a cascade. We show by simulations on the complete Twitter graph that much more practical heuristics are almost as effective. For example, exploiting simply the knowledge of degree and reciprocation probability of each node i (respectively d i and r i ), the strategy that selects the nodes with the largest product r i d i performs at most 2% worse than the above mentioned greedy algorithm. Moreover, the even simpler random selection strategy requires only to know the set of users and achieves similar performance when the information replication probability of the cascade process is as large as 1%.

Propagation de l'information dans les réseaux sociaux

Résumé :

Dans ce papier, on évalue comment maximiser l'influence des utilisateurs dans les réseaux sociaux. En particulier, on étudie comment les liens sociaux modifient l'influence dans les réseaux sociaux dirigés (comme Twitter) et non dirigés (comme Facebook). Cette étude introduit trois différences par rapport au problème classique de maximisation introduit dans [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF], où K utilisateurs influents sont sélectionnés. Premièrement, si un utilisateur suit ou propose une relation d'amitié à l'utilisateur le plus influent, il n'y a aucune garantie que l'utilisateur le plus influent accepte la relation, c'est-à-dire qu'il y ait réciprocité. Deuxièmement, créer une relation de suivi ou d'amitié est peu coûteux dans les réseaux sociaux, par conséquent, les utilisateurs peuvent facilement changer leurs relations. Troisièmement, on quantifie l'influence non seulement par le nombre d'utilisateurs qui peuvent répliquer une information, mais aussi par le nombre d'utilisateurs qui reçoivent cette information.

On montre qu'en dépit de ces trois différences, les algorithmes gloutons conduisent aux mêmes résultats théoriques que dans le problème standard de maximisation de l'influence, c'est-à-dire qu'ils atteignent un facteur d'approximation (1 -1/e). Ces algorithmes gloutons ont besoin de la connaissance de toute la topologie et sont coûteux à cause de l'évaluation de l'effet d'une cascade.

On montre avec des simulations sur le graphe social complet de Twitter que des heuristiques simples ont une efficacité proche d'un algorithme glouton. Par exemple, en connaissant simplement le degré d i et la probabilité de réciprocité r i de chaque noeud i, la stratégie qui choisit les noeuds avec le plus grand produit r i d i est seulement au plus 2% moins efficace qu'un algorithme glouton. De plus, la stratégie qui consiste à simplement choisir les noeuds au hasard obtient des performances similaires quand la probabilité de réplication de l'information pour le processus de cascade est de 1%.

Mots-clés : Twitter, réseau social, influence

Introduction

The general problem to select individuals taking into account their network value, i.e. their contribution to information propagation in the network, was first introduced in [START_REF] Domingos | Mining the network value of customers[END_REF], which motivated Kempe et al. to define a general optimization framework in [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF]. Because our analysis extends the foundational work from Kempe et al., we start by summarizing their contribution. They modeled the propagation of information in a social network (e.g. a tweet) using two different discrete-time models. The first one is the order independent cascade model. Nodes with/without the information are respectively called active/inactive. When one node, say it u, becomes active at time t, it has one chance to influence (infect) all its non-active neighbors, who may then become active at time t + 1. From time t + 1 on, node u is still active but no more contagious. The contagion attempts from new active nodes at t + 1 are arbitrarily ordered. The probability of success needs to be specified in order to completely describe the model. A quite general case is when u's success probability to infect v depends on the set S of v's neighbors that already attempted to influence v. We denote such probability p v (u, S). In a decreasing cascade model this probability is non-increasing in S, that is p v (u, S) ≥ p v (u, T ) whenever S ⊆ T . This corresponds to the fact that the more nodes have already tried in vain to infect v, the less likely v is to be influenced by other attempts. Starting from an initial set of active nodes A, the process will stop in at most n -1 steps. The main performance metric of interest is the final set φ(A) of active nodes or better its expected size E [|φ(A)|] σ(A). The second model is the general threshold model. In this case each node has a monotone activation function f v : 2 V → [0, 1], and a threshold θ v chosen independently and uniformly at random from the interval (0, 1]. A node v becomes active at time t + 1 if f v (S) ≥ θ v , where S is the set of active nodes at time t. Interestingly [START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF] shows that the two models are equivalent, in the sense that for any activation functions f v (.), there exist corresponding activation success probabilities p v (.) such that the distribution over final active sets ϕ(A) is the same under both models.

The optimization problem introduced in [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] is to choose the initial set A under the constraint that |A| ≤ K so that the expected size of the active nodes' final set is maximized. The authors show that the problem is NP-hard, but that a natural greedy heuristic reaches a (1 -1/e) approximation factor for the decreasing cascade model (and for the corresponding general threshold model). The greedy heuristic simply incrementally increases the set A starting from an empty set and adding at each time the node v i that maximizes the marginal gain σ(A ∪ {v}) -σ(A). If at each step the selected node is a 1 -ǫ approximation of the best node, then the greedy algorithm achieves a (1 -1/e -ǫ ′ ) approximation factor, where ǫ ′ depends on ǫ polynomially. The key for proving this result is to show that σ(A) is a non-negative, monotone, submodular function on sets,1 then the conclusion about greedy algorithm's approximation ratio follows from known results on such functions [START_REF] Nemhauser | An analysis of approximations for maximizing submodular set functions-i[END_REF][START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF].

An implicit assumption of the influence maximization problem as defined by Kempe et al. is that, once the influential individuals have been identified, they can be recruited in order to spread the information of interest. Recruitment is costly (in terms of money or social investment) and then the available budget limits the number of individuals to be selected to K. In this paper we consider a user of an Online Social Network (OSN) who can only exploit its networking strategy inside the OSN itself in order to maximize its influence, i.e. it can select which other users to follow (in directed OSNs such as Twitter or Google+) or to propose its friendship to (in undirected OSNs such as Facebook), but it cannot recruit them outside the OSN. Due to this different point of view, our problem introduces some new twists. First, even if the user follows or proposes its friendship to the most influential individuals, there is no guarantee that they will follow it back or accept the friendship request, i.e., they will reciprocate. Second, following or proposing friendship are quite cheap operations in an OSN so that more aggressive dynamic strategies are feasible, even if there may be some intrinsic constraints imposed by the OSN. For example Twitter puts a cap on the maximum number of users each account can follow at a given time instant, but the user may dynamically change them, for example replacing those who do not reciprocate with different ones. A third difference in comparison to the classic formulation is that we quantify the influence not only by the number of individuals who actively replicate the information but also who can see the information. Our main theoretical contribution is to show that, despite the differences highlighted, greedy algorithms still guarantee the same approximation ratios in all the different variants of the problem we considered.

We note that in the classic influence maximization problem greedy algorithms require to know the topology of the social network as well as all the functions p v (u, S) for every node v. The same is true in our problem. This information may hardly be available to a user. Moreover greedy algorithms are computationally expensive, because of the inherent cost of evaluating the expected size of φ(A), that can only be estimated by Monte Carlo simulations of the cascade process on the (large) social network graph. The second main contribution of this paper is to show that, from the practical point of view, the user needs much less information and computational resources. We reach this conclusion comparing by simulations the greedy algorithms to much simpler heuristics on the complete Twitter social graph as crawled in 2012 [START_REF] Gabielkov | The Complete Picture of the Twitter Social Graph[END_REF]. This graph has 505 million nodes and 23 billion connections. We show that, if only the degree and reciprocation probability of each node i (respectively d i and r i ) are known, the simple strategy to select the nodes with the largest product r i d i performs at most 2.5% worse than the above-described greedy algorithm. Moreover, randomly selecting its neighbors achieves similar performance when the replication probability of the cascade process is as large as 1% and only requires to know the set of users. Similar results have been observed in [START_REF] Habiba | Working for influence: network density and influential individuals[END_REF]. That paper introduces the effective density, which is the product of the average degree and the replication probability, and shows empirically across many different, but relatively small, networks (with at most 20 thousands nodes) that selecting the highest degree nodes performs well in networks with low effective density, while selecting random nodes is as good as any other strategy in networks with high effective density. The greedy strategy appears to be advantageous only for intermediate densities when the network exhibits a modular structure. Our results can be read in the same way if we extend the effective density to include also the reciprocation probability. Our paper then confirms the empirical findings in [START_REF] Habiba | Working for influence: network density and influential individuals[END_REF] on a much larger network. Moreover, by varying the replication probability of the cascade process, we have explored different effective densities and we have never observed that greedy algorithms offer a significant advantage in Twitter graph. This is another indirect proof that OSNs' structure is not modular, but closer to random graphs.

Problem formulation and analysis

We move now to extend the results in [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF] to actual OSNs. For the sake of simplicity we refer to Twitter in our description of the problem, but the same issues hold in most of the other social networks. Twitter is one of the largest social networks with more than 500 million registered accounts, it allows its users to send short messages called tweets. However, it differs from other social networks, such as Facebook and Google+, because it uses exclusively directed edges (arcs) among accounts. Twitter has no notion of bidirectional friendship, but it allows users to follow other users, i.e. to subscribe for their messages. Following does not require any approval from the user being followed. If Alice follows Bob, then Alice is called a follower of Bob and Bob a following of Alice. Twitter users can retweet received tweets that means forwarding the tweet Inria to their followers. In this paper we use the notation (V, E) to refer to the Twitter social graph, where V is the set of Twitter users and E is the set of directed edges. We orient the arcs in such a way that they show the tweet propagation direction, e.g. if A follows B the arc is directed from B to A because A receives tweets from B.

We evaluate the influence of a user u in Twitter through two related metrics: the average number of users who retweet u's tweets and the average number of users who read u's tweets. By default the tweets of a user are visible to all its followers (even if they do not read them immediately). If we consider the number of retweets, there is a natural one-to-one mapping of the order independent cascade model in our setting, so for the moment we focus on this metric. Let a node be active if it has read the tweet and decided to retweet it. Then the original influence maximization problem can be rephrased as follows: how to choose K nodes that should initially tweet the message in order to maximize the expected number of retweets. In this case p v (u, S) is the probability that node v reads and decides to retweet the message tweeted or retweeted from u, given that the nodes in S have already tweeted or retweeted it. In the original problem formulated by Kempe et al. it is not specified how the K initial users should be infected, i.e., in our language, how should they be convinced to tweet the message. In this paper we focus on a specific user u 0 that is trying to maximize its influence and cannot reach other Twitter users through some external communication network. Then, u 0 can only rely on a smart "networking strategy": it can carefully select a given set of users to follow and hope that these users will follow it back and will eventually retweet its tweets. The strategic choice of u 0 is then the selection of its set of followings in order to maximize its influence. We consider for the moment that u 0 makes this choice once and for all at its registration. We observe that Twitter puts a cap to the maximum number of initial followings that is K = 2000 (this limit is increased when the user gets more then 2000 followers). More formally, let B denote the set of u 0 's followings and let ϕ(B) be the set of nodes that retweets a tweet originally emitted from u 0 . We can write ϕ(B) = v∈V X v , where X v is a Bernoulli random variable, that is equal to 1 iff node v is active at the end of the cascade. Our problem can be formally stated as follows:

Argmax B E [|ϕ(B)|] subject to |B| ≤ K. (1)
In the same spirit of [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF] we assume to know 1) the probability r(u) that a given user u would reciprocate u 0 if u 0 follows u and 2) the probability p v (u, S) that node v reads and decides to retweet the message tweeted or retweeted from u, given that the nodes in S have already tweeted or retweeted it. The knowledge of p v (u, S) is also required for u = u 0 or u 0 ∈ S. The greedy algorithm for Problem 1 corresponds to the following behavior: user u 0 selects K followings one after the other, maximizing at each step the marginal increment of the function E [|ϕ(.)|]. Our first theoretical result is the following. Proposition 1. The greedy algorithm is a (1 -1/e) approximation algorithm for Problem 1.

Proof. Let (V, E) be the social network's graph without node u 0 . Consider a new graph ( V , Ê), where for each node u in V we add a new node u ′ and a link oriented from u ′ to u . Let V ′ be the set of these newly added nodes and h : V → V ′ the function such that h(u) = u ′ . On this graph we define success probability functions as follows: 1 (a) illustrates the graph transformation. We consider now the order independent cascade model on the graph ( V , Ê). u 0 's choice of the set of its followings B ⊆ V corresponds to the choice of the set A = h(B) of initial active nodes in V ′ . Moreover, the probabilities have been defined in such a way that it is possible to couple the two processes so that φ(h(B)) = ϕ(B) + K, where adding K corresponds to the fact that the initial set of active nodes is counted by φ(.)

pv (t, S) = p v (t, S) for t = v ′ and v ′ / ∈ S , pv (v ′ , S) = r(v)p v (u 0 , S) and pv (t, S) = r(v)p v (t, S) if v ′ ∈ S. Fig.
u 1 u 2 u 3 u 4 p p p p u ′ 1 u ′ 2 u ′ 3 u ′ 4 rp rp rp rp (a) reciprocation u 1 w u1 = 0 u 2 w u2 = 0 u 3 w u3 = 0 u 4 w u4 = 0 p p p p u ′′ 1 w u ′′ 1 = 1 u ′′ 2 w u ′′ 2 = 1 u ′′ 3 w u ′′ 3 = 1 u ′′ 4 w u ′′ 4 = 1 1 1 1 1 1 1 1 1 (b) readers
(A ⊆ φ(A)). It follows that σ(h(B)) = E [ϕ(B)]
+K and Problem 1 is equivalent to solve the influence maximization problem on ( V , Ê) with the additional constraint that the nodes can only be selected in V ′ . This does not change the property of the function σ(.), that is non negative, monotone and sub-modular, then the results in [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF] still hold. In particular the greedy algorithm is a (1 -1/e) approximation algorithm for the influence maximization problem defined on ( V , Ê) and then for Problem 1. 2 We now consider a variation of problem 1 where node u 0 is not required to select all the K followings at once, but it can apply more complex dynamic strategies. For example node u 0 can stop following nodes that do not reciprocate by a given time T and start following new users. In this way u 0 can follow during a given time window more than K users (but at most K at the same time) and reach in general a larger number of followers (the number can approach K if there are at least K nodes in the network willing to reciprocate u 0 ). This improvement in comparison to the original problem is obtained at the price of a longer time required to select the best followings. The best possible result achievable by u 0 is obtained if we assume u 0 to know a priori which nodes would reciprocate. For each node v, let R v be the Bernoulli random variable indicating if node v reciprocates node u 0 by time T after u 0 starts following v. Clearly it holds r(v) = E [R v ]. We introduce then the following ideal optimization problem:

Argmax B E [|ϕ(B)|] subject to |B| ≤ K and R v = 1 ∀v ∈ B. (2)
The greedy algorithm for this problem orderly selects K reciprocating nodes. At each step the reciprocating node that maximizes the marginal improvement of ϕ(B) is added to the current set and the success probability functions are left Proposition 2. The greedy algorithm is a (1 -1/e) approximation algorithm for problem 2.

2 Also the results for the case when the greedy algorithm selects at each step a (1ǫ) approximation of the best node can be extended to our case, but for the sake of conciseness we only refer to the simpler case.

Inria

Proof. The proof is analogous to that of Proposition 1. In this case an additional node u ′ is added only for each reciprocating node u, i.e. for each u ∈ V such that R u = 1 and the probabilities can be updated as follows: pv (t, S) = p v (t, S) for t = v ′ and v ′ / ∈ S , pv (v ′ , S) = p v (u 0 , S) and pv (t, S) = p v (t, S) if v ′ ∈ S, where only the nodes v ′ such that R v = 1 need to be considered.

While Problem 2 requires to know a priori which users are willing to reciprocate u 0 , the greedy algorithm can be implemented online without such knowledge. This practical greedy algorithm operates in steps, where each step has a duration at most equal to T time units. At each step the user follows the node v that brings the largest marginal increase in comparison to the already selected nodes assuming that v reciprocates. If node v reciprocates by time T , node u 0 maintains user v in its list of followings, otherwise it removes it. The algorithm stops when K users reciprocate or when there are no more users to select in the network. It is easy to check that the practical greedy algorithm selects exactly the same users that the greedy algorithm with a priori knowledge of the reciprocating nodes would, but it requires in general a longer time to execute. The reasoning above leads us to conclude that: Proposition 3. The greedy algorithm for Problem 2 can be implemented without a priori knowledge of which users reciprocate, and its expected number of retweets is at least (1-1/e) of the value obtained by any online algorithm where each node can be selected at most once and reciprocation delays of at most T time units are tolerated.

Finally, we move to consider the case where user's influence is quantified through the number of users who read its tweet (or better that have the tweet in their stream). This problem can be mapped to a variant of the previous case (where we consider the number of retweets) introducing opportune nodes' weights. We need to change the original graph (V, E) as follows. For each user u ∈ V , we introduce a new node u ′′ and the directed arcs (u, u ′′ ) and (v, u ′′ ), for each node v such that (v, u) ∈ E (see Fig. 1 (b)). We denote V ′′ and E ′′ respectively the set of new nodes and arcs and ( Ṽ , Ẽ) the new graph. By doubling each node, we can separately account for the two roles of a user as retweeter and as reader. Going back to the cascade model terminology, at a given time step if node u is active, the corresponding user has retweeted the tweet, and if node u ′′ is active the corresponding user has read the tweet. In order to correctly model the process, we introduce activation success probabilities as follows: pv (t, S) = p v (t, S) for v ∈ V and pv ′′ (t, S) = 1 for v ′′ ∈ V ′′ . We also introduce nodes' weights w v = 0 for v ∈ V w v ′′ = 1 for v ′′ ∈ V ′′ . Let X v be the Bernoulli random variable that indicates if node v is active when the cascade terminates. The number of users that see the tweet is given by ψ(B) = v∈ Ṽ w v X v where B ⊆ V is the set of followings selected by node u 0 . Two different problems can then be defined depending if the set B has to be selected at the begin or can be changed dynamically, similarly to what is done above. The only difference is the fact that the weighted objective function E [ψ(B)] is considered instead of the unweighted one E [ϕ(B)]. Obviously the function E [ψ(B)] is non-negative and non-decreasing, we can also prove that Proof. We adapt some results in [START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF] relative to the size of the different sets to the case where we consider a weighted sum of the set elements. We need to prove that ψ(B 1 ∪ {z}) -ψ(B 1 ) ≥ ψ(B 2 ∪ {z}) -ψ(B 2 ) for any z whenever B 1 ⊆ B 2 . Let C = ϕ(B) be the (random) set of nodes active at the end of the cascade starting from the nodes in B. Imagine now to start a new cascade process on the graph activating node z, but taking into account the fact that all the nodes in C have already tried to infect their neighbors. This new cascade is called the residual cascade process and has success probabilities p process as S C (z) and the additional nodes in V \ C made active by it as ϕ C (z) . In Theorem 3 of [START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF], it is proven that ϕ C (z) is distributed as ϕ(B ∪ {z}) -ϕ(B). Then it holds:

E [ψ(B ∪ {z}) -ψ(B)] = E   v∈ϕ ϕ(B) (z) w v   (3)
Consider C 1 ⊆ C 2 , and the corresponding residual processes S C1 (z) and S C2 (z). If we couple the equivalent general threshold models by selecting the same threshold at each node, it can be shown (see Lemma 3 in [6]) that pathwise ϕ

C1 (z) ⊇ ϕ C2 (z). It follows that v∈ϕ C 1 (z) w v ≥ v∈ϕ C 2 (z) w v and then E   v∈ϕ C 1 (z) w v   ≥ E   v∈ϕ C 2 (z) w v   whenever C 1 ⊆ C 2 . ( 4
)
Let us now consider two cascade processes whose initial activation sets are respectively B 1 and B 2 with B 1 ⊆ B 2 , if we couple them as above, we can similarly show that φ(B 1 ) ⊆ φ(B 2 ), then

P (φ(B 1 ) = C 1 , φ(B 2 ) = C 2 ) = 0 whenever C 1 ⊆ C 2 . ( 5
)
We can now wrap-up our intermediate results.

Let B 1 ⊆ B 2 , then E [ϕ(B 1 ∪ {z}) -ϕ(B 1 )] = E   v∈ϕ ϕ(B 1 ) (z) w v   = C1 E   v∈ϕ C 1 (z) w v   P (ϕ(B 1 ) = C 1 ) = C1 C2⊇C1 E   v∈ϕ C 1 (z) w v   P (ϕ(B 1 ) = C 1 , ϕ(B 2 ) = C 2 ) ≥ C1 C2⊇C1 E   v∈ϕ C 2 (z) w v   P (ϕ(B 1 ) = C 1 , ϕ(B 2 ) = C 2 ) = C2 E   v∈ϕ C 2 (z) w v   P (ϕ(B 2 ) = C 2 ) = E [ϕ(B 1 ∪ {z}) -ϕ(B 1 )] ,
where we have used Eqs. ( 3), ( 4) and ( 5).

From the general results for non-negative, non-decreasing submodular functions it follows that if selecting all its followings at the begin according to the greedy algorithm that incrementally maximizes E [ψ(.)] guarantees a (1 -1/e) approximation ratio. The same result holds in the dynamic case. Due to lack of space we do not define formally the two problems and the corresponding propositions, but we summarize our conclusions as follows:

Proposition 5. The greedy algorithms for the static and dynamic versions of our problem reach a (1 -1/e) approximation ratio also when the objective function is E [ψ(.)], the expected number of users who see the tweet.

Inria 3 Experiments on Twitter

In this section we present the experimental part of our study. In Section 3.1, we describe the dataset and the methodology that we used to perform our simulations. In Section 3.2 we discuss the results.

Methodology

For our experiments, we considered the simple case when p v (u, S) = p is constant and evaluated different selection strategies on the complete dataset of Twitter as crawled in July 2012 [START_REF] Gabielkov | The Complete Picture of the Twitter Social Graph[END_REF]. This dataset is a social graph with 505 million nodes and 23 billion arcs and requires roughly 417GB of storage in the form of edgelist. A naive implementation of the experiment would require to load the graph into memory and then use Montecarlo simulations of the retweet process in order to estimate the objective functions with high accuracy. The followers of the initial node u 0 would retweet with probability 1, then their followers will retweet with probability p and so on till no new node is retweeting. However we could not afford loading this amount of data in memory with our actual resources. We have overcome this problem by generating a set of pruned graphs. A pruned graph is obtained from the original one by sampling each edge with probability p (and with probability 1 -p the edge is removed from the graph). Computing the set of reachable nodes from u 0 on a pruned graph is equivalent to counting the number of retweeting nodes in a specific sample of the retweet random process, but memory requirement is reduced by a factor p (usually p << 1) at the expense of storage increase, because we need to work on multiple pruned graphs (see discussion below) in order to reach the required accuracy.

Despite this expedient our software was still hitting memory constraints when computing reachability for the larger values of p we considered. To work around this problem we took the following approach consisting of two steps. First we computed the Strongly Connected Components (SCCs) of the graph. Second, we constructed a Directed Acyclic Graph (DAG) by abstracting each SCC as a single node and replace multiple arcs between the nodes with a single arc. Provided that p is quite large, we will observe big SCCs in the pruned graph, thus we can achieve a big reduction in size using our approach. Then we compute the reachability on the obtained DAG and deduce the reachability of the original pruned graph by taking into account the number of nodes in each SCC and the fact that the nodes belonging to same SCC have the same reachability. This approach decreases the computation time, as well as memory and storage requirements (because of the more compact DAG representation).

Another challenging aspect of the simulation analysis is to determine how many pruned graph samples we need in order to achieve a given precision for the estimates of the expected number of retweets. To this purpose we have used two different models that we can only describe shortly here because of space constraints.The first model approximates the cascade process with a branching process, where the probability to have a follower with k followers is kq k / k , where q k is the distribution of the number of followers in the graph and k is the average number of followers (see for example [START_REF] Barrat | Dynamical Processes on Complex Networks[END_REF]Chapter 8] for a justification of such expression). This model requires that different active nodes have different followers and is good only for small values of p. In particular it may be accurate only when the branching process dies out with probability 1, because otherwise the model predicts that the expected number of active nodes is infinite while this number is obviously limited by the total number N (= |V |) of nodes in the graph. The branching process extinguishes with probability 1 if p k kq k / k < 1, i.e. p < 2 × 10 -4 in the considered Twitter graph. The second model addresses the case for p > 2 × 10 -4 . In this case branching process' theory predicts that the process can still extinguish with a probability p ext that is a decreasing function of p. The intuition behind our second model is to couple the branching process and the actual cascade model and assume that the cascade will reach almost all the N nodes when the branching process does not extinguish and a negligible number of nodes when it does. In particular, given that we are interested in providing upper-bounds for the variability of the process, we simply consider that the number of active nodes is equal to a random variable that is equal to N with probability 1 -p ext and to 0 with probability p ext . Some further refinements of the model lead to the conclusion that the number of samples needed to achieve a reasonable prevision is below 100 for all the values of p we considered, i.e. p = 10 -4 , 10 -3 , 10 -2 , 10 -1 . This result is quite surprising, given the high variability of the degree distribution {q k } (that is power law) and the even higher variability of the skewed distribution kq k / k . With the approach described above we have been able to perform our experiments on the real social graph with hundreds of millions of nodes and tens of billions of arcs.

Results

We considered three selection strategies for the user u 0 to select its followers: i) the greedy strategy described above; ii) the high-degree strategy which consists in picking the nodes orderly according to their number of followers (from the largest number to the smallest); iii) the random strategy where followers are selected uniformly at random from the whole set of users. We have performed simulations for four values of the retweet probability: p = 10 -4 , 10 -3 , 10 -2 , 10 -1 . The performance of the random strategy strongly depend on the choice of the random set of followers, Inria so we show 95% confidence intervals in the plots below.

In Fig. 2, we can see how these approaches perform in different situations when the reciprocation probability is equal to 1, i.e. u 0 is followed back from every node it follows. Moreover we consider that u 0 's followers retweet u 0 's tweets with probability 1, while all the others users retweet with probability p. The figure shows the expected number of retweets versus the initial number K of followers u 0 can choose. The average number of followers in the original graph is k ≈ 45, but the effective density, as defined in [START_REF] Habiba | Working for influence: network density and influential individuals[END_REF], is k p ≈ 4 * 10 -3 for p = 10 -4 (in Fig. 2 (a)). Then in this case most of the nodes are not retweeted by any follower, but due to the skewness of the distribution q k (the number of followers can be as high as 24,635,412), there are some hubs in the social network that have an expected number of retweeters significantly larger than 0. The cascade processes from different followers of u 0 do not overlap much (each pruned graph is almost a forest of small-depth trees with a multitude of singletons), so that the high-degree strategy performs almost as well as the greedy algorithm. Due to this structure, the expected number of retweeters significantly increases as the number of u 0 's followers keeps increasing. The random strategy performs very poorly, and basically, even selecting 200 followers, all of them are singletons with a very high probability. When p = 10 -3 (Fig. 2 (b)), the cascade originated from the node with the largest degree is already able to reach about 3 * 10 6 users (roughly 1% of the whole social network) and both the greedy and the high-degree strategy select this node as first. The other followers selected from u 0 using these two strategies bring a much less significant improvement: even adding 199 more followers the expected number of retweeters increases by only 33%. The random strategy starts paying off because there are much less singletons in the pruned graph. Further increasing p to 10 -2 , the contribution of the first follower is even larger and the contribution of the others even more marginal, as it is shown in the plot in Fig. 2 (c). In fact, a non-negligible strongly connected component appears in most of the pruned graphs and a careful choice of the first follower allows u 0 to have roughly one tenth of the nodes retweeting its tweets (this follower is not necessarily in the largest strongly connected component, but can reach it). The other 199 followers provide roughly 5% more retweeters. We observe that the effective density is about 0.4, then more than half of the nodes have 0 out-degree/in-degree in the pruned graphs. The greedy strategy and the high-degree one exhibit here the most significant difference in our set of experiments, but this is limited to less than 2% Interestingly, while most of the nodes do not provide any additional retweet, the probability to randomly pick a node in the largest strongly connected component is now quite high, so that the random strategy provides a small number of retweeters until a good follower in such component (or able to reach it) is selected and then the number of retweeters jumps to a value comparable to that of the other two strategies. These jumps cause the high variability revealed by the large confidence intervals in the figure. Moreover the figure shows how the good follower is very likely to be selected among the first 10-20 nodes. The same reasoning allows to explain also the curves in Fig. 2 (d) for p = 0.1. In this case greedy and high-degree are almost indistinguishable and random has almost the same performance for K ≥ 20.

In the simulation described above we considered that every user u 0 chooses to follow will reciprocate (r = 1). We decided to perform some simulations considering for each user a reciprocation probability determined by the formula r = min{ #followings #followers+100 , 1}, where #f ollowings and #f ollowers are respectively the number of followings and followers for the given user. The rationale behind is that a user with a lot of followers and a few followings is not likely to reciprocate u 0 . In any case we do not claim that this formula has any particular value, apart from allowing us to simply test the effect of heterogeneous reciprocation probabilities. The results for p = 0.01 are qualitatively unchanged as shown in Fig. 3 (a). We have also compared the different algorithms in terms of the expected number of users who can read the tweet. A result is presented in Fig. 3 (b). The number of readers is obviously much bigger than the number of retweeters, but there is no significant difference in the relative performance of the three algorithms.

Conclusions

In this paper we have considered a user of a social network who tries to maximize its influence through a careful networking strategy. We have shown how greedy algorithms guarantee a good 1 -1/e approximation ratio, but much simpler strategies like selecting users with the largest number of followers or even selecting random users may practically reach the same performance on real online social networks.

This research is partially supported by Alcatel Lucent Bell Labs in the framework of the ADR Network Science. The authors would like to thank Alonso Silva (Alcatel Lucent Bell Labs), Paolo Giaccone (Politecnico di Torino) and Damien Saucez (Inria) for the helpful discussions.

Figure 1 :

 1 Figure1: Graph transformations. The original nodes are green. The added nodes are red/blue, added arcs are dashed. We have specified the new success probability functions for the simple case when p v (.) and r(.) are constant and respectively equal to p and r.

Proposition 4 .

 4 The function E [ψ(B)] is submodular.

v

  (u, S) p v (u, S ∪ C). We denote this new stochastic RR n°8423

1 Figure 2 :

 12 Figure 2: Performance of greedy, high-degree and random approach on the Twitter social graph for different values of retweet probability p. The reciprocation probability is considered to be r = 1.

Figure 3 :

 3 Figure 3: Extensions of the experiments by taking into account the probability that users will follow back (a), and by looking at the number of users who received the tweet instead of the number of users who retweeted it (b).

A set function f (.) is submodular if f (S ∪ {z})f (S) ≥ f (T ∪ {z}f (T ) whenever S ⊆ T and it is monotone if f (S ∪ {z}) ≥ f (S)for each S and z.RR n°8423

RR n°8423

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399