Cyrille Vézy

Gladys Massiera

Annie Viallat

flow of a giant vesicle membrane in an external shear flow

Adhesion induced non-planar and asynchronous flow of a giant vesicle membrane in an external shear flow

Cyrille Vézy, Gladys Massiera, Annie Viallat

Introduction

Situations, where soft deformable objects with a fluid interface like drops, vesicles and cells are subjected to hydrodynamics flows at low Reynolds numbers, are involved in an increasing number of engineering and biophysical processes including microfluidics and emulsion processing 1 , biomechanics 2 and blood circulation 3,4 . Numerous studies have brought insights into the specificity of the motions of this class of particles under simple Poiseuille or shear flows. In particular, it is well known that under simple shear flow, the fluidity of the particle interface allows surface flows, which are at the origin of a typical motion called tanktreading. This regime of motion, observed under suitable conditions of viscosity, aspect ratio of the particle and shear rate [5][6][7] , is characterized by a stationary shape of the particle, a steady finite inclination angle with respect to the flow direction and the rotation of the surface layer or of the membrane of the particle about its centre of mass.

The surface flow of the incompressible membrane of tanktreading red blood cells has long been observed from the position of small latex beads stuck onto the rotating membrane 4 . Similarly, the motion of lipid vesicle membranes has been reported for tanktreading vesicles in shear flow 8,9 and for vesicles sliding along an inclined plane in a quiescent fluid 10 by tracking small lipid defects linked to the membrane. It was observed both for red blood cells biconcave disks and spherical or ellipsoidal vesicles that all elements of the membrane flow on closed surface streamlines, which describe quasi-planar orbits in the shear plane 4,10 . The surface flow of the red blood cell membrane, which is bound to a solid elastic cytoskeleton is synchronous in the sense that the cyclic motions along the streamlines have one common frequency, the tanktreading frequency 4 . It means that adjacent membrane elements remain adjacent after a full revolution along the streamlines. The revolution velocity on the streamlines of vesicle surfaces has not been experimentally explored in detail. A short report on a non spherical vesicle fixed by a thin lipid tube to the substrate suggests that the angular velocity along the surface streamlines of the viscous membrane, depends on the lateral streamline position with respect to the meridian orbit of the vesicle 11 .

55

The theoretical problem of the surface flow of a tanktreading fluid membrane with fixed area and bending rigidity in shear flow is complex. Using a simple surface velocity field and under the hypothesis of a synchronous motion along planar elliptical orbits, Keller and Skalak 12 60 analytically derived the equation of motion of a fluid ellipsoid and computed the tanktreading velocity. Secomb and Skalak 13 generated more realistic area-conserving velocity fields on the surface of ellipsoids. In this case, they showed that the motion along streamlines which presented a curvature towards each 65 end of the cell resulted in less dissipation than the motion with planar orbits. More recently, Kraus et al. 14 proposed a numerical approach to deal with an incompressible membrane with bending rigidity and an ellipsoidal shape of arbitrary aspect ratio. He showed that the streamlines lie in a plane 70 parallel to the shear plane and that when the vesicle shape departs markedly from the spherical shape the revolution velocity varies along the contour in a way that velocities are smaller towards the poles of the vesicle. Very recent theoretical works numerically dealt with the full problem of 75 motion of vesicles, including the effects of thermal fluctuations, but they did not focus on surface flows 15. Contrarily to the case of non-bounded shear flows, the surface flow of vesicles firmly adhered to a plane wall in a shear flow has not generated much experimental studies 9,16 , 80 although the question is of interest in terms of mobility and recruitment of cell membranar receptors towards the adhesive zone on the subtrate, which bear associated ligands 17 . Two theoretical works describe the motion of bound vesicles under flow 16 17 focusing their studies on the unbinding of non-85 specifically adhered vesicles, but do not describe the membrane flow. The main questions we want to address in this paper are: is the vesicle membrane able to flow in presence of attractive interaction with the substrate, either induced by the binding of specific membranar linkers or by a

| [journal], [year], [vol], 00-00

This journal is © The Royal Society of Chemistry [year] non specific adhesive field? What are the characteristics of surface streamlines and associated velocity field? How do these features vary with the vesicle size and the contact area?

The paper is organized as follows. After the description of materials and methods, we present the observation of vesicles shape and surface flows under shear flow. We characterize the streamlines on the vesicle surface as a function of the relative size of the contact zone with the substrate. Then, we determine the variation of the angular velocity along a streamline with its position on the surface. We finally shortly 100 discuss the obtained results.

Experimental Substrates

Two types of substrate are prepared in order to induce either non specific adhesion (charged coverslips covered by poly-L-105 lysin) or specific adhesion (coverslips covered by histidine ligands). All products were purchased from Sigma except the Histidine peptide (KGGSGGSYGGSGGSHHHH-HH) obtained from Covalab (Villeurbanne, France). Adhesion is induced by chelation between two histidin groups and a Nickel ion. The stability constant [START_REF] Dawson | Data for Biochemical Research[END_REF] of the complex C*, K=[C*]/[Ni][Hist] 2 , is equal to 10 15.9 .

Prior to any chemical treatment, glass coverslips are cleaned by immersion in a 14.5M NaOH solution for 5 minutes and rinsed extensively with pure water. Polylysin 115 coverslips are obtained by incubation in a polylysin solution (10 -3 % v/w) for 30 min, followed by rinsing with ultrapure water. The histidine functionalization is obtained according to the following process: a glutaraldehyde peptide is first bound to the silane activated glass surface by reaction between an 120 aldehyde bond on the peptide and an amine bond on the silane. The histidine peptide is then bound to the glutaraldehyde peptide via its terminal amine function. The 6histidine peptide was chosen since it maximizes the probability of chelation of a Ni on a vesicle [START_REF] Conti | [END_REF] . Technically, the 125 glass slides receive sequentially the following treatments at room temperature: incubation in a silane solution (1% v/v 3aminopropyl-tri-ethoxysilane and 5 mM acetic acid in water) for 20 minutes under gentle mixing, rinsing with pure water, curing for 15 min at 100 °C, incubation in a glutaraldehyde solution (10 % w/w) for 90 min under gentle mixing. Coverslips are then incubated for 2 hours at 37°C in a solution of histidine peptide (1.2 mg/ml) diluted in a carbonate/bicarbonate buffer (0.2 M, pH=8). After rinsing with a PBS-Triton solution (1 %), coverslips are incubated for temperature for 1 hour without shaking, to reinforce the bond between the glutaraldehyde and the peptide (reduction of the the imine group of the glutaraldehyde / peptide bond into an amine group). Coverslips can then be stored up to 8 days at 4°C in a sodium azide PBS buffer (0.1 % NaN 3 v/v).

Vesicles

The lipids, 1,2-dioleoyl-sn-glycero-3-phosphocholine (DOPC) and 1,2 -Dioleoyl -sn -Glycero -3 -{[N (5 -Amino -1 -Carboxypentyl)iminodi Acetic Acid] Succinyl} (Nickel Salt) (DOGS-NTA-Ni) are purchased as a powder from Avanti 150 Polar Lipids, and diluted at 2mg/ml in a chloroform/methanol solution (9:1). Giant unilamellar lipid vesicles were prepared either from pure DOPC or from a 95:5 mixture of DOPC and DOGS-NTA-Ni, using the standard electroformation method 20 . Sucrose solutions (50 mM and 200 mM) are used as 155 the internal fluid. Vesicles are then diluted in a solution of glucose with the same osmolarity as the internal solution of sucrose and is prepared in a HEPES buffer (10 mM, pH 8).

Microscopy

'Side view' observation was obtained by orienting a phase 160 contrast inverted microscope (Leica DM IRB, Wetzlar, Germany) horizontally and by working at low-angle incidence. The observation plane is then parallel to gravitational force and to the shear plane 8 . It provides welldefined side-view images of both vesicles and their reflections 165 on the substrate. Most observations were performed with a phase contrast 20X objective (long working distance). Pictures were captured with a CCD (Cohu) and a dvcam video-recorder (Sony, DSR-25).

Reflection interference contrast microscopy (RICM) was 170 used to determine the contact area of the adhered vesicle with the substrate 21 . This microinterferometric technique generates an intensity pattern by interference of two reflected rays: the incident light reflected both from the glass-buffer interface and from the buffer-vesicle interface. Strongly bound parts of 175 the membrane appear as dark regions on the characteristic RICM patterns. Both standard "bottom view" observation and RICM observation were performed using a phase contrast inverted microscope (Olympus, IX71) equiped with an antiflex objective (Plan Neofluar, x63 /1.25 Oil, Zeiss). Epi-180 illumination through the objective was rendered monochromatic by passing light from a 100-W Hg vapor lamp (Olympus) through an interference filter (Ifg 546.1 nm).

Flow

For side view observation, the flow chamber was a 185 parallelepiped-plate chamber (spectrophotometric circulation chamber from Hellma (Müllheim), height = 1 mm, width = 10 mm, length = 45 mm) with four optical faces. At one end, a rectangular opening give us the possibility to introduce a coverslip. The laminar shear rate (from 1 to 12 s -1 ) was 190 applied with 20 mL syringe mounted on a syringe pump. Shear rate calibration was performed by measuring the translational speed of polystyrene beads (2 µm of diameter) versus their distance from the substrate. For bottom view experiments, the chamber was a plexiglas block bearing a 195 cavity of 15.9 x 0.99 x 0.9 mm 3 surrounded by a toric gasket. Histidine or polylysin coverslips are maintained against the gasket with a screwed steel plate.

Protocol of measurement 200

Measurements were performed at a distance from the substrate less than 50 μm, so that the shear rate can be taken as constant and equal to the wall shear rate. All vesicles studied were at a minimal distance of 1 mm from the nearest optical face of the chamber, so that velocity field and wall shear rate values were 205 not disturbed by the presence of the side walls. Vesicles are slowly injected in the chamber and allowed to settle. One well contrasted axisymmetric vesicle is chosen at rest. A flow is then applied. The wall shear rate applied to the vesicle is then increased gradually from 1.3 s -1 to 11 s -1 , by increasing step 210 by step the flow rate in the chamber.

Image analysis

For side view image analysis, we developed an IDL (RSI) code to determine the vesicle contour. Both the vesicle and its reflection are fit by a sphere, and their intersection determine 215 the adhesion parameter (contact length = L). The membrane defect position was either tracked using an IDL tracking code ‡, or manually selected on each image using imageJ software, depending on the contrast.

Results and Discussion

220

We first determine vesicle shapes. We then show the existence of surface flows in the part of the membrane which is not at the close vicinity of the substrate. We then determine the surface streamlines and the angular velocity on the streamlines.

225

All coordinates are indicated by using a Cartesian referential: x = flow direction; y= shear direction.

Determination of vesicle shapes

The projection of vesicles onto their meridian plane (z = 0) is directly observed from side-view microscopic imaging (Fig. 230 1). Shapes are stable in time and do not significantly change upon increasing the shear rate. They are well-described by truncated spheres, when the shear rate is less than 12 s -1 . It suggests that adhesion is strong, i.e., WA>>κ, with W the adhesion energy per unit area, A the area of the adhesion disk 235 and κ the bending rigidity of the membrane. The shapes are characterized by their radius R and the position of the substrate (y = y s ) relatively to the sphere centre, which is taken as the origin of the referential. One directly derives the diameter L of the contact zone in strong interaction with the 240 substrate as shown in Fig. 1b. The full vesicle shape is determined by considering that the vesicles are axisymmetric about the y-axis.

The projection of vesicles onto their equatorial plane (y= 0) is directly observed from regular "bottom view" phase 245 contrast observation in the horizontal plane and yields vesicle radii (Fig. 2a). Moreover, simultaneous RICM observations show a strong interaction of the vesicle with the substrate over a large homogeneous disk of diameter L (Fig. 2b). There is no interference fringes at the edge of the contact zone due to a 250 sharp slope of the membrane relative to the substrate. Observation in the horizontal (y=cst) plane does not allow the full determination of the vesicle shape, since the vesicle axis of symmetry is perpendicular to the plane of observation. Based on side-view observations, we assume that the shape of 255 these vesicles is also a truncated sphere. Geometrical characteristics of studied vesicles are reported in Table 1. The vesicles exhibit large contact area, L/2R values ranging from 0.46 to 1 (half-sphere). As all vesicles were suspended in a solution of same osmolarity as that of vesicle 260 inner solution, they were expected to be swollen and present a spherical shape. We therefore assume that upon adhering to the substrate the vesicles transiently opened several pores to release a part of the internal solution in order to relax the line tension on the membrane 22 . It should be emphasized that the 265 shape of these adhering vesicles, which consists of a circular disk like area on the substrate, a spherical cap on the opposite side, and a very small intermediate region of strong curvature along the contact line, reveals a large adhesion energy with the substrate 23 .

270

Surface flow observation

We followed the movement of small defects (small clumps of lipids) bound to the vesicle membrane (approximate size 1μm) under shear flow. We selected defects associated to the inner part of the membrane, which may theoretically circulate 275 on the inner side of the membrane even if its latter is at the immediate vicinity or in contact with the substrate.

The movement of these markers allows one to visualize the projection of surface motions. Sequences shown in Fig. 1 and Fig. 2 clearly demonstrate the existence of surface flows of 280 the membrane, as already reported in ref 9 and 16. The projection of the orbits described by the defects on the surface are determined by measuring their position as a function of time as shown in Fig. 1 and assumed to correspond to the surface streamlines on the membrane. It is worth emphasizing 285 that the Brownian motion of a defect is slow compared to the velocity at which it circulates on the membrane and does not perturb the determination of the surface streamlines. On a longer timescale, however, the defects slowly diffuse on the membrane surface and explore various surface streamlines.

290

The observation of the movement of a single defect therefore allows the determination of several orbits on a single vesicle.

The sequence in Fig. 2 shows that when the defect passes at the top of the vesicle membrane (x = 0), its orbit is quasicircular and lies in the plane (z = cst) parallel to the shear 295 plane. When it approaches the substrate, as detected by the change of focus of the defect, its trajectory departs from the plane and avoids the contact zone. This zone and the water molecules that can possibly lie between the vesicle and the substrate are therefore considered as being motionless.

300

Streamlines determination

The streamlines on each vesicle surface were obtained from the observation of a single defect. Its couple of coordinates (x, y) and (x, z) is directly measured from side view (projection on the plane z = 0) and regular bottom view (projection on the 305 plane y = 0) respectively. The third coordinate is calculated from the description of the vesicle as a truncated sphere of equation x 2 + y 2 + z 2 = R 2 and y > y s . The projections of streamlines are illustrated on three vesicles in three planes (x, z), (x, y) and (z, y) in Fig. 3. Data are either obtained from 310 direct observation or from determination of one coordinate via the sphere equation. The three vesicles exhibit various aspect ratios, characterized by L/2R. Typical streamlines are illustrated in Fig. 3. The first feature to notice is that the surface flow is divided into two symmetric quadrants observed on each side of the meridian plane z = 0. The defect that moved in the meridian zone had changed side during the observation time, as illustrated in Fig. 3c. The second feature is that two stagnation points are observed on each side of the vesicle. As the vesicles are not spherical, the axis z is not a symmetry axis so that the stagnation points are not located on this axis, contrarily to what was observed for spherical vesicles sliding along an inclined plane 10 . The position of the stagnation point lies on the median plane x = 0 and is located by the angle θ between the radius of the sphere passing by this point and the axis z (Fig. 3). The variation of the angle θ with the vesicle aspect ratio, characterized by the non-dimensional number L/2R, is reported in Fig. 4. The angle θ starts from 0 for spherical symmetrical vesicles and slowly increases with L/2R. The increase is much sharper when L/2R approaches 1 (half-sphere). We did not observe vesicles with a ratio L/2R greater than 1 (with a contact angle greater than 90°), which are likely very unstable due to the large bending energy of the membrane at the contact with the substrate. When the size of the contact zone increases, the orbits of the streamlines depart more and more from planar circular orbits since no flow is allowed in the contact zone. The streamlines have non trivial non planar shapes, which are difficult to characterize (Fig. 3).

Angular velocities

The period T of revolution of a defect on an orbit at the surface of a vesicle was experimentally determined by following the projection of marker trajectories over at least one full orbit. An example of the variation of the coordinates x and y of the marker versus time, as deduced from side view imaging of the vesicle, is represented in Fig. 5. These variations are well fitted by a sinusoidal function, suggesting the rotational velocity is constant and equal to the frequency of revolution, ω = 2π/T. Typical variation of ω on one given orbit as a function of the shear rate ú γ is illustrated in Fig. 6.

The membrane velocity show several remarkable features. First, the velocity ω varies linearly with the wall shear rate, as predicted for non adhered vesicles in non bounded shear flow 14 and observed on non adhered vesicles flowing close to a substrate 8,11 . Moreover, for a given shear rate, the values of ω increase upon decreasing the relative contact zone L/2R, i.

e. upon modifying the aspect ratio of the vesicle. Finally, the rotational velocity on a given streamline depends on its lateral position on the vesicle surface. In order to illustrate this phenomenon, we measured the rotational velocity on various streamlines located on a single vesicle.

The lateral position of a streamline is characterized in the median plane of the vesicle (x = 0) by the ratio s* = s/s 0 , of the curvilinear distance between the stagnation point and the streamline s to the curvilinear distance between the stagnation point and the vesicle top (x=0, y=R, z=0), s 0 , as shown in Fig. 3. Fig. 7 shows the variation of ω/ú γ with s* for vesicles observed either from side or bottom view. Velocities are larger towards the stagnation points (SP). This variation is the contrary to that predicted by Kraus et al 14 on vesicles flowing in a non-bounded shear flow, where ellipsoid vesicles display smaller angular velocity towards the SP. Our result is likely due to the fact that the contact zone is motionless. It induces that the angular velocities of the orbits at the proximity of the contact line be small in order to limit the viscous dissipation 375 in the membrane. The difference of angular velocity on the various streamlines reveals an effective strong shear in the membrane, since two adjacent lateral elements of the membrane do not remain adjacent after a full revolution. It is also note worthy that the ratio ω/ú γ is greater than 0.5 close to 380 the vesicle SP (also observed in Ref. 11) , this value being the angular velocity of a rigid fluid in a non-bounded shear flow.

We infer the two extreme values of the angular velocity, ω 0 at the vesicle top and ω θ on the SP, by fitting the variation of the angular velocity with an arbitrary linear 385 function, ω/ú γ = (ω 0 -ω θ )s * +ω θ , as displayed in Fig. 7.

The quantity ω 0 -ω θ vhthus represents the gradient of velocity upon curvilinear displacement along the vesicle membrane. These three parameters are plotted versus the aspect ratio, L/2R, in Fig. 8. It clearly appears that ω/ú γ is 390 mainly determined by the vesicle aspect ratio L/2R and is weakly sensitive to the vesicle radius in the studied range.

ω/ú γ is constant for L/2R≤ 0.8. For larger contact areas, the velocities sharply decrease and display a smaller difference between the top and the SP.

395

Discussion

We described the main features of surface flows of giant lipid vesicles adhering to a substrate. We revealed the existence of fast flows on the surface associated with closed non planar orbits around two stagnation points on each side of the 400 vesicle. We showed that flow is very unlikely to occur in the adhesion zone with the substrate, meaning that the lipids do not bind and unbind at the rotational frequency of the membrane. It should be underlined here that the nature of the contact and thus the dissipation might be different for each 405 kind of adhesion: specific or non-specific. While non-specific adhesion will create an homogeneous contact area where all lipids are subjected to the interaction field with the substrate, specific adhesion implies domains of tight adhesion formed by Ni-lipids and Histidin groups separated by non-adhesive of 410 weakly adhesive areas containing pure DOPC lipids. These DOPC lipids may, in principle, flow around the bound lipids, though such a flow has a high cost in terms of energy of viscous dissipation 24. The observation of local lipid flow requires more sophisticated instruments to be detected. The 415 adhesive zone rather acts as an obstacle to the membrane flow, which therefore induces a velocity gradient. The angular velocity on the orbits indeed increases when the orbits are closer to the SP, showing a strong shearing dissipation in the membrane. However, as far as we know, no theoretical nor 420 numerical description of the surface flows of the vesicle membrane is today available to describe the shape of the streamlines and the total viscous dissipation in the membrane. Similar questions have been addressed in the case of a drop adhered to a wall 24,25 must equal zero in the case of a lipid vesicle. In the case of a 430 cell, a solid cytoskeleton is bound to the membrane via transmembranar proteins. As the contact zone is fixed and the cytoskeleton is an elastic solid, the whole cytoskeleton is expected to remain fixed over the whole cell. Therefore, no fast flow of the cell membrane is expected. Indeed, side view 435 imaging reveal that small heterogeneities on CHO cells adhered to a glass substrate under shear flow are motionless [START_REF] Viallat | the Gordon Research Conference colloidal, macromolec and polyelect solutions[END_REF] . However, a small lipid flow may occur around the transmembranar proteins, associated with a strong viscous dissipation as observed, when a thread is pulled out from a 440 cell 27 . The decrease in ω / ú γ with the adhesion strength, characterised by the ratio L/2R, could have multiple origins including: i) the fact that the larger the adhesive zone, the more the membrane flow is hindered by this obstacle, ii) Deviation from the spherical shape has previously been shown 445 to decrease the ratio ω / ú γ as derived from theories describing the dynamics of a vesicle under shear flow [12][13][14] .

Conclusion

We used a simple experimental approach to describe the fast surface flows of a lipid membrane of an adhered giant vesicle, 450 which had not been studied yet. Our approach relied on the motion of markers, whose size is of the order of one micron.

It is worth underlining that molecular flow may also occur in the contact area which might allow the recruitment of surface receptors towards the membrane adhesion zone. Other 455 experimental tools, such as adapted fluorescence techniques (FRAP, FCS), could be of interest to give a further insight into the molecular flows on adhered cells and vesicles. Moreover, we hope that our work will generate numerical studies in order to better understand the dependence of the 460 streamline shapes and of the membrane viscous dissipation as a function of the radius and of the aspect ratio of the vesicles.

We acknowledge Pr. F. Bruckert for the design of the peptide and the help in the functionalization process, Dr. L.

Fig. 2 :

 2 Fig.2 : (a) : Bottom view of Ves5, subjected to a linear shear flow. The dotted line represents the projection of the marker trajectory. (b) : RICM view of ves5 (the scale is different from (a), (c)-(h)). The adhesive zone corresponds to the large homogenous dark disc. (c), (d) and (h): the marker (black dot) avoids the contact zone when approaching the substrate. From (e) to (g) the marker circulates at the vesicle top (the focus varies).

Fig. 1

 1 Fig.1 (a) : Side view of a vesicle (Ves4) and its reflection on the substrate subjected to a linear shear flow along the x direction. (b) : L is the length of the contact zone. R is the vesicle radius. From (b) to (f): we infer the surface flow from the motion of a lipid defect (clear dot), we used as a marker.

Fig. 3

 3 Fig.3 Marker trajectories and streamlines reconstruction for three vesicles. Projection in the plane (x,y) of marker trajectories observed from side view imaging and reconstruction of the corresponding streamlines in (z,y) and (x,z) planes : (a) : Ves1; (b) : Ves3. Projection in the plane (x,z) of marker trajectories observed from bottom view imaging and reconstruction of the corresponding streamlines in (z,y) and (x,y) planes : (c) : Ves5. The grey disc in the (x,z) view represents the contact zone.

Fig. 4

 4 Fig.4 Variation of θ (defined in Fig.3) as a function of the aspect ratio L/2R. The dashed line is a guideline for eyes..

Fig. 5

 5 Fig.5 Typical time evolution of the coordinates x (black circles) and y (open squares) of a marker on Ves3 as deduced from side view imaging. The lines are guidelines for eyes.

Fig. 6

 6 Fig.6 Linear variation of the angular velocity ω of a circulating marker as a function of the shear rate γ & observed on fixed orbits: • : Ves1; ■ : Ves2; ▲ : Ves3; ▼ : Ves4; O : Ves5; □ : Ves6 and ∆ : Ves7. Dashed lines are linear fit.

Fig. 7 Fig. 8

 78 Fig.7 Variation of the reduced angular velocity γ ω & / of a circulating marker as a function of the dimensionless curvilinear distance s* = s/s 0 . • : Ves1; ■ : Ves2; ▲ : Ves3; ▼ : Ves4; O : Ves5; □ : Ves6 and ∆ : Ves7. γ & is varied in the range 1.13 -11 s -1

  but streamlines are very different from 425 the ones we observed since recirculation of surface molecules to the internal volume is authorized for drop, whereas lipid molecules can not enter into the inner vesicle volume, or in other terms, the surface divergence of the surface velocity

	This journal is © The Royal Society of Chemistry [year]	[journal], [year], [vol], 00-00 | 5

  Alon, D. A. Hammer and T. A. Springer, Nature, 1995, 374, 539;

		2 R. 475
	465	Limozin
		for RICM experiments, Pr. P. Bongrand for tracking
		numerical codes and Dr. M. Abkarian for discussions. Part of
		experiments were performed in Laboratoire de Spectrométrie
		Physique, UMR5588-University J. Fourier, Grenoble, France.
	470	Notes and references
		‡ http://www.physics.emory.edu/~weeks/idl/
		1 H. Stone, A. Stroock and A. Ajdari, Annu. Rev. Fluid Mech., 2004,
		36, 381

1 hour at 37°C in an ethanolamine solution (0.2 M at pH=10) in order to passivate the substrates and to prevent non specific adhesion. The coverslips are rinsed again using the PBS-Triton solution. Finally, the substrates are incubated in a sodium borohydre (NaBH 4 ) solution (3.5 mg/ml) at room

This journal is © The Royal Society of Chemistry [year][journal], [year], [vol], 00-00 | 3

This journal is © The Royal Society of Chemistry[year]


Yunbo Li

Chuanyou Li
email: cyli@seu.edu.cn

Anne-Cécile Orgerie
email: anne-cecile.orgerie@irisa.fr

Philippe Raipin Parvédy
email: philippe.raipin@orange.com

WSGP: A Window-based Streaming Graph Partitioning Approach

Graph partitioning, a preliminary step of distributed graph processing, has been attracting increasing attention in the last decade. A high quality graph partitioning algorithm should facilitate graph processing by minimizing the communication overhead and maintaining the load balancing among distributed computing units. Offline partitioning algorithms usually require the knowledge of a complete graph,and therefore, are not adaptive to handle massive graph-structured data. On the contrary, streaming partitioning algorithms take edges or vertices as a stream and make partitioning decisions on the fly. However, the streaming manner faces dilemmas from time to time because of a lack of knowledge. Furthermore, an unmindful partitioning decision in such a dilemma could significantly decrease the partition quality. In this paper, we propose a novel window-based streaming graph partitioning algorithm (WSGP). WSGP leverages a greedy-based heuristic to perform edge partitioning. When facing a decision dilemma, WSGP utilizes a size-bounded window to buffer the edges. When the window is fully filled, an edge is poped and assigned to a partition. The assignment is decided by knowledge obtained from both the edges already settled and the ones still cached in the buffer window. Our experiments take into account various real-world benchmark graphs. The experimental results demonstrate that WSGP consistently has a smaller replication factor than the state-of-the-art algorithms by up to 23%, at a limited cost in terms of memory and comprehensive running time.

I. INTRODUCTION

Many complex systems such as social networks, road networks, or molecular networks, ranging from computer science to biology, can be naturally represented by graphs. Analyzing graph-structured data brings opportunities to explore underlying rich and complex relationships. This has been widely applied in recommendation, link prediction, and subgraph matching for instance. However, with the rapid growth of graph-structured data, it is no more adaptive to perform graph processing in a single computing unit. As an example, the graph from the online social network Orkut (used later in this work) comprises more than 3,000,000 vertices and more than 117,000,000 edges [START_REF] Yang | Defining and Evaluating Network Communities Based on Ground-Truth[END_REF].

Processing graphs over distributed systems has attracted significant interests in the last decade, from both the research and industry communities. In particular, distributed graph processing systems, such as Pregel [START_REF] Malewicz | Pregel: a system for large-scale graph processing[END_REF], GraphLab [START_REF] Low | Graphlab: A new framework for parallel machine learning[END_REF], Powergraph [START_REF] Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF] and GraphX [START_REF] Gonzalez | Graphx: Graph processing in a distributed dataflow framework[END_REF], have been proposed and succeeded to process billion-scale graphs. To perform distributed graph processing, it is required to partition the graph first. Edge partitioning currently constitutes the favored approach for very large graphs in order to balance the load among distributed computing units.

In this paper, we study the edge partitioning (vertex cut) problem, where each edge is assigned to a single partition, such that the graph is divided along vertices. Usually, vertex cut is modeled through vertex replication. For example, if two edges share a common vertex but are assigned to two different partitions, then the common vertex has two replicas, one on each partition. Such replication inevitably causes synchronization or communication overhead for distributed graph processing. Hence, a high quality edge partitioning approach should minimize the number of produced replicas. On the other hand, fair load distribution is highly desirable in distributed systems. Therefore, edge partitioning should also maintain load balancing by assigning edges evenly over partitions.

To perform edge partitioning, there are two basic approaches: offline partitioning and streaming partitioning. Offline partitioning relies on loading the complete graph into memory. This way allows for designing high quality partitioning heuristics, but is lacking of availability to process large-scale graphs. On the opposite side, streaming partitioning follows the online setting. Edges arrive as a stream and the partitioner assigns edges to partitions on the fly. Compared with offline partitioning, the streaming manner has a good scalability and a reasonable loss of partitioning quality.

In this paper, we systematically investigate the streaming edge partitioning problem, and propose a novel Windowbased Streaming Graph Partitioning approach (WSGP). WSGP inherits the framework of Oblivious [START_REF] Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF] and leverages new heuristic strategies. Once an edge arrives, Oblivious makes the assignment according to four rules. Yet, we notice that in Oblivious it is hard to make a good assignment for an edge whose pair vertices does not appear in the same partition. We consider such scenario as a dilemma, whose existence is due to the fact that the current partial knowledge is not sufficient. Aiming at such problem, our idea is to leverage a window to buffer this edge temporarily while continuing to assign the next incoming edges. The buffering operation does provide new opportunities to break through the dilemma, as it allows to collect more knowledge of the graph. As soon as the window is fully filled, we pop a buffered edge and carry out the assignment. If this edge is still in the same dilemma, our new strategy selects the partition which targets to benefit the assignment of more edges still buffered in the window, i.e., let more buffered edges not meet the dilemma again.

Our contributions are summarized as follows:

• We perform a comprehensive study on different streaming edge partitioning algorithms. We characterize the features and identify the key problems. • We propose WSGP a new window-based streaming partitioning approach. WSGP enables the partitioner to synthetically use knowledge obtained from both the edges already settled and still cached, and this approach succeeds in avoiding bad assignments. • We carry out the evaluation with different types of realworld graphs. The experimental results demonstrate that our new approach outperforms existing streaming edge partitioning algorithms in terms of the replication factor, at the cost of a acceptable processing time overhead and a limited additional memory consumption. The rest of this paper is organized as follows. Section II sketches out the related work. Section III introduces the notations and gives a formal problem definition. In Section IV, a new window-based streaming partition algorithm is proposed and analyzed. The experimental setup and results are discussed in Section V. Finally, Section VI concludes the paper.

II. RELATED WORK

Graph partitioning is a well-known fundamental problem in many parallel and distributed applications [START_REF] Malewicz | Pregel: a system for large-scale graph processing[END_REF], [START_REF] Hendrickson | Graph partitioning models for parallel computing[END_REF], [START_REF] Tsourakakis | Fennel: Streaming graph partitioning for massive scale graphs[END_REF]. There are two graph partitioning variants: edge partitioning (vertex cut) and vertex partitioning (edge cut). Edge partitioning results in partitions that are edge disjoint while vertex partitioning results in partitions that are vertex disjoint. Figure 1 depicts an example showing their differences. We can see that both partitioning variants bring in additional costs, e.g., in Figure 1(a) vertex v 2 is replicated and in Figure 1(b) two edges are cut. In another aspect, load balancing also affects the efficiency of downstream tasks execution due to Liebig's law, such that graph partitioning in a general not only targets to minimize the partitioning costs, but also to maintain load balancing. For optimizing both objectives, the two variants are known to be NP-hard problems [START_REF] Kim | Sbv-cut: Vertex-cut based graph partitioning using structural balance vertices[END_REF]- [START_REF] Andreev | Balanced graph partitioning[END_REF]. In the following, we first sketch typical vertex partitioning approaches and then introduce the latest development on edge partitioning.

A. Vertex Partitioning

Pregel [START_REF] Malewicz | Pregel: a system for large-scale graph processing[END_REF] and GraphLab [START_REF] Low | Graphlab: A new framework for parallel machine learning[END_REF] are two distributed graph processing systems that leverage a vertex-program which is executed on each vertex and can interact through sharedmemory or messages. Both Pregel and GraphLab depend on vertex partitioning to minimize communication costs and ensure load balancing. However, in the case of natural graphs (e.g., power-law graphs), Pregel and GraphLab are forced to resort to hash-based partitioning which can extremely decrease the system performance.

v3 v 2 v 1 v 4 v 5 v 3 v 2 v 1 v 4 v 5 v 4 v 5 v 1 v 2 v 3 v 2
LDG [START_REF] Stanton | Streaming balanced graph partitioning algorithms for random graphs[END_REF], [START_REF] Stanton | Streaming graph partitioning for large distributed graphs[END_REF] and Fennel [START_REF] Tsourakakis | Fennel: Streaming graph partitioning for massive scale graphs[END_REF] also follow the vertex partitioning paradigm but take a stream of vertices as input. LDG uses a greedy heuristic that tries to assign neighboring vertices to the same partition. Fennel leverages a heuristic which combines locality-centric measures with load balancing factors [START_REF] Stanton | Streaming graph partitioning for large distributed graphs[END_REF]. Both LDG and Fennel require the total number of vertices as an a priori. Hence, both of them could be considered as bounded streaming algorithms.

J.E. Gonzalez et al. [START_REF] Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF] argued that edge partitioning is more adaptive for partitioning natural graphs. They also pointed out that for a given edge-cut with g replicas, any vertex cut along the same partition boundary has strictly fewer than g mirrors. In recent years, more researches has focused on studying edge partitioning.

B. Edge Partitioning

C. Zhang et al. [START_REF] Zhang | Graph edge partitioning via neighborhood heuristic[END_REF] proposed NE an edge partitioning heuristic whose key idea is neighborhood expansion. NE selects edge gradually to fully fill each partition and this approach performs quite well. M. Hanai et al. [START_REF] Hanai | Distributed edge partitioning for trillionedge graphs[END_REF] proposed a follow-up study. They reformed NE to distribute its approach, this proposition can process trillion-edge graphs and achieves better performance in terms of running time. However, both of them depend on the knowledge of the complete graph.

Streaming based edge partitioning does not rely on knowing the complete graph. Z. Abbas et al. [START_REF] Abbas | Streaming graph partitioning: An experimental study[END_REF] did an experimental study of several typical streaming edge partitioning methods including Hash, Grid [START_REF] Jain | Graphbuilder: scalable graph etl framework[END_REF], PDS [START_REF] Jain | Graphbuilder: scalable graph etl framework[END_REF], DBH [START_REF] Xie | Distributed powerlaw graph computing: Theoretical and empirical analysis[END_REF], Oblivious [START_REF] Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF] and HDRF [START_REF] Petroni | Hdrf: Stream-based partitioning for power-law graphs[END_REF]. Hash is an intuitional method that decides the partition by simply computing a hash function. Hash is adept at maintaining load balancing but can lead to a large number of vertex replicas. Grid and PDS are also hash based methods. The difference is that they require additional constrains. For example, Grid needs all partition IDs arranged in a square matrix, while PDS involves Perfect Difference Sets which requires p 2 + p + 1 partitions (p being prime). Existing studies [START_REF] Abbas | Streaming graph partitioning: An experimental study[END_REF] showed that only relying on hash function is difficult to have a good partitioning result. DBH prioritizes cutting the vertices having highest degree and employs hash for partitioning. With its heuristic cutting high degree vertices, DBH outperforms pure hash based methods. Different from Hash, Grid, PDS and DBH, our new proposed WSGP does not depend on any hash function to assign the edges.

Oblivious [START_REF] Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF] and HDRF [START_REF] Petroni | Hdrf: Stream-based partitioning for power-law graphs[END_REF] are closer to our work. As a general approach, Oblivious uses greedy heuristic to make the current optimal assignment according to the known partial knowledge. When Oblivious meets a dilemma, it simply performs the assignment by only considering load balancing. Different from Oblivious, HDRF prefers to cut vertices with high degrees when meeting a dilemma. After deciding the cutting preference, HDRF makes the final assignment in order to maintain load balancing. Our WSGP also uses a greedy algorithm. Different from Oblivious and HDRF, WSGP leverages a bounded window to buffer the edge temporarily when facing an assignment dilemma. When processing a buffered edge, WSGP does the assignment aiming at producing less replicas for the successive assignments of edges still buffered in the window.

Our work is also related ADWISE [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF] as the common idea consists in involving a window to buffer edges. However, both ways of window utilization differ. ADWISE puts every edge into the window. Once the window is fully filled, a greedy strategy integrating a balancing factor, a degreeawareness factor and a clustering factor is performed to decide the assignment. According to our study, this strategy that buffer each vertex is not good for partitioning efficiency. Hence, in our approach, we consider to buffer only the edges facing a special dilemma. Meanwhile, for the way to use information collected by the window, we propose a new greedy strategy aiming at producing less replicas, which also differ from ADWISE strategy.

III. NOTATIONS AND PROBLEM FORMULATION

In this section, we first provide necessary notations and then formulate the streaming edge partitioning problem.

A. Notations

We consider G = (V, E) the undirected graph waiting to be processed, where V is a set of vertices and E is the set of edges. To facilitate our presentation, we usually use lowercase like u (or v, x, y, ...) to express a vertex and use e u,v to represent an edge connecting two vertices u and v. A partition of edges P = (P 1 , P 2 , ..., P k ) is defined as a family of pairwise disjoint edge sets, i.e., ∀i = j, P i ∩ P j = ∅ and

P 1 ∪ P 2 ∪ ... ∪ P k = E. Each partition P i (i = 1, ..., k) is a subset of edges denoted as P i = {e x,y |e x,y ∈ E ∧x, y ∈ V }.
Let A(u) be the set of partitions (A(u) ⊆ P ) where each vertex u ∈ V is replicated. The replication factor RF is defined to be the average number of replicas per vertex [START_REF] Florian | Balanced graph edge partition[END_REF]:

RF = 1 |V | u∈V |A(u)| (1)
A partitioning of edges P is σ balanced if:

max Pi∈P |P i | < σ |E| |P | , ( 2
)
where |E| is the total number of edges of G, |P | = k represents the total number of partitions, and σ ≥ 1 is the factor describing the maximum acceptable imbalance.

B. Problem Formulation

In streaming edge partitioning, a sequence of edges e u,v , e x,y , ... (that could be in any order) arrive in a streaming manner. An edge partitioning algorithm claimed to be streaming should not foreknow the sequence order and has to assign every edge to a given partition P i on the fly.

In this paper, we focus on a k-way σ balanced streaming edge partitioning problem which divides the edge set E into k disjoint parts and aims at minimizing the replication factor RF , meanwhile, maintaining the load of each partition σ balanced. The formulation is given in the following: minimize RF ;

(3)

s.t., max Pi∈P |P i | < σ |E| |P | (4)

IV. STREAMING EDGE PARTITIONING

A. Analysis

Our algorithm WSGP follows the framework of Oblivious [START_REF] Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF] which leverages a greedy approach to assign edges on the fly. Once an edge e (u,v) arrives, Oblivious decides the assignment for e (u,v) according to the following four cases:

1) Case 1:

If A(u) ∩ A(v) = ∅, e (u,v) is assigned to the minimum loaded partition in A(u) ∩ A(v). 2) Case 2: If A(u) = ∅ and A(v) = ∅, e (u,v) is placed to the minimum loaded partition in A(v). And vice versa, if A(u) = ∅ and A(v) = ∅, e (u,v) is placed to the minimum loaded partition in A(u). 3) Case 3: If A(u) = ∅ and A(v) = ∅, e (u,v) is placed to the minimum loaded partition in |P |. 4) Case 4: If A(u) = ∅, A(v) = ∅ and A(u) ∩ A(v) = ∅, e (u,v
) is assigned to the minimum loaded partition in A(u) ∪ A(v). Case 1 and Case 2 apply reasonable greedy strategies to selected the optimal partition according the current state. In case 3, both vertices u and v appear for the first time, i.e., there is no known information to assign e (u,v) towards RF minimization. Hence, the assignment can be done by only considering load balancing. In Case 4, both vertices u and v appeared before. However u and v do not have replicas in the same partition as A(u) ∩ A(v) = ∅. We consider Case 4 as an assignment dilemma, since no matter how to do the partition, the partitioner either increases u's replicas by one or increases v's replicas by one. In such a dilemma, Oblivious considers the minimum loaded partition, i.e., and totally ignores RF in this case. Different from Oblivious, to break the symmetry, HDRF [START_REF] Petroni | Hdrf: Stream-based partitioning for power-law graphs[END_REF] chooses to sacrifice the one with the larger degree.

Our idea is different from both of these approaches: we consider taking advantage of memory to cache edges like e (u,v) temporarily. When we try to assign e (u,v) for the second time, the situation is different because we can utilize information from both the already processed edges and the ones still cached to break the symmetry. According to this key idea, we propose a novel Window-based Streaming Graph Partitioning algorithm (WSGP).

B. Window-based Algorithm

WSGP leverages a window to cache those edges whose partitions are hard to be decided yet. In a nutshell, once a new edge e (u,v) arrives, there are four cases to deal with e (u,v) :

1) Case 1, Case 2, Case 3 inherits from Oblivious; 2) Case 4: If A(u) = ∅, A(v) = ∅ and A(u) ∩ A(v) = ∅,
call the method WEA(e (u,v) ) to tackle e (u,v) .

Before elaborating Window-based Edge Allocation (WEA), let us introduce the data structure for constructing the window w. Generally, w buffers each edge e (u,v) coming from Case 4. The cardinality |w| of w is defined as the number of edges it has buffered. For easily obtaining information from w, we also maintain a partial neighbor list for each vertex appearing in w. More precisely, if e (u,v) has been buffered in w, we then maintain two sets N (u) and N (v). Take N (u) as an example, it records u's neighbors that also appears in w. For example, in Figure 4, there is a window buffering of six edges. At a given time depicted on 1: Input u, v; 2: for each P i ∈ A(u) do 3:

rank(P i ) = x∈N (v) g(x, P i ); 4: end for 5: m 1 ← max rank(P i ), where P i ∈ A(u); 6:

S 1 ← {P i |P i ∈ A(u) ∧ rank(P i ) = m 1 }; 7: for each P i ∈ A(v) do 8:
rank(P i ) = x∈N (u) g(x, P i ); 9: end for 10: m 2 ← max rank(P i ), where

P i ∈ A(v); 11: S 2 ← {P i |P i ∈ A(v) ∧ rank(P i ) = m 2 };
12: S ← S 1 ∪ S 2 ; 13: id ← arg max{rank(P i ) + P bal (P i )}, where P i ∈ S; 14: return id; The pseudo code of WEA is provided in Figure 2. WEA takes an edge e (x,y) as its input (line 1). If w still has an empty space to accommodate one more edge, WEA buffers e (x,y) in w (line 13) and updates N (x) and N (y) (lines 14-15) immediately. Otherwise, WEA pops out an edge e (u,v) (line 3) to compute its partition (lines 4-11) and then buffers e (x,y) . For the popped edge e (u,v) , WEA first tests whether Case 1 is satisfied (line 4). If so, e (u,v) is assigned to the minimum loaded partition in A(u) ∩ A(v) (line 5). Note that when e (u,v) arrives in the system, Case 4 is satisfied, such that e (u,v) is buffered in w. The buffering of e (u,v) actually changes the order of edge assignments, such that when e (u,v) is popped, we can have Case 1 that is satisfied. If the test in line 4 is not passed, the method score is called to return the partition for e (u,v) (line 7). Once the assignment is decided, e (u,v) is settled (line 9) and then the dual sets N (u), N (v) are updated (lines 10-11).

The pseudo code of the method score is provided in Figure 3. score takes the pair vertices of e (u,v) as the inputs (line 1). As now A(u) and A(v) have no intersection, we shall choose the best partition from A(u) ∪ A(v) to be the target partition. Hence, we scan each partition in A(u)∪A(v) to get their ranks (lines 2-4, 7-9). We pick a partition P i from A(u) as an example. P i 's rank is counted by the number of vertices that appear both in P i and N (v), which could be formulated by g(x, P i ) as follows:

g(x, P i ) = 1, if P i ∈ A(x); 0, otherwise.
Note that such a heuristic aims at getting benefits from using the window scheme: once e (u,v) 's partition is decided, it should facilitate as much as possible edges also buffered in the window to get their partitions, since they are not in a dilemma situation anymore.

m 1 records the highest rank of partitions from A(u) (line 5). Then all the partitions from A(u) ranked by m 1 are logged in to an auxiliary set S 1 (line 6). Lines 7-11 perform a similar ranking process for partitions from A(v). For all partitions selected (logged in S, line 12), we then combine them with the balance factor P bal to make the final decision (line 13). The id of the target partition is returned (line 14).

P bal (P i ) = λ × max Pj ∈P |P j | -|P i | max Pj ∈P |P j | -min Pj ∈P |P j | + (5)
The above equation ( 5) calculates P bal (P i ), where is a constant used to avoid the denominator equals to 0 and λ is used to define the importance of load balancing. Figure 4 depicts an example showing the process after an edge e (u,v) is popped. In this example, w contains six edges, from which we can get N (u) = {v, x, y} and N (v) = {u, z}. Right now A(v) = {P 1 , P 3 } and A(u) = {P 2 , P 4 }, such that e (u,v) will be located on one of the four partitions. In Figure 4, we use a dash line to express e (u,v) 's four possible assignments. Considering that e (u,v) is assigned to P 1 . We can see that one vertex x appears in both N (v) and P 1 . According to our strategy, rank(P 1 ) = 1. Analogously, we can get that rank(P 2 ) = 0, rank(P 3 ) = 2 and rank(P 4 ) = 1. Therefore, in line 12, S = {P 2 , P 3 , P 4 } is obtained in this case. If the balance factor P bal does not play a major role, then id = 3 is obtained in line 13.

Note that if there are no more edges arriving, WSGP successively pops edge from w and then carries out the assignment by directly executing lines 4-12 in Figure2.

C. The costs of WSGP

We analyze the time complexity of WSGP through a comparison with Oblivious, i.e., focusing on the extra overhead for settling each edge. Oblivious is a one-pass streaming algorithm guaranteeing that each edge is processed only once. WSGP could be seen as a two-pass streaming algorithm as each buffered edge needs to be processed again. Hence, the extra overhead of WSGP comes from the operations after an edge is popped. Let us take edge e (u,v) as an example. After e (u,v) is popped, the major time consumption arises from computing rank for each candidate partition (lines 2-3, 7-9, Figure 3

V. EVALUATION

This section presents the experimental results for WSGP approach compared with other streaming edge partitioning (SEP) algorithms. The evaluation was performed on different degree distribution graphs.

A. Datasets

Many graph datasets are used in previous work [START_REF] Zhang | Graph edge partitioning via neighborhood heuristic[END_REF], [START_REF] Abbas | Streaming graph partitioning: An experimental study[END_REF], [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF], [START_REF] Petroni | Hdrf: Stream-based partitioning for power-law graphs[END_REF]. In order to build a fair and comparable result, we selected the four most common real-world graphs that capture different characteristics for degree distribution. We also used two additional graphs in order to compare with the results extracted from other articles. Table. I shows the statistics of the 4 datasets.

Table I: Statistics for real-world datasets

Dataset

|V | |E| dblp [START_REF] Yang | Defining and Evaluating Network Communities Based on Ground-Truth[END_REF] 317,080 1,049,866 web-google [START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF] 875,713 4,322,051 com-liveJournal [START_REF] Pacaci | Experimental analysis of streaming algorithms for graph partitioning[END_REF] 3,997,962 34,681,189 com-orkut [START_REF] Yang | Defining and Evaluating Network Communities Based on Ground-Truth[END_REF] 3,072,441 117,185,083

Figure 5 provides the degree of vertices, the number of vertices with the same degree, the percentage of each degree and a regression line of degree distribution. We observed that DBLP and WEB-GOOGLE datasets have many low degree vertices. Compared with DBLP and WEB-GOOGLE, COM-LIVEJOURNAL and COM-ORKUT have less low degree vertices and follow a heavy-tailed distribution.

B. Partition tool and Environment setup

In order to study the performance of the state-of-theart SEP algorithms and compare them to our approach, we build a low cost window streaming partitioner WStool based on the approach provided in [START_REF] Petroni | Hdrf: Stream-based partitioning for power-law graphs[END_REF]. The motivation of developing such a stand-alone partition tool is to run the SEP algorithms in an isolate environment with efficient implementation, not only avoiding any extra overhead of resource management and scheduling from the downstream graph computing systems [START_REF] Malewicz | Pregel: a system for large-scale graph processing[END_REF], [START_REF] Gonzalez | Graphx: Graph processing in a distributed dataflow framework[END_REF], [START_REF] Pacaci | Experimental analysis of streaming algorithms for graph partitioning[END_REF], but also minimizing the running time. There are three major differences compared with the HDRF partitioner VGP [START_REF] Petroni | Hdrf: Stream-based partitioning for power-law graphs[END_REF]. Firstly, VGP needs to load the full graph into memory such that it is not suitable to process the large-scale graphs. Table II shows the preprocessing time of VGP. Our implementation WStool loads and processes each edge on the fly. Hence, compared with VGP, WStool removes the preprocessing time and reduces memory footprint. Secondly, we implemented a more efficient datastructure (e.g. bitset) to store the information of replicas that allows to further reduce memory footprint and speedup the calculation. Lastly, we also eliminated the lock mechanism which is used for parallel processing. In this paper, all experiments used one thread.

The number of partitions is set to 30 except the experiments dedicated to varying this parameter. Figure 6 As expected, WStool processes much faster than VGP. In this paper, all experiments are deployed on a single server with the following specifications: 2 × Intel(R) Xeon(R) CPU @ 3.2GHz, 96GB of RAM, Ubuntu 18.04. WStool is implemented with Java 1.8.

C. Metrics

We used two metrics to measure the quality of graph partitioning algorithms: Replication Factor (RF ) and Load Balancing Index (LBI).

Replication Factor: this metric is defined in Equation 1 (in Section III.A). RF describes the average number of replicas per vertex. RF corresponds to the communication overhead for synchronization in graph computing phase. Generally, graph computing phase is composed of multiple iterations. Each vertex exchanges information by message passing or memory sharing in each iteration [START_REF] Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF]). So the higher the RF is, the more messages arise over the network, which slows down the whole computing phase.

Load Balancing Index: this metric is defined as follows:

LBI = max |P i | |E| |P | (6)
A partition can be seen as an isolate computing node in computing phase. A node hosts a portion of edges received from the partitioning procedure. The node having the largest number of edges decides the max processing time.

D. Input Order

The streaming partitioning algorithms have a common feature that their performance is particularly sensitive to the input edge order, such that it is difficult to propose an "onefit-for-all" streaming partitioning algorithm. For example, if the input edges arrive according to a BFS (Breadth First Search) or a DFS (Depth First Search) order, the greedybased algorithms that prefer to assign successive edges into a single partition, can provide a bad RF . Enlarging the balance factor [START_REF] Petroni | Hdrf: Stream-based partitioning for power-law graphs[END_REF] is a possible way to break the tie. However, we believe that for a particular order of edges, the best choice is to design a particular partitioning method. To avoid the ordering problem discussed above, we shuffled each dataset randomly before running the experiments. Moreover, we tested several random orders and the results show little difference.

E. Window size

In this section, we evaluate the proposed WSGP algorithm with different window sizes and compare its performance with other SEP algorithms on real-world graphs.

Replication factor: Figure 7 shows the replication factor of Oblivious, HDRF and WSGP algorithms in different window size settings (the x-axis is the percentage of the buffered edges). Oblivious and HDRF have different partitioning qualities in the four datasets. In general, HDRF outperforms 0.02 0.04 0.06 0.08 0.10 0.12 0.14 0.16 window size As for WSGP, when the window size approaches to 0, WSGP shows a similar behavior to Oblivious. By increasing the window size, WSGP is able to get more information that helps to make good partitioning decisions. In general, the larger the window size is, the better performance WSGP achieves. Note that, the slope of the replication factor curve is slowly decreasing. In our experiments, when the window size is around in average 25%|E|, the slope of the replication factor curve approaches to 0.

Load balancing index: Table III reports the results of load balancing index. All algorithms yield a good load balancing result. For our algorithm WSGP, the load balancing index increases slightly when the window size grows. In Table III, we gives the result of WSGP by setting |w| = 15%|E|. In [START_REF] Petroni | Hdrf: Stream-based partitioning for power-law graphs[END_REF], the authors concluded that the value of parameter λ(Equation 5) affects the load balancing result. Note that λ → ∞, the P bal (P i ) in Equation 5actually dominates the score( 3 line 13), our algorithm becomes meaningless. According to our study, we assign λ = 1.1.

≤ 1‰ ≤ 1‰ ≤ 1‰ ≤ 1‰ HDRF ≤ 1‰ ≤ 1‰ ≤ 1‰ ≤ 1‰ WSGP ≤ 1‰ ≤ 1‰ ≤ 1‰ ≤ 8‰
Partitioning time: Figure 8 shows the average throughput (edges/millisecond) for all algorithms (the x-axis is the percentage of the buffered edges). We can see that as the window size increases, the throughput of WSGP slowly drops due to more computation needed. Oblivious and HDRF do not impact by window size and have a better throughput than WSGP. We consider this as a reasonable tradeoff between throughput and RF . Many previous work [START_REF] Zhang | Graph edge partitioning via neighborhood heuristic[END_REF], [START_REF] Abbas | Streaming graph partitioning: An experimental study[END_REF], [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF], [START_REF] Petroni | Hdrf: Stream-based partitioning for power-law graphs[END_REF] demonstrated that the communication overhead in the graph computation phase is strongly affected by the replication factor achieved: even RF is increased by a little, the computing time, due to thousands of graph computing iterations, increases a lot. In particular, reducing communication cost is rather important in geo-graphically processing.

Therefore, we believe that in the graph partitioning stage it is worth to have a one time cost to minimize RF : the extra overhead of WSGP can be well compensated in the following graph computing phase.

F. The number of partitions

In this section, we evaluated the performance of increasing the number of partitions on a wide range from 2 to 64. The window size |w| is fix to 3%|E|.

Replication factor: Figure 9 shows the results in different number of partitions. The replication factor of all algorithms show a slowly increasing trend when increasing the number of partitions. WSGP outperforms all the comparison algorithms. Since WSGP leverages a bounded window to collect more information from the incoming edges, it greedily maximizes the potential data locality. In particular, increasing the number of partitions, it provides more opportunities for WSGP to buffer edges in the window. As shown in Figure 9, the gap between WSGP and oblivious/hdrf are getting larger when the partition number increases.

Furthermore, we show another example that how the parameter λ affects RF . We added TWITTER a larger social graph. Figure 10 shows the results of RF for all algorithms. With increasing the value of λ, the value of RF of Oblivious increases significantly, the RF of HDRF and WSGP stay invariant. We also extends the test to other graphs. The results consistently report that WSGP is less sensitive to parameter λ.

Load balancing index: All algorithms yield almost perfectly balanced partitions(LBI ≤ 1‰).

Partitioning time: Figure 11 shows the average throughput (edges/millisecond). All algorithms slow down as the number of partitions increases. Oblivious and HDRF have better performance than WSGP as they perform less computation.

G. ADWISE

In this section, we compare with another window-based streaming graph partitioning ADWISE [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF], WSGP is sometime better in RF but with much less resources. We used the same datasets BRAIN [START_REF] Rossi | The network data repository with interactive graph analytics and visualization[END_REF] and COM-ORKUT from article [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF] as the input stream for fair comparison. The BRAIN dataset Our experiments follow the configuration provided in [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF] such that the number of partitions |P | = 32 and λ = 1.1.

Since [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF] did not mention the window size, we tested RF under different throughput values. We then picked out the results which are the closest to the one provided in [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF]. Figure 12 shows the results with respect to RF of WSGP and ADWISE. The results of ADWISE are plotted according to [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF] (from Figures 7 and8 in Section IV in [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF]).

Replication factor: WSGP is worse than ADWISE on BRAIN and outperforms ADWISE on COM-ORKUT graph.

Load balancing index: Although there is no exact LBI in [START_REF] Mayer | ADWISE: Adaptive Window-Based Streaming Edge Partitioning for High-Speed Graph Processing[END_REF] for each dataset, the authors indicated LBI ≤ 5%. WSGP provides well balanced partitions where LBI ≤ 1%.

Partitioning time: ADWISE spent 281s on BRAIN and 329s on COM-ORKUT. WSGP required 306s on BRAIN and 349s on COM-ORKUT. Yet, it should be highlighted that the results of ADWISE employ 8 nodes with 8 Intel(R) Xeon(R) CPU cores (3.0GHz, 6144 KB cache) and 32GB RAM per node, while WSGP algorithm is processed by a single core on a single node with only 8.4G memory consumption (see Section V-B). Thanks to adopt the efficient implementation WStool and lower complexity of WSGP, the computation overhead and memory consumption of WSGP is much lower than ADWISE with a similar running time, which implies WSGP is more adaptive to process large-scale graphs with much less resources. Moreover, by increasing the window size, WSGP can further reduce the RF to 3.88 on BRAIN with an acceptable time cost (408s).

H. Summary of results

We summarize the results of our WSGP algorithm for the studied aspects. Using WSGP effectively reduces the number of replicas. By varying the size of windows and the number of partitions, WSGP consistently gives a good load balancing for all graph datasets. The above results rely on a reasonable window size with an acceptable time cost.

VI. CONCLUSION AND FUTURE WORK

Distributed graph partitioning for very large-size graphs targets both load balancing among computing units and runtime minimization. Replicating the high-degree vertices is a good heuristic and existing work has shown that it is useful for graph partitioning problem. In this paper, we demonstrated that there is an alternative way to achieve the same goal. With the low cost partitioner Wstool, the proposed WSGP algorithm leveraged a size-bounded window to optimize the decision for edge assignment efficiently. Our experimental results show that WSGP consistently achieves a smaller replication factor than the state-of-the-art algorithms (up to 23%), with a limited impact on memory utilization and runtime. We consider implementing a parallel version of our algorithm and integrating it to a distributed graph computing system as our future work.

Figure 1 :

 1 Figure 1: Edge Partitioning vs. Vertex Partitioning

Figure 2 :

 2 Figure 2: Window-based Edge Allocation (WEA)

Figure 3 :

 3 Figure 3: The pseudo code of method score

Figure 4 :

 4 Figure 4: An Example of WEA

  ), which could be modeled by |A(u)||N (v)| + |A(v)||N (u)|. Therefore, the extra overhead for settling each edge is upper-bounded by O(|w||P |), as |A(u)| ≤ |P |, |A(v)| ≤ |P |, |N (v)| |w| and |N (u)| |w|.

Figure 5 :

 5 Figure 5: Characteristics for real-world datasets

  plots the running time (without preprocessing time) of WStool and VGP partitioner for a variety of real-world datasets.

Figure 6 :

 6 Figure 6: Graph partitioning time of VGP and WStool

Figure 7 :

 7 Figure 7: Replication factor in different windows sizes

Figure 9 :Figure 10 :

 910 Figure 9: Replication Factor in different number of partitions

Figure 11 :Figure 12 :

 1112 Figure 11: Throughput in different number of partitions

Table II :

 II Preprocessing time of VGP (seconds)

	dblp	web-Google	com-LiveJournal	com-Orkut
	1	7	81	327

Table III :

 III Load balancing index

	dblp	web-google	com-livejournal	com-orkut
	Oblivious

ACKNOWLEDGMENTS

This work is supported by the National Natural Science Foundation of China under Grant 61902063, and by the Provincial Natural Science Foundation of Jiangsu, China under Grant BK20190342. This work is also supported by China Postdoctoral Science Foundation under Grant 2020M671669. Early experiments that help us to understand partitioning problem were partially carried out using the Grid'5000 testbed (supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations, see https://www.grid5000.fr).