Costanza Conti
email: costanza.conti@unifi.it

Jean-Louis Merrien
email: jmerrien@insa-rennes.fr

Lucia Romani
email: lucia.romani@unimib.it

Dual Hermite Subdivision Schemes of de Rham-type

Keywords: Vector subdivision, Inherently stationary Hermite subdivision, de Rham strategy, Dual parametrization, Convergence and smoothness analysis

Introduction

Vector subdivision schemes are iterative algorithms that, starting from an initial set of vector data f 0 := {f 0 (α), α ∈ Z} ∈ ℓ d+1 (Z), allow to generate denser and denser sets of vector data {f n+1 , n ≥ 0} through the repeated application of subdivision operators {S An , n ≥ 0}. The level-n subdivision operator S An which maps the sequence of vectors f n := {f n (α), α ∈ Z} ∈ ℓ d+1 (Z) into the denser sequence of vectors f n+1 := {f n+1 (α), α ∈ Z} ∈ ℓ d+1 (Z) is defined as

f n+1 (α) := S An f n (α) = β∈Z A n (α -2β) f n (β), α ∈ Z. (1)
Therefore the refinement rules, possibly different from level to level, are averaging rules with average coefficients given by real matrices defining the so called level-n subdivision mask

A n := {A n (α), α ∈ Z} ∈ ℓ (d+1)×(d+1) (Z).
Whenever convergent, a vector subdivision scheme defines a continuous vector limit function for any choice of initial data f 0 . In order to formally define a notion of convergence, we need to attach the data f n , generated at the n-th step of the subdivision procedure, to the real parameter values t n = {t n (α), α ∈ Z} with t n (α) < t n (α + 1) and t n (α + 1) -t n (α) = 2 -n , n ≥ 0. In this way, the vector subdivision scheme {S An , n ≥ 0} is said to be convergent in ℓ d+1 ∞ (Z) if for any initial vector sequence f ∈ ℓ d+1 ∞ (Z) there exists a continuous vector function g f : R → R d+1 , such that for any compact K ⊂ R lim

n→∞ max α∈Z∩2 n K g f (t n (α)) -S A n-1 • • • S A 0 f (α) ∞ = 0
, and g f = 0 for some initial vector data f . Moreover, a vector subdivision scheme is said to be contractive if g f = 0 for any initial f , and it is called C ℓ -convergent if g f ∈ C ℓ (R, R d+1 ) for any initial vector data. We also recall that, when the initial data is the matrix sequence

δ I d+1 = {δ I d+1 (α), α ∈ Z} with δ I d+1 (α) = I d+1 , if α = 0, 0, if α ∈ Z \ {0},
then the limit of the vector subdivision scheme is the so called basic matrix limit function, hereinafter denoted by Φ : R → R (d+1)×(d+1) .

Vector subdivision schemes, natural extension of scalar subdivision schemes, play an important role in the analysis of multivariate subdivision schemes [START_REF] Charina | Regularity of multivariate vector subdivision schemes[END_REF] when dealing with refinable spaces generated by more than one function (see, e.g., [START_REF] Cohen | Stability and inter-dependence of matrix subdivision schemes[END_REF][START_REF] Conti | A new subdivision method for bivariate splines on the four-directional mesh[END_REF][START_REF] Conti | Interpolatory rank-1 vector subdivision schemes[END_REF][START_REF] Micchelli | On vector subdivision[END_REF]), as well as in the analysis of Hermite subdivision schemes. The latter are a special type of vector subdivision schemes aimed at refining vector valued sequences with the understanding that, with some extent, the (k + 1)-th component of such a sequence corresponds to the k-th derivative of an underlined function (see, for instance, [START_REF] Dyn | Analysis of Hermite-interpolatory subdivision schemes[END_REF][START_REF] Han | Multivariate refinable Hermite interpolant[END_REF][START_REF] Merrien | A generalized Taylor factorization for Hermite subdivision schemes[END_REF]). The latter fact makes a Hermite subdivision scheme non-stationary by nature: refining vector valued sequences approaching derivatives at refined grids requires to involve level dependent matrices.

Vector Hermite-type subdivision schemes are the main topic of this paper. A first contribution of our work consists in the classification of this category of schemes. In fact, though a Hermite subdivision scheme is non-stationary by nature, its non-stationarity can be of two types, making useful the distinction between Inherently Stationary (I.S.) and Inherently Non-Stationary (I.N.S.) Hermite subdivision schemes. When classifying Hermite-type subdivision schemes, the difference between interpolatory and non-interpolatory (or approximating) ones should be also considered. Starting with an initial set of Hermite-type data ( i.e. vectors containing function values and associated derivatives) interpolatory Hermite subdivision schemes are able to simultaneously design points and associated derivatives, thus defining, in the limit, a continuous vector function with each component being the derivative of the previous one. Moreover, they are designed such that the initial set of vector data is interpolated as well as all sets of vector data generated by the subdivision process. On the contrary, non-interpolatory or approximating Hermite subdivision schemes, while still generating a continuous vector function with each component being an approximation of the derivative of the previous one, provide in the limit a vector function which is only approximating the initial set of vector data. Such schemes, also investigated for example in [START_REF] Han | Noninterpolatory Hermite subdivision schemes[END_REF], turn out to be of interest whenever the interpolatory case produces "unfair" limit functions with unwanted wiggles or undulations, as well as when non-exact data are available.

In this paper we present a novel idea for the construction of non-interpolatory Hermite subdivision schemes, based on a generalization of the de Rham corner cutting strategy [START_REF] De Rham | Sur une courbe plane[END_REF]. This is why the resulting schemes are called Hermite subdivision schemes of de Rham-type. Other examples of application of the de Rham strategy can be also found in the previous literature. In particular, in [START_REF] Conti | Dual univariate m-ary subdivision schemes of de Rham-type[END_REF] the de Rham construction is applied in a more general but scalar context, while in [START_REF] Dubuc | de Rham Transform of a Hermite Subdivision Scheme, Approximation Theory[END_REF] the Hermite case was tackled for the first time. The de Rham construction considered in this paper, at each subdivision step consists in the double application of an interpolatory Hermite subdivision operator followed by a decimation step selecting only the odd elements of the resulting sequence. Therefore, the de Rham strategy provides Hermite subdivision schemes which are dual by construction, hence approximating the initial data rather than interpolating them. We recall that, from a geometric point of view, primal vector subdivision schemes are those that at each iteration retain or modify the given vectors and create a "new" vector in between two "old" ones. Dual schemes, instead, discard all given vectors after creating two "new" ones in between any pair of them. This fact is algebraically connected with the choice of the parameter values t n := {t n (α), α ∈ Z} (see, e.g, [START_REF] Conti | Polynomial reproduction for univariate subdivision schemes of any arity[END_REF] for more details). More precisely, the primal parametrization is such that

t n (α) := α 2 n , α ∈ Z, n ≥ 0.
On the contrary, the dual parametrization is given by

t n (α) := α -1/2 2 n , α ∈ Z, n ≥ 0. ( 2
)
Another contribution of this paper consists in the derivation of two new theoretical results (extension of the results in [START_REF] Dubuc | de Rham Transform of a Hermite Subdivision Scheme, Approximation Theory[END_REF]) for the analysis of de Rham-type Hermite subdivision schemes. Furthermore, the new notion of HC ℓ -convergence is introduced to allow the construction of Hermite schemes of order d + 1 with the first element of the vector valued limit function of regularity ℓ ≥ d.

The organization of the paper is as follows: Section 2 provides the most general formulation of vector Hermite-type subdivision schemes together with the definition of HC ℓ -convergence. Section 3 characterizes the subclass of Inherently Stationary (I.S.) Hermite subdivision schemes and recalls specific tools for the analysis of this type of Hermite schemes. Interpolatory versus dual approximating Hermite subdivision schemes are discussed in Section 4 where the so called de Rham-type construction is detailed and two new theoretical results for the analysis of de Rham-type Hermite subdivision schemes are given. The closing Section 5 illustrates applications of the de Rham-type approach: two new dual non-interpolatory subdivision schemes obtained when starting with Merrien's interpolatory schemes in [START_REF] Merrien | A family of Hermite interpolants by bisection algorithms[END_REF][START_REF] Merrien | Interpolants dHermite C 2 obtenus par subdivision, M2AN Math[END_REF] are presented. For these schemes a complete smoothness analysis is given and explicative pictures are provided.

In all sections the following notation is used: vectors in R d+1 are labeled by lowercase boldface letters as y; matrices in R (d+1)×(d+1) are written as uppercase boldface letters, like A; the space of polynomials of degree at most n is denoted by P n ; sequences of vectors in R d+1 are denoted by lowercase calligraphic letters as f := {f (α), α ∈ Z} and the space of such sequences is denoted by ℓ d+1 (Z) and by ℓ d+1 ∞ (Z) if their infinity norm is bounded; sequences of matrices in R (d+1)×(d+1) are denoted by uppercase calligraphic letters as A := {A(α), α ∈ Z}, and the space of such sequences is denoted by ℓ (d+1)×(d+1) (Z). The symbol • ∞ is to denote the infinity norm of a matrix, a function or a sequence.

Hermite subdivision schemes

Hermite subdivision schemes of order d + 1 simultaneously design function values and associated derivatives so that their limit is a continuous vector function R → R d+1 with each component being the derivative of the previous one. Since such subdivision schemes generate finer and finer sequences of "Hermite-type" data f n which are associated with "shifted" versions of dyadic parameters, the first component of f n (α) can be interpreted as getting closer to the value of a function ψ n at a parameter t n (α), while the next one describes the value of its first derivative at the same location, i.e. ψ n (t n (α)). This is why for any Hermite subdivision scheme the relation between D n+1 f n+1 and D n f n is given by the rule

D n+1 f n+1 = S An D n f n = β∈Z A n (• -2β) D n f n (β), n ≥ 0 , (3)
where A n := {A n (α), α ∈ Z} is the level-n mask and D is the diagonal matrix with diagonal entries 2 -j , j = 0, . . . , d. Obviously, (3) can also be written in a more standard way as

f n+1 = β∈Z D -(n+1) A n (• -2β) D n f n (β), n ≥ 0 , (4)
namely in terms of a level-n subdivision operator S An associated to the level-n mask

A n := {D -(n+1) A n (α) D n , α ∈ Z} . (5)
To simplify notation, from now on a Hermite subdivision scheme based on (5) will be simply denoted by H {An, n ≥ 0} .

Due to the fact that the limit vector function of any reasonable Hermite subdivision scheme must be of special type (as described at the beginning of this section), the following new and more specialized definition of HC-convergence is given.

Definition 1 A Hermite subdivision scheme H {An, n ≥ 0} acting on vectors in ℓ d+1 (Z) is called HC ℓconvergent with ℓ ≥ d if for any initial vector sequence f 0 ∈ ℓ d+1 (Z) and the corresponding sequences of refinements {f n , n ≥ 0}, there exists a vector function φ

= [φ [i] ] i=0,...,d ∈ C ℓ-d R, R d+1 with φ [0] ∈ C ℓ (R, R) such that for any compact K ⊂ R lim n→∞ max α∈Z∩2 n K f n (α) -φ 2 -n α ∞ = 0 and φ [i] = d i φ [0] dx i , i = 1, . . . , d .
Remark 1 To avoid confusion it is important to remark that, indeed, the notions of C ℓ and HC ℓ convergence are intrinsically different. The first notion refers to the minimal smoothness of the entries of the vector limit function, while the second to the maximal one. The reason why we did not select a unified definition is to be consistent with the existing literature on vector and Hermite subdivision schemes, respectively. Note also that the new notion of HC ℓ -convergence allows the construction of Hermite schemes of order d + 1 with the first element of the vector valued limit function having regularity ℓ ≥ d.

Inherently Stationary Hermite subdivision schemes

From the previous section we know that Hermite subdivision schemes are essentially given by the repeated application of level-dependent subdivision operators S An associated to the level-n masks

A n := {D -(n+1) A n (α) D n , α ∈ Z}. Now,
f n+1 = β∈Z D -(n+1) A (• -2β) D n f n (β), n ≥ 0 ,
or, equivalently, that the Hermite scheme is based on the repeated application of the subdivision operators S An , n ≥ 0 associated to the masks

A := {D -(n+1) A(α) D n , α ∈ Z}, n ≥ 0 . ( 6
)
Otherwise the Hermite subdivision scheme is named Inherently Non-Stationary (I.N.S.).

Remark 2We remark that I.N.S. Hermite subdivision schemes occur whenever the first row of the basic matrix limit function Φ belongs to some space of exponential polynomials (see, e.g., [START_REF] Conti | Algebraic conditions on non-stationary subdivision symbols for exponential polynomial reproduction[END_REF]). An example of such kind of I.N.S. Hermite subdivision schemes is presented in [START_REF] Romani | A circle-preserving C 2 Hermite interpolatory subdivision scheme with tension control[END_REF].

In accordance with the notation of the previous section, for shortness, from now on an I.S. Hermite subdivision scheme will be denoted by H A .

In the rest of the paper we focus our attention on the class of inherently stationary Hermite subdivision schemes only. We emphasize that if an I.S. Hermite subdivision scheme H A defining the vector sequences {f n , n ≥ 0} converges in the sense specified in Definition 1, then the sequence

D n f n converges to the vector function [φ [0] , 0 • • • , 0] T .
This implies the existence of a convergent stationary counterpart of any inherently stationary Hermite subdivision scheme, hereinafter denoted by S A . This is a crucial fact that we are going to use in the following for the analysis of I.S. Hermite subdivision schemes.

Analysis tools for Inherently Stationary Hermite subdivision schemes

We start this section with some definitions needed to the development of the forthcoming theoretical results.

Definition 3 A primal Hermite subdivision scheme H A is called interpolatory if, starting from any vector sequence f 0 ∈ ℓ d+1 (Z), then f n+1 (2•) = f n (•) for all n ≥ 0. This is equivalent to the following property either of the mask A or of the mask A := {D -(n+1) A(α)D n , α ∈ Z}:

A(0) = D, A(0) = I, A(2β) = A(2β) = 0, ∀β = 0.
Definition 4 We say that a Hermite subdivision scheme

H A reproduces a function ϕ ∈ C d (R) if for any initial vector sequence f 0 = {f 0 (α), α ∈ Z} such that f 0 (α) = [ϕ(α), . . . , ϕ (d) (α)] T , we have f n = {f n (α), α ∈ Z} with f n (α) = [ϕ(α/2 n ), . . . , ϕ (d) (α/2 n )] T for any n ∈ N, α ∈ Z.
We continue by associating to any function

f ∈ C d (R) the vector sequence v f = {v f (α), α ∈ Z} ∈ ℓ d+1 (Z) with v f (α) := [f (α), f ′ (α), . . . , f (d) (α)] T , α ∈ Z. (7)
A fundamental property of Hermite subdivision schemes is the spectral condition introduced in [START_REF] Dubuc | Hermite subdivision schemes and Taylor polynomials[END_REF], which requires the existence of particular polynomial eigenvalues of the subdivision operator S A , stationary counterpart of H A .

Definition 5 A stationary mask A or its associated subdivision operator S A satisfies the spectral condition of order ℓ + 1 if there exist polynomials p j ∈ P j , deg p j = j, j = 0, . . . , ℓ, such that

S A v pj = 1 2 j v pj , where v pj = {v pj (α), α ∈ Z}, v pj (α) is defined as in (7) and p j is normalized such that p j (x) = 1 j! x j + • • • . Remark 3
In [START_REF] Dubuc | Hermite subdivision schemes and Taylor polynomials[END_REF] it was proven that the spectral condition is also equivalent to the sum rule introduced by Han et al. in [START_REF] Han | Vector cascade algorithms and refinable functions in Sobolev spaces[END_REF][START_REF] Han | Noninterpolatory Hermite subdivision schemes[END_REF].

In the following proposition we discuss a property fulfilled by the stationary counterpart of a Hermite subdivision scheme reproducing polynomials of a certain degree.

Proposition 1 Let H A be a Hermite subdivision scheme of order d + 1, reproducing a basis of P ℓ where ℓ ≥ d. Then its stationary counterpart S A satisfies the spectral condition of order ℓ + 1 for the sequence of polynomials p j (x) =

x j j! , j = 0, . . . , ℓ.

Proof: If a basis of P ℓ is reproduced by H A then, using linearity, any polynomial of P ℓ is reproduced. For j = 0, . . . , ℓ, let

f 0 := v pj . Using (3) at step n = 0, D f 1 (α) = β∈Z A (α -2β) f 0 (β), α ∈ Z.
Since p j is reproduced by the Hermite scheme, we deduce that starting from

f 0 = {f 0 (α), α ∈ Z} with f 0 (α) = [p j (α), . . . , p (d)
j (α)] T • in case j ≤ d, f 1 (α) =                 p j (α/2) p ′ j (α/2) . . . p (j) j (α/2) p (j+1) j (α/2) . . . p (d) j (α/2)                 =                 1 2 j α j j! 1 2 j-1 α j-1 (j-1)! . . . 1 0 . . . 0                 and Df 1 (α) = 1 2 j                 α j j! α j-1 (j-1)! . . . 1 0 . . . 0                 = 1 2 j v pj (α),
• while in case j > d,

f 1 (α) =        p j (α/2) p ′ j (α/2) . . . p (d) j (α/2)        =         1 2 j α j j! 1 2 j-1 α j-1 (j-1)! . . . 1 2 j-d α j-d (j-d)!         and Df 1 (α) = 1 2 j         α j j! α j-1 (j-1)! . . . α j-d (j-d)!         = 1 2 j v pj (α),
which is exactly the spectral condition at step j, i.e.

1 2 j v pj = Df 1 = S A f 0 = S A v pj . Remark 4
In [START_REF] Dyn | Analysis of Hermite-interpolatory subdivision schemes[END_REF] it is proven that, for interpolatory Hermite subdivision schemes of order d+1, the reproduction of polynomials of degree at least d is a necessary condition to obtain HC d -convergence.

The next theorem recalls a factorization result proven in [START_REF] Merrien | A generalized Taylor factorization for Hermite subdivision schemes[END_REF] for Hermite subdivision schemes whose stationary counterpart satisfies the spectral condition.

Theorem 2 [18, Theorem 2] Let H A be a Hermite subdivision scheme of order d + 1. If the mask A ∈ ℓ (d+1)×(d+1) (Z) of its stationary counterpart S A satisfies the spectral condition of order at least d + 1, then there exists a finitely supported mask B in ℓ (d+1)×(d+1) (Z) such that

T d S A = 2 -d S B T d ,
where

T d :=         δ -1 . . . -1 (d-1)! -1 d! δ . . . . . . -1 (d-1)! . . . -1 . . . δ -1 1         , ( δy
)(α) = y(α + 1) -y(α),
is the Taylor operator of order d + 1 acting on ℓ d+1 (Z) and S B is the stationary subdivision scheme with mask B, usually termed the Taylor subdivision scheme associated to S A .

Following the reasoning in [START_REF] Merrien | A generalized Taylor factorization for Hermite subdivision schemes[END_REF] we can now prove the following theorem that allows us to check the convergence of a Hermite subdivision scheme by studying the behavior of the associated Taylor subdivision scheme.

Theorem 3 Let H A be a Hermite subdivision scheme of order d + 1. Suppose that the mask A ∈ ℓ (d+1)×(d+1) (Z) of its stationary counterpart S A satisfies the spectral condition of order at least d + 1 and the associated Taylor subdivision scheme S B is C k -convergent. Then the Hermite subdivision scheme H A is HC d+k -convergent.

Proof: The proof follows the lines of the proof of [18, Theorem 21] and following results. We begin by using the contractivity of S B and properties of vector subdivision schemes to prove that there exists a continuous function

ψ ∈ C k (R, R) such that the last component of f n (α) = [f n (α), • • • , f (d) n (α)] T satisfies lim n→∞ max α∈Z∩2 n K |f (d) n (α) -ψ(2 -n α)| = 0,
for any compact subset K ⊂ R. Then, step by step, using successive integrations (see [START_REF] Merrien | A generalized Taylor factorization for Hermite subdivision schemes[END_REF]Lemma 22]), we prove that each component converges. The integration gives that, at each step, we get a primitive function of the previous one so that for the first component ϕ of the vector valued limit function we have ϕ ∈ C d+k (R, R) and

ϕ (d) = ψ ∈ C k (R, R).
4 Interpolatory versus dual approximating Hermite schemes: the de Rham approach

For an interpolatory Hermite subdivision scheme H A of order d+1, with mask A = {D -(n+1) A(α)D n , α ∈ Z}, let us define a new dual non-interpolatory Hermite subdivision scheme by taking the de Rham transform of H A and itself as follows (see also [START_REF] Dubuc | de Rham Transform of a Hermite Subdivision Scheme, Approximation Theory[END_REF]). Starting with the data f 0 ∈ ℓ d+1 (Z), for n ≥ 0 we define the sequence f n+1 = {f n+1 (α), α ∈ Z} by computing

D n+1 f n+1 (β) := γ∈Z A(β -2γ) D n f n (γ), β ∈ Z D n+2 f n+2 (α) := β∈Z A(α -2β) D n+1 f n+1 (β), α ∈ Z f n+1 (α) := f n+2 (2α + 1), α ∈ Z.
Therefore

D n+1 f n+1 (α) = D -1 D n+2 f n+2 (2α + 1) = D -1 β∈Z A(2α + 1 -2β) γ∈Z A(β -2γ) D n f n (γ) = D -1 γ∈Z   β∈Z A(2α + 1 -2β) A(β -2γ)   D n f n (γ) = D -1 γ∈Z   β∈Z A(2α + 1 -4γ -2β) A(β)   D n f n (γ) = γ∈Z A(α -2γ) D n f n (γ),
where

A(α) = D -1 β∈Z A(2α + 1 -2β)A(β), α ∈ Z. (8)
Definition 6 For a Hermite subdivision scheme H A , the associated de Rham-type Hermite subdivision scheme H A is the Hermite subdivision scheme having mask A = D -(n+1) A(α)D n , α ∈ Z where A = {A(α), α ∈ Z} is defined by (8).

Remark 5 We recall from [START_REF] Dubuc | de Rham Transform of a Hermite Subdivision Scheme, Approximation Theory[END_REF] that, if the support of S A is [σ, σ ′ ], then the support of its de Rham transform S A is contained in [(3σ -1)/2, (3σ ′ -1)/2].

We continue by discussing the parametrization of the generated de Rham-type Hermite subdivision scheme. At each step, given a sequence f n associated to the parameter values t n , the primal interpolatory Hermite subdivision scheme is applied twice to get the sequence associated to the parameter values t n+2 (4α) := t n (α), t n+2 (4α + 1) := 3t n (α) + t n (α + 1) 4 , and

t n+2 (4α + 2) := t n (α) + t n (α + 1) 2 , t n+2 (4α + 3) := t n (α) + 3t n (α + 1) 4 .
The sequence f n+2 is then decimated (by taking the odd entries only) to get f n+1 , which is therefore associated to the dual parameter values

t n+1 (2α) = 3t n (α) + t n (α + 1) 4 , t n+1 (2α + 1) = t n (α) + 3t n (α + 1) 4 ,
meaning that the corresponding subdivision scheme is dual in the sense of (2).

We conclude this section by proving that, if the stationary counterpart of the interpolatory Hermite subdivision scheme satisfies a spectral condition of order ℓ + 1, so does the stationary counterpart of the de Rham-type Hermite subdivision scheme. This result extends [9, Theorem 5].

Theorem 4 Suppose that S A satisfies the spectral condition of order ℓ + 1. Then the corresponding de Rham transform S A , with mask A = {A(α), α ∈ Z} defined by (8), also satisfies the spectral condition of order ℓ + 1.

Proof:

Since S A satisfies the spectral condition of order ℓ + 1, for i = 0, . . . , ℓ for p i ∈ P i ,

p i (x) = 1 i! x i + • • • and for the sequence v i with elements v i (α) = [p i (α), . . . , p (d) i (α)] T , α ∈ Z we know that S A v i = 1 2 i v i ⇔ β∈Z A(α -2β) v i (β) = 1 2 i v i (α), α ∈ Z, (9)
where, for the sake of simplicity, we omit p i from the lower index of the sequence v i (differently from Definition 5). Our aim is to show by induction that for i = 0, . . . , ℓ we are able to build the polynomials pi with leading coefficient 1/i! and the corresponding vector sequences vi such that

S A vi = 1 2 i vi ⇔ β∈Z Ā(α -2β) vi (β) = 1 2 i vi (α), α ∈ Z. (10)
We begin by proving that (9) implies

β∈Z Ā(α -2β) v j (β) = 1 4 j D -1 v j (2α + 1), j = 0, . . . , ℓ, α ∈ Z. (11)
Indeed,

β∈Z Ā(α -2β)v j (β) = D -1 β∈Z γ∈Z A(2α -4β -2γ + 1)A(γ)v j (β) = D -1 β∈Z γ ′ ∈Z A(2α + 1 -2γ ′ )A(γ ′ -2β)v j (β) = D -1 γ ′ ∈Z β∈Z A(2α + 1 -2γ ′ )A(γ ′ -2β)v j (β) = D -1 γ ′ ∈Z A(2α + 1 -2γ ′ ) 1 2 j v j (γ ′ ) = 1 4 j D -1 v j (2α + 1).
We continue proving the claim by induction on j: for j = 0, we define p0 (x) = 1 = p 0 (x) so that v0 (α) = v 0 (α) = [1, 0, . . . , 0] T and from [START_REF] Dyn | Analysis of Hermite-interpolatory subdivision schemes[END_REF] we get

β∈Z Ā(α -2β)v 0 (β) = β∈Z Ā(α -2β)v 0 (β) = D -1 v 0 (2α + 1) = v 0 (α) = v0 (α),
which is S A v0 = 1 2 0 v0 . Next, we assume that ( 10) is true for i = 0, 1, . . . , j -1 where 0 < j ≤ ℓ. Since {p j , pj-1 , . . . , p0 } is a basis of P j , and since we know that the leading coefficient of p j is 1/j!, we can write

p j (2x + 1) = 2 j p j (x) + j-1 i=0 λ j,i pi (x).
Differentiating up to d times both sides of the previous equation with respect to x and evaluating at α we get

D -1 v j (2α + 1) = 2 j v j (α) + j-1 i=0 λ j,i vi (α), α ∈ Z. ( 12
)
Then, let us define pj (x) = p j (x) + j-1 i=0 µ j,i pj (x) where µ j,i = -λ j,i 2 i-j 2 j -2 i and construct the corresponding vector sequence vpj that we are going to simply denote as vj . Note that pj is a polynomial of degree j and its leading coefficient is exactly 1/j!. Therefore, differentiating pj up to d times and evaluating at α, we obtain

vj (α) = v j (α) + j-1 i=0 µ j,i vi (α). ( 13
)
Next, using the induction assumption, we observe that for i = 0, 1, . . . , j -1,

β∈Z Ā(α -2β)v i (β) = 1 2 i vi (α), α ∈ Z.
Thus, due to ( 11), ( 13) and the induction hypothesis we have that

β∈Z Ā(α -2β)v j (β) = β∈Z Ā(α -2β) v j (β) + j-1 i=0 µ j,i vi (β) = 1 4 j D -1 v j (2α + 1) + j-1 i=0 µ j,i 2 i vi (α) = 1 2 j v j (α) + j-1 i=0 λ j,i 4 j + µ j,i 2 i vi (α) (from (12)) = 1 2 j v j (α) + j-1 i=0 µ j,i - 1 4 j 2 j -2 i 2 i-j + 1 2 i vi (α) = 1 2 j v j (α) + j-1 i=0
µ j,i vi (α) = 1 2 j vj (α) (from ( 13)).

We conclude that β∈Z Ā(α -2β)v j (β) = 1 2 j vj (α), α ∈ Z which is the end of induction step j.

As a consequence of Theorem 4, we get the following Corollary, extension of [9, Corollary 6].

Corollary 5 Suppose that S A satisfies the spectral condition of order ℓ + 1 with the sequence of polynomials p j (x) = x j /j! and corresponding vector sequences v j for j = 0, . . . , ℓ. Then S A with mask A = {A(α), α ∈ Z} defined by (8) satisfies the spectral condition of order ℓ + 1 with the sequence of polynomials p j (x) = (x -1/2) j /j! and corresponding vector sequences vj for j = 0, . . . , ℓ.

Proof: We use the notation of the previous theorem and prove the claim by induction.

For j = 0, p 0 (x) = 1, and we have seen in the proof of the previous theorem that p0 (x) = 1 = p 0 (x -1/2). Next, we suppose that for i = 0, . . . , j -1, pi (x) = (x -1/2) i /i!, and we write p j (2x + 1) as

p j (2x + 1) = 2 j x j /j! + 2 j (x -1/2 + 1) j /j! -2 j (x -1/2 + 1/2) j /j! = 2 j x j /j! + 2 j j! j-1 i=0 j i (1 -1/2 j-i )(x -1/2) i = 2 j p j (x) + j-1 i=0 λ j,i pi (x), with λ j,i = 2 j -2 i (j-i)! .
In the proof of the previous theorem we have seen that pj (x) = p j (x) + j-1 i=0 µ j,i pi (x) where µ j,i = -λ j,i 2 i-j 2 j -2 i , so that we obtain pj (x) = p j (x) -

j-1 i=0 λ j,i 2 i-j 2 j -2 i pi (x) = p j (x) - j-1 i=0 2 j -2 i (j -i)! 2 i-j 2 j -2 i pi (x) = (x -1 2 + 1 2 ) j j! - j-1 i=0 2 i-j (j -i)! pi (x) = 1 j! j i=0 j i 2 i-j (x -1/2) i - 1 j! j-1 i=0 j i (x -1/2) i 2 i-j = (x -1/2) j /j!
and the result is proved by this finite induction.

Applications

In this section we apply the de Rham strategy to two known Hermite interpolatory subdivision schemes and obtain two new dual non-interpolatory Hermite subdivision schemes whose convergence and smoothness is investigated with the support of the theoretical results in the previous sections and of the sufficient conditions for convergence of stationary vector subdivision schemes in [START_REF] Charina | Regularity of multivariate vector subdivision schemes[END_REF]. As a matter of fact, giving up the interpolation condition, we manage to increase by one the regularity of the basic limit function, while its support width is only enlarged by one.

A dual non-interpolatory HC 2 Hermite subdivision scheme of order 2

We start with the interpolatory Hermite subdivision scheme of order d + 1 = 2 proposed by Merrien in [START_REF] Merrien | A family of Hermite interpolants by bisection algorithms[END_REF], which depends on two free parameters λ, µ ∈ R. The non-zero matrices of the mask A of its stationary counterpart are

A(-1) = 1 2 λ 1 2 (1 -µ) µ 4 , A(0) = 1 0 0 1 2 , A(1) = 1 2 -λ 1 2 (µ -1) µ 4 .
For any values of the parameters λ and µ, this scheme reproduces polynomials of degree 1. Moreover it reproduces P 2 if and only if λ = -1 8 , and P 3 if also µ = -1 2 . Applying the de Rham transform, we end up with the dual approximating Hermite subdivision scheme having stationary counterpart S A . The non-zero entries of its mask A are given by

A(-2) = 1 8 2 + 4λ(1 -µ) 4λ + 2λµ 4 -2µ -2µ 2 µ 2 + 8λ(1 -µ) , A(-1) = 1 8 6 -4λ(1 -µ) 8λ -2λµ 4 -2µ -2µ 2 µ 2 -8λ(1 -µ) + 2µ , A(0) = 1 8 6 -4λ(1 -µ) -8λ + 2λµ -4 + 2µ + 2µ 2 µ 2 -8λ(1 -µ) + 2µ , A(1) = 1 8 2 + 4λ(1 -µ) -4λ -2λµ -4 + 2µ + 2µ 2 µ 2 + 8λ(1 -µ)
.

Since H A satisfies the spectral condition of order 2, we can construct the mask

B = {B(α), α ∈ Z} supported on [-1, 1] such that z -1 -1 -1 0 1 A * (z) = 1 2 B * (z) z -2 -1 -1 0 1 .
Moreover, due to the fact that the common eigenvector of B e := α∈Z B(2α) and B o := α∈Z B(2α+

1) is [0, 1]
T , in view of the results in [START_REF] Charina | Regularity of multivariate vector subdivision schemes[END_REF], the difference mask of B, hereinafter denoted by B, can be computed as

1 0 0 z -1 -1 B * (z) = B * (z) 1 0 0 z -2 -1 .
The non-zero entries of the mask B are

B(-1) = 1 4 2 -4λ(µ -1) 2λ(µ + 2) -2µ 2 -2µ + 4 µ 2 -8λ(µ -1)
,

B(0) = 1 4 2µ 2 + 2µ + 8λ(µ -1) 4λ(µ -1) -µ 2 0 2µ + 16λ(µ -1) , B(1) = 1 4 2µ 2 + 2µ -4λ(µ -1) -2 2 -2µ -6λµ -µ 2 2µ 2 + 2µ -4 4 -2µ -8λ(µ -1) -µ 2 .
To show that the Hermite subdivision scheme H A is HC 2 (namely, accordingly to Definition 1, S A generates a C 2 limit function) we show that S B is C 1 . Following Theorem 3 this is done by proving that its divided difference scheme S C , with C = 2 B, is C 0 . In view of the results in [START_REF] Charina | Regularity of multivariate vector subdivision schemes[END_REF], a necessary condition for S C to be convergent is that C e and C o have at least a common eigenvector associated with the eigenvalue 1. Since,

C o = 1 2 8λ(1 -µ) + 2µ + 2µ 2 4λ(1 -µ) -µ 2 -2µ + 2 0 4 -2µ + 16λ(1 -µ)
and

C e = 1 2 -8λ(1 -µ) + 2µ + 2µ 2 -4λ(1 -µ) -µ 2 0 2µ -16λ(1 -µ) ,
they have a common eigenvalue 1 if and only if the following conditions are fulfilled:

(i) 4λ(1 -µ) + µ + µ 2 = 1 or 2 -µ + 8λ(1 -µ) = 1, for C o and (ii) -4λ(1 -µ) + µ + µ 2 = 1 or µ -8λ(1 -µ) = 1, for C e .
To make the second equation in (i) and (ii) satisfied, we set λ = -1 8 . Under this assumption the joint 1-eigenspace E C is the eigenvector [1, 2] T .

In order to apply the theory in [START_REF] Charina | Regularity of multivariate vector subdivision schemes[END_REF] we continue by applying the similarity transform S = 1 0 2 1 to the matrix mask C ending up with the matrix mask

C = {C(α) = S -1 C(α) S, α ∈ Z} such that E C = [1, 0] T . The non-zero elements of the mask C are C(-1) = 1 4 1 -1 -1 2 µ 2 3µ + 2µ 2 , C(0) = 1 4 4 1 -µ -2µ 2 0 2 + 2µ + 4µ 2 , C(1) = 1 4 3 4 -5 2 µ -2µ 2 -2 -2 + 3µ + 2µ 2 .
For C we construct the difference mask E = {E(α), α ∈ Z} satisfying

z -1 -1 0 0 1 C * (z) = E * (z) z -2 -1 0 0 1 ,
whose non-zero entries are

E(-1) = 1 8 0 -µ -2 0 0 , E(0) = 1 8 0 -4µ 2 -µ + 4 0 4µ 2 + 6µ , E(1) = 1 8 2 6 -3µ 0 8µ 2 + 4µ + 4 , E(2) = 1 8 6 4µ 2 + 5µ -8 4 4µ 2 + 6µ -4 .
Now we look for a range of µ such that for a small k (say k < 10) the iterated subdivision scheme

S k E is contractive, that is S k E ∞ < 1.
For µ ∈ [-0.7, 0.425] we find S 4 E ∞ < 1, so that we can conclude that the scheme H A is HC 2 , while for µ in the same range H A is only HC 1 .

Figures 1 and2 are to compare the basic matrix limit functions of H A and H A for the parameter choice µ = -1 2 .

-2

-1 0 1 2 -1 0 1 -2 -1 0 1 2 -1 0 1 -2 -1 0 1 2 -1 0 1 -2 -1 0 1 2 -1 0 1
Figure 1: Basic matrix limit function of the interpolatory Hermite subdivision scheme H A with µ = -1 2 .

- 5.2 A dual non-interpolatory HC 3 Hermite subdivision scheme of order 3

2 -1 0 1 2 -1 0 1 -2 -1 0 1 2 -1 0 1 -2 -1 0 1 2 -1 0 1 -2 -1 0 1 2 -1 0
In this case we start with the interpolatory Hermite subdivision scheme of order d + 1 = 3 proposed by Merrien in [START_REF] Merrien | A family of Hermite interpolants by bisection algorithms[END_REF]. This is a 2-point subdivision scheme depending on several real parameters. The non-zero matrices of the mask A of its stationary counterpart are

A(-1) = D   α 1 α 2 α 3 β 1 β 2 β 3 γ 1 γ 2 γ 3   , A(0) = D, A(1) = D   α 1 -α 2 α 3 -β 1 β 2 -β 3 γ 1 -γ 2 γ 3   where D =   1 0 0 0 1 2 0 0 0 1 4   .
To guarantee reproduction of degree 3 polynomials, among the free parameters, the following constraints are assumed (see [START_REF] Guglielmi | Convergence analysis of C 2 Hermite interpolatory subdivision schemes by explicit joint spectral radius formulas[END_REF]):

α 1 = 1 2 , γ 1 = 0, β 2 = 1 -β 1 2 , γ 3 = 1 -γ 2 2 , α 3 = -1 -8α 2 16 , β 3 = 2β 1 -3 24 .
Since the mask under consideration is now depending only on α 2 , β 1 , γ 2 , for shortness we rename the free parameters as α, β, γ, respectively, and denote by R their range of variation given in [START_REF] Guglielmi | Convergence analysis of C 2 Hermite interpolatory subdivision schemes by explicit joint spectral radius formulas[END_REF] to ensure HC 2 -continuity of the subdivision scheme. Therefore the mask we consider reads as

A(-1) =    1 2 α -1-8α 16 β 2 1-β 4 2β-3 48 0 γ 4 1-γ 8    , A(0) =    1 0 0 0 1 2 0 0 0 1 4    , A(1) =    1 2 -α -1-8α 16 -β 2 1-β 4 -2β-3 48 0 -γ 4 1-γ 8    , (α, β, γ) ∈ R.
Applying the de Rham transform we end up with the dual approximating Hermite subdivision scheme H A . The non-zero entries of the mask A are A(-2), A(-1), A(0), A(1) and the associated symbol A * (z) is a 3 × 3 matrix with polynomial entries a * ij (z), i, j = 0, 1, 2, given by

a * 00 (z) = 1 384 (192αβ + 96)z -2 + (288 -192αβ)z -1 + (288 -192αβ) + (192αβ + 96)z , a * 01 (z) = 1 384 (288α -96αβ -6γ(8α + 1))z -2 + (288α + 96αβ -6γ(8α + 1))z -1 + (6γ(8α + 1) -96αβ -288α) + (96αβ -288α + 6γ(8α + 1))z , a * 02 (z) = 1 384 (3γ -144α + 16αβ + 24αγ -15)z -2 + (3γ -144α -16αβ + 24αγ -21)z -1 + (3γ -144α -16αβ + 24αγ -21) + (3γ -144α + 16αβ + 24αγ -15)z , a * 10 (z) = 1 384 (-96β(β -3))z -2 + (-96β(β -3))z -1 + (96β(β -3)) + (96β(β -3))z , a * 11 (z) = 1 384 (48(β -1) 2 + 384αβ + 4γ(2β -3))z -2 + (48β 2 -384αβ -192β -4γ(2β -3) + 144)z -1 + (48β 2 -384αβ -192β -4γ(2β -3) + 144) + (48(β -1) 2 + 384αβ + 4γ(2β -3))z , a * 12 (z) = 1 384 (6γ -192αβ -4βγ -8β 2 -18)z -2 + (48β -6γ + 192αβ + 4βγ -8β 2 -18)z -1 + (6γ -48β -192αβ -4βγ + 8β 2 + 18) + (192αβ -6γ + 4βγ + 8β 2 + 18)z), a * 20 (z) = 1 384 (192βγ)z -2 + (-192βγ)z -1 + (-192βγ) + (192βγ)z , a * 21 (z) = 1 384 (-48γ(2β + γ -3))z -2 + (48γ(2β -γ + 3))z -1 + (-48γ(2β -γ + 3)) + (48γ(2β + γ -3))z , a * 22 (z) = 1 384 (24γ 2 + 8γ(2β -9) + 24)z -2 + (24γ 2 -8γ(2β + 9) + 72)z -1 + (24γ 2 -8γ(2β + 9) + 72) + (24γ 2 + 8γ(2β -9) + 24)z ,
where the coefficients of a * ij (z) are the (i, j)-entries of the matrices A(-2), A(-1), A(0), A(1), respectively. Since H A satisfies the spectral condition of order 3 we can construct the mask B supported on

[-1, 1] such that   z -1 -1 -1 -1 2 0 z -1 -1 -1 0 0 1   A * (z) = 1 4 B * (z)   z -2 -1 -1 -1 2 0 z -2 -1 -1 0 0 1   .
* 00 (z) = 1 96 (192αβ + 96)z -1 + (96β 2 -384αβ -96βγ -288β + 192) + (192αβ -288β + 96βγ + 96β 2 + 96)z , b * 01 (z) = 1 96 (288α -96αβ -2γ(24α + 3))z -1 + (96β -192αβ -48β 2 + 24γ 2 + 2γ(20β -30) -48) + (192β -288α + 288αβ -2γ(20β -24α + 39) -48β 2 + 24γ 2 -48)z , b * 02 (z) = 1 96 ((24α + 3)γ + 16αβ -144α -15)z -1 + ((30 -4β)γ -12γ 2 + 8β 2 + 160αβ) + ((4β -24α + 39)γ -12γ 2 + 144α -48β -176αβ + 8β 2 + 15)z , b * 10 (z) = 1 96 (-96β(β -3))z -1 + (-192βγ) + (96β(β + 2γ -3))z , b * 11 (z) = 1 96 ((8β -12)γ + 384αβ -96β + 48β 2 + 48)z -1 + (48γ 2 + (80β -120)γ -96β -768αβ + 96) + (48γ 2 -(88β + 156)γ + 192β + 384αβ -48β 2 + 48)z , b * 12 (z) = 1 96 ((6 -4β)γ -8β 2 -192αβ -18)z -1 + (-24γ 2 + (60 -8β)γ + 48β + 384αβ -24) + ((12β + 78)γ -24γ 2 + 8β 2 -192αβ -48β -6)z , b * 20 (z) = 1 96 (192βγ)z -1 + (-384βγ) + (192βγ)z , b * 21 (z) = 1 96 (48γ(-2β -γ + 3))z -1 + (192βγ) + (48γ(-2β + γ -3))z , b * 22 (z) = 1 96 (24γ 2 + (16β -72)γ + 24)z -1 + (48 -32βγ) + (-24γ 2 + (16β + 72)γ + 24)z .
To see weather the Hermite subdivision scheme H A is HC When α = -5 32 , γ = 3 2 , β = 2, we can show that ∃n < 10 : S n E ∞ < 1, i.e. S E is contractive, namely S C is C 0 and H A is HC 3 . Differently, for the same choice of the free parameters the associated interpolatory Hermite subdivision scheme H A is only HC 2 (see Figures 3 and4 for a comparison of the basic matrix limit functions of the two schemes).

Conclusions

In this paper we have presented a novel constructive approach for deriving new dual approximating Hermite subdivision schemes from known Hermite interpolatory schemes. The strategy, called de Rham transform, at each recursion step consists in the double application of an interpolatory Hermite subdivision operator, followed by a decimation step selecting the odd entries only of the obtained vector sequence. Applying the proposed construction to Merrien's interpolatory Hermite schemes in [START_REF] Merrien | A family of Hermite interpolants by bisection algorithms[END_REF][START_REF] Merrien | Interpolants dHermite C 2 obtenus par subdivision, M2AN Math[END_REF], two new dual de Rham-type Hermite subdivision schemes are obtained. Their smoothness is analyzed with the help of new theoretical results showing that, with respect to the starting schemes, the regularity is increased by one as well as the support width of the associated basic matrix limit function.

( 1 )

 1 n (t n (α)), and so on up to the last one describing ψ

  since the presence of the matrices D n is by nature, we can further classify a Hermite subdivision scheme by means of the following definition.Definition 2 A Hermite subdivision scheme is named Inherently Stationary (I.S.) in case the masks A n := {A n (α), α ∈ Z}, n ≥ 0, reduce to the same mask A = A n for all n ≥ 0. It means that the subdivision step in (4) becomes

1 Figure 2 :

 12 Figure 2: Basic matrix limit function of the non-interpolatory dual Hermite subdivision scheme H A with µ = -1 2 .

  Like in the previous example, we compute from B the difference mask B whose non-zero entries are B(-1), B(0), B(1), and the associated symbol B * (z) is given by b

3 z - 1 -

 31 we use Theorem 3 and check if S B is C 1 , which is equivalent to the fact that its divided difference scheme S C , with C = 2 B, is C 0 . Since the joint 1-eigenspace of C e and C o is E C = [1, 3, 6] T , we apply the similarity transformC(α) = S -1 C(α) S for α = -1, so that E C = [1, 0, 0] T . To show that S C is C 0 , we construct the difference mask E via   -6(8α + 1)γ -96αβ)z -1 + (24γ 2 + (48α + 40β -54)γ + 96β -288α -96αβ -48β 2 -48) + ((48α -80β -18)γ + 96β -288α + 480αβ)z + ((40β -48α + 78)γ -24γ 2 + 288α -192β -288αβ + 48β 2 + 48)z 2 , e * 02 (z) = 1 48 ((24α + 3)γ + 16αβ -144α -15)z -1 + ((27 -4β -24α)γ -12γ 2 + 8β 2 + 144αβ + 144α + 15) + ((8β -24α + 9)γ + 144α -48β -336αβ + 15)z + (12γ 2 + (24α -4β -39)γ + 48β -144α + 176αβ -8β 2 -15)z 2 , e * 10 (z) = 1 48 18z 2 , e * 11 (z) = 1 48 ((144α + 8β + 6)γ + 672αβ -96β -864α + 48β 2 + 48) + ((60 -40β)γ -24γ 2 + 144β 2 -192αβ -384β + 240)z + ((32β -144α + 78)γ -24γ 2 + 864α -384β -480αβ + 96β 2 + 192)z 2 , e * 12 (z) = 1 48 (432α -(72α + 4β + 3)γ -8β 2 -240αβ + 27) + (12γ 2 + (4β -30)γ + 48β -96αβ -24β 2 -24)z + (12γ 2 + (72α -39)γ + 96β -432α + 336αβ -16β 2 -51)z 2 , e * 20 (z) = 1 48 108z 2 , e * 21 (z) = 1 48 (-48γ 2 + (288α -96β + 180)γ -1728α + 576αβ) + ((360 -48β)γ -144γ 2 + 1152αβ -576β + 288β 2 + 288)z + ((144β -288α + 324)γ -96γ 2 + 1728α -1152β -1728αβ + 288β 2 + 288)z 2 , e * 22 (z) = 1 48 (24γ 2 + (16β -144α-90)γ + 864α -96αβ + 114) + (72γ 2 + (-8β -180)γ -48β 2 -960αβ + 48)z + (48γ 2 + (144α -8β -162)γ + 288β -864α + 1056αβ -48β 2 -66)z 2 .

Figure 3 :Figure 4 :

 34 Figure 3: Basic matrix limit function of the interpolatory Hermite subdivision scheme H A with α = -5 32 , γ = 3 2 , β = 2.

Acknowledgements

This work was partially supported by Italian funds from INdAM-GNCS. Special thanks go to the anonymous referees for their useful comments.


Konstantin Avrachenkov
email: k.avrachenkov@sophia.inria.fr

Bruno Ribeiro
email: ribeiro@cs.purdue.edu

Jithin K Sreedharan
email: jithin.sreedharan@inria.fr

Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls

Keywords: Bayesian inference, Random walk on graphs, Social network analysis, Graph sampling

Online social networks (OSN) contain extensive amount of information about the underlying society that is yet to be explored. One of the most feasible technique to fetch information from OSN, crawling through Application Programming Interface (API) requests, poses serious concerns over the the guarantees of the estimates. In this work, we focus on making reliable statistical inference with limited API crawls. Based on regenerative properties of the random walks, we propose an unbiased estimator for the aggregated sum of functions over edges and proved the connection between variance of the estimator and spectral gap. In order to facilitate Bayesian inference on the true value of the estimator, we derive the approximate posterior distribution of the estimate. Later the proposed ideas are validated with numerical experiments on inference problems in real-world networks.

Inférence bayésienne de statistiques des réseaux sociaux par les marches aléatoires avec complexité légère

Résumé : Les réseaux sociaux en ligne contiennent grande quantité d'informations à propos de la société qui peut être significativement exploré. Une des techniques, parmi les plus faisable de récupérer des informations, est d'explorer le réseau à l'aide de Application Programming Interface (API). Dans ce travail, nous nous concentrons sur l'inférence statistique fiable avec un taux limité des appels vers l'API. Basé sur les propriétés régénératrices des marches aléatoires, nous proposons un estimateur sans bias pour la somme agrégée des fonctions sur des arêtes. Nous montrons la connexion entre la variance de l'estimateur et l'écart spectral. Afin de faciliter l'inférence bayésienne sur la vraie valeur de l'estimateur, nous dérivons la distribution postérieure asymptotique de l'estimation. Finalement, les idées proposées sont validés par des expériences numériques sur les problèmes d'inférence dans les réseaux sociaux réels Mots-clés : Inférence bayésienne, marche aléatoire sur les graphes, analyse de réseau social.

Introduction

What is the fraction of male-female connections against that of female-female connections in a given Online Social Network (OSN)? Is the OSN assortative or disassortative? Edge, triangle, and node statistics of OSNs find applications in computational social science (see e.g. [START_REF] Ottoni | Ladies first: Analyzing gender roles and behaviors in Pinterest[END_REF]), epidemiology [START_REF] Pastor | Epidemic spreading in scale-free networks[END_REF], and computer science [START_REF] Benevenuto | Characterizing user behavior in online social networks[END_REF][START_REF] Gjoka | 2.5 k-graphs: from sampling to generation[END_REF][START_REF] Putzke | Cross-cultural gender differences in the adoption and usage of social media platforms-an exploratory study of Last[END_REF]. Computing these statistics is a key capability in large-scale social network analysis and machine learning applications. But because data collection in the wild is often limited to partial OSN crawls through Application Programming Interface (API) requests, observational studies of OSNs -for research purposes or market analysis -depend in great part on our ability to compute network statistics with incomplete data. Case in point, most datasets available to researchers in widely popular public repositories are partial OSN crawls 1 . Unfortunately, these incomplete datasets have unknown biases and no statistical guarantees regarding the accuracy of their statistics. To date, the best methods for crawling networks ([3, 10, 28]) show good real-world performance but only provide statistical guarantees asymptotically (i.e., when the entire OSN network is collected). This work addresses the fundamental problem of obtaining unbiased and reliable node, edge, and triangle statistics of OSNs via partial crawling. To the best of our knowledge our method is the first to provide a practical solution to the problem of computing OSN statistics with strong theoretical guarantees from a partial network crawl. More specifically, we (a) provide a provable finite-sample unbiased estimate of network statistics (and their spectral-gap derived variance) and (b) provide the asymptotic posterior of our estimates that performs remarkably well all tested real-world scenarios.

More precisely, let G = (V, E) be an undirected labeled network -not necessarily connected -where V is the set of vertices and E ⊆ V × V is the set of edges. Both edges and nodes can have labels. Network G is unknown to us except for n > 0 arbitrary initial seed nodes in I n ⊆ V . Nodes in I n must span all the different connected components of G. From the seed nodes we crawl the network starting from I n and obtain a set of crawled edges D m (I n ), where m > 0 is a parameter that regulates the number of website API requests. With the crawled edges D m (I n ) we seek an unbiased estimate of

µ(G) = (u,v)∈E f (u, v) . (1)
Note that functions of the form eq. ( 1) are general enough to compute node statistics

µ node (G) = (u,v)∈E g(v)/d v ,
where d u is the degree of node u ∈ V , and statistics of triangles such as the local clustering coefficient of G first provided by [START_REF] Ribeiro | Estimating and sampling graphs with multidimensional random walks[END_REF] µ

(G) = 1 |V | (u,v)∈E 1(d v > 2) d v a∈Nv b∈Nv,b =a 1((v, a) ∈ E ∩ (v, b) ∈ E ∩ (a, b) ∈ E) dv 2
, where the expression inside the sum is zero when d v < 2 and N v are the neighbors of v ∈ V in G. Our task is to find estimates of general functions of the form µ(G) in eq. ( 1).

Contributions

In our work we provide a partial crawling strategy using random walk tours whose posterior

P [µ(G)|D m (I n )]
is shown to have an unbiased maximum a posteriori estimate (MAP) μMAP (D m (I n )) regardless of the number of nodes in the seed set n > 0 and regardless of the value of m > 0, i.e.,

E[μ MAP (D m (I n ))] = µ(G), ∀n, m > 0.
Note that we guarantee that our MAP estimate is unbiased in the finite-sample regime unlike previous asymptotic methods [START_REF] Avrachenkov | Improving random walk estimation accuracy with uniform restarts[END_REF][START_REF] Gjoka | Practical recommendations on crawling online social networks[END_REF][START_REF] Lee | Beyond random walk and Metropolis-Hastings samplers: why you should not backtrack for unbiased graph sampling[END_REF][START_REF] Ribeiro | Estimating and sampling graphs with multidimensional random walks[END_REF]29]. Moreover, we provide the posterior

P [µ(G)|D m (I n )]
for the large m regime and prove its convergence in distribution showing its convergence rate. In our experiments we note that the posterior is remarkably accurate using a variety of networks large and small. We also provide upper and lower bounds for

P [µ(G)|D m (I n )].

Related Work

The works of [START_REF] Massoulié | Peer counting and sampling in overlay networks: random walk methods[END_REF] and [START_REF] Cooper | Fast low-cost estimation of network properties using random walks[END_REF] are the ones closest to ours. [START_REF] Massoulié | Peer counting and sampling in overlay networks: random walk methods[END_REF] estimates the size of a network based on the return times of random walk tours. [START_REF] Cooper | Fast low-cost estimation of network properties using random walks[END_REF] estimates number of triangles, network size, and subgraph counts from weighted random walk tours using results of [START_REF] Aldous | Reversible Markov chains and random walks on graphs[END_REF]. The previous works on non-asymptotic inference of network statistics from incomplete network crawls [START_REF] Goel | RespondentâĂŘdriven sampling as Markov chain Monte Carlo[END_REF][START_REF] Koskinen | Analysing exponential random graph (p-star) models with missing data using Bayesian data augmentation[END_REF][START_REF] Koskinen | Bayesian analysis for partially observed network data, missing ties, attributes and actors[END_REF][START_REF] Handcock | Modeling social networks from sampled data[END_REF][START_REF] Heckathorn | Respondent-driven sampling: A new approach to the study of hidden populations[END_REF][START_REF] Ligo | A controlled sensing approach to graph classification[END_REF]30] need to fit the partial observed data to a probabilistic graph model such as ERGMs (exponential family of random graphs models). Our work advances the state-of-the-art in estimating network statistics from partial crawls because: (a) we estimate statistics of arbitrary edge functions without assumptions about the graph model or the underlying graph; (b) we do not need to bias the random walk with weights; this is particularly useful when estimating multiple statistics reusing the same observations; (c) we derive upper and lower bounds on the variance of estimator, which both show the connection with the spectral gap; and, finally, (d) we compute a posterior over our estimates to give practitioners a way to access the confidence in the estimates without relying on unobtainable quantities like the spectral gap and without assuming a probabilistic graph model. The remainder of the paper is organized as follows. In Section 2 we introduce our main theorems and supporting lemmas and proofs. In Section 3 we introduce artificial illustrative examples to aid understanding our method. In Section 4 we introduce our results using simulations over real-world networks. Finally, in Section 5 we present our conclusions.

Network Estimation from Partial Crawls

In this section we present our main results. The outline of this section is as follows. Section 2.1 introduces key concepts and defines the notation used throughout this manuscript. Section 2.2 introduces our main results in the form of two theorems: Theorem 1 presents an unbiased estimator of any function over edges of an undirected graph using random walk tours. Our random walk tours are shorter than the "regular random walk tours" because the "node" that they start from is an amalgamation of a multitude of nodes in the graph. Here, we briefly explains the approximate posterior of the estimator in Theorem 1. Section 2.3 proves Theorem 1, introducing important upper and lower bonds of the estimator variance in Section 2.4.1 and showing the effect of the spectral gap. Finally, Section 2.4 derives the approximate Bayesian posterior (3) also using the bounds obtained in Section 2.4.1.

Inria

Preliminaries

Let G = (V, E) be an unknown undirected graph. Our goal is to find an unbiased estimate of µ(G) in eq. ( 1) and its posterior by crawling a small fraction of G. We are given a set of n > 0 initial arbitrary nodes denoted I n ⊂ V . If G has disconnected components I n must span all the different connected components of G.

Our network crawler is a classical random walk over the following augmented multigraph G = (V , E ). A multigraph is a graph that can have multiple edges between two nodes. In G we aggregate all nodes of I n into a single node, denoted hereafter S n , the super-node. Thus,

V = {V \I n } ∪ {S n }. The edges of G are E = E\ {E ∩ {I n × V }} ∪ {(S n , v) : ∀(u, v) ∈ E, s.t. u ∈ I n and v ∈ V \I n }, i.e.
, E contains all the edges in E including the edges from the nodes in I n to other nodes, and I n is merged into the super-node S n . Note that G is necessarily connected as I n spans all the connected components of G.

A random walk on G has transition probability from node u to an adjacent node v, p uv := P u,v with α u,v /d u , where d u is the degree of u and α u,v is the number of edges between u ∈ V and v ∈ V . We note that the theory presented in the paper can be extended to more sophisticated random walks as well. Let π i be the stationary distribution at node i in the random walk on G .

A random walk tour is defined as the sequence of nodes

X (k) 1 , . . . , X (k)
ξ k visited by the random walk during successive k-th and k + 1-st visits to the super-node S n . Here {ξ k } k≥1 denote the successive return times to S n . Tours have a key property: from the renewal theorem tours are independent since the returning times act as renewal epochs. Moreover, let Y 1 , Y 2 , . . . , Y n be a random walk on G in steady state.

Note that the random walk on G is equivalent to a random walk on G where all the nodes in I n are treated as one single node.

The function f is redefined on G as follows: for

(u, v) ∈ E , f (u, v)) remains same when u / ∈ S n and v / ∈ S n . But when u ∈ S n or v ∈ S n , f (u, v) is redefined as zero.

Super-node Motivation

The introduction of super-node is primary motivated by the following three reasons:

• Tackling disconnected or low-conductance graphs: When the graph is not strongly connected or has many connected components, forming a super-node with representatives from each of the components make the modified graph connected and suitable for applying random walk theory. Even when the graph is connected, it might not be well-knit, i.e., it has low conductance. Since the conductance is closely related to mixing time of Markov chains, such graph will prolong the mixing of random walks. But with proper choice of super-node, we can reduce the mixing time and, as we show, improve the estimation accuracy. This idea is illustrated with a Dumbell graph example in Section 3.

• Faster Estimate with Shorter Tours: The expected value of the k-th tour length E[ξ k ] = 1/π Sn is inversely proportional to the degree of the super-node d Sn . Hence, by forming a massive-degree super-node we can significantly shorten the average tour length.

Main Results

In what follows we present our main results. Theorem 1 proposes an unbiased estimator of edge characteristics µ(G) via random walk tours. Then we present the approximate posterior distribution of the unbiased estimator presented in Theorem 1.

Theorem 1. Let G be an unknown undirected graph where n > 0 initial arbitrary set of nodes is known I n ⊆ V which span all the different connected components of G. Consider a random walk on the augmented multigraph G described in Section 2.1 starting at super-node S n . Let (X

t ) ξ k t=1 be the k-th random walk tour until the walk first returns to S n and let

D m (S n ) denote the collection of all nodes in m ≥ 1 such tours, D m (S n ) = (X (k) t ) ξ k t=1 m k=1 . Then, μ(D m (S n )) = Estimate from crawls d Sn 2m m k=1 ξ k t=2 f (X (k) t-1 , X (k) t ) + Edges between initial nodes at original G (u,v)∈E s.t. u∈In or v∈In f (u, v) (2
)

is an unbiased estimate of µ(G), i.e., E[μ(D m (S n ))] = µ(G). Moreover the estimator is strongly consistent, i.e., μ(D m (S n )) → µ(G) a.s. for m → ∞.
Theorem 1 provides an unbiased estimate of network statistics from random walk tours. The length of tour k is short if it starts at a massive super-node as the expected tour length is inversely proportional to the degree of the super-node, E[ξ k ] ∝ 1/d Sn . This provides a practical way to compute unbiased estimates of node, edge, and triangle statistics using μ(D m (S n )) (eq. ( 2)) while observing only a small fraction of the original graph. Because random walk tours can have arbitrary lengths, we show in Lemma 2, Section 2.4, that there are upper and lower bounds on the variance of μ(D m (S n )). For a bounded function f , the upper bounds are shown to be always finite.

In what follows we show the approximate posterior of the estimator in Theorem 1. In Section 4 we shall see that the approximate posterior matches very well the empirical posterior using simulations over real-world networks while crawling < 10% of the nodes in the network.

Let µ(G ) be the true value µ(G) outside the subgraph formed by the nodes that were merged into the super-node.

Bayesian approximation of the posterior of µ(G)

Let

Fh = d Sn 2 √ m h √ m k=((h-1) √ m +1) ξ h t=2 f (X (k) t-1 , X (k) t ) + (u,v)∈E s.t. u∈In or v∈In f (u, v).
In the scenario of Theorem 1 for m ≥ 2 tours and assuming priors µ(G)

|σ 2 ∼ Normal(µ 0 , σ 2 /m 0 ), σ 2 ∼ Inverse-gamma(ν 0 /2, ν 0 σ 2 0 /2) (σ 2 is the variance of F1 ), then the marginal posterior density of µ(G) as m → ∞ converges in distribution to a non-standardized t-distribution φ(x|ν, µ, σ) = Γ ( ν+1 2 ) Γ ( ν 2 ) σ √ πν 1 + (x -µ) 2 σ 2 ν -ν+1 2 (3)
with degrees of freedom parameter

ν = ν 0 + √ m , location parameter µ = m 0 µ 0 + √ m μ(D m (S n )) m 0 + √ m ,
Inria and scale parameter

σ = ν 0 σ 2 0 + √ m k=1 ( Fk -μ(D m (S n ))) 2 + m0 √ m (μ(Dm(Sn))-µ0) 2 m0+ √ m (ν 0 + √ m )(m 0 + √ m ) .
Remark 1. Note that approximation in (3) is a Bayesian approach and Theorem 1 is the frequentist counterpart. In fact, the motivation to form the Bayesian approach comes from the frequentist estimator ( Fh samples). From the approximate posterior, the Bayesian MAP estimator for sufficiently large values of m is

μMAP = arg max x φ(x|v, µ, σ) = µ.
Thus when m 0 = 0, the Bayesian estimator μMAP is essentially the first term in the frequentist estimator μ(D m (S n )) (second term is calculated a priori), and hence both the estimators are same. In this paper we make use of the posterior distribution from the Bayesian approach to get the degrees of belief along with the common estimator from both the approaches.

The above remark shows that the approximate posterior in (3) provides a way to access the confidence in the estimate μ(D m (S n )). The Normal prior for the average gives the largest variance given a given mean. The inverse-gamma is a non-informative conjugate prior if the variance of the estimator is not too small [START_REF] Gelman | Prior distributions for variance parameters in hierarchical models[END_REF], which is generally the case in our application. Other choices of prior, such as uniform, are also possible yielding different posteriors without closed-form solutions [START_REF] Gelman | Prior distributions for variance parameters in hierarchical models[END_REF]. The posterior is conservative as μ(D m (S n )) is calculated from m tours while the posterior considers only √ m tours. Being conservative, however, is advised as the posterior is for large values of m and the conservative estimate better protects us from finitesample anomalies and perform very well in practice as we see in Section 4. In what follows we provide the proofs of our main results.

Proof of Theorem 1

The outline of this proof is as follows. In Lemma 1 we show that the estimate of µ(G) from each tour is unbiased.

Lemma 1. Let X (k) 1 , . . . , X (k)
ξ k be the nodes traversed by the k-th random walk tour on G , k ≥ 1 starting at super-node S n . Then the following holds, ∀k,

E ξ k t=2 f (X (k) t-1 , X (k) t ) = 2 d Sn µ(G ). (4)
Proof. The random walk starts from the super-node S n , thus

E ξ k t=2 f (X (k) t-1 , X (k) t ) = (u,v)∈E E No. of times Markov chain crosses (u, v) in the tour f (u, v) (5)

RR n°8793

Consider a renewal reward process with inter-renewal time distributed as ξ k , k ≥ 1 and reward as the number of times Markov chain crosses (u, v). From renewal reward theorem, {Asymptotic frequency of transitions from u to v}

= E No. of times Markov chain crosses (u, v) in the tour f (u, v) E[ξ k ]
Here the left-hand side is essentially 2π u p uv . Now ( 5) becomes

E ξ k t=2 f (X (k) t-1 , X (k) t ) = (u,v)∈E f (u, v) 2π u p uv E[ξ k ] = 2 (u,v)∈E f (u, v) d u j d j 1 d u j d j d Sn = 2 d Sn (u,v)∈E f (u, v),
which concludes our proof.

In what follows we prove Theorem 1 using Lemma 1.

Theorem 1. By Lemma 1 the estimator

W k = ξ k -1 t=2 f (X (k) t-1 , X (k)
t ) is an unbiased estimate of µ(G ). By the linearity of expectation the average estimator W (m) = m -1 m k=1 W k is also unbiased. Finally for the estimator

μ(D m (S n )) = d Sn 2m W (m) + (u,v)∈E s.t. u,v∈In f (u, v)
has average

E[μ(D m (S n ))] = (u,v)∈E s.t. u ∈In or v ∈In f (u, v) + (u,v)∈E s.t. u,v∈In f (u, v) = µ(G).
Furthermore, by strong law of large numbers with

E[W k ] < ∞, μ(D m (S n )) → µ(G) a.s.
for m → ∞. This completes our proof.

Derivation of the approximate posterior

The derivation of (3) relies first on showing that μ(D m (S n )) has finite first and second moments. We go further and in Lemma 2 we introduce upper and lower bounds on the variance of

μ(D m (S n )). By Theorem 1 the first moment of μ(D m (S n )) is finite as E[μ(D m (S n ))] = µ(G).
To show that the second moment is finite we prove that the estimate

W k = ξ k -1 t=2 f (X (k) t-1 , X (k) t ), k ≥ 1, whose variance is m • Var(μ(D m (S n ))
), has finite second moment. The results in Lemma 2 are of interest on their own because they establish a connection between the estimator variance and the spectral gap. Let the left and right eigenvectors of P be v j and u j respectively.

d tot := v∈V d v . Define f, g π = (u,v)∈E πuv f (u, v)g(u, v),
with πuv = π u p uv , and matrix P * with (j, i)th element as p * ji = p ji f (j, i). Also let f be the vector with f (j) = i∈V p * ji . Lemma 2. The following holds (i). Assuming the function f is bounded, max

(i,j)∈E f (i, j) ≤ B < ∞, B > 0 and for tour k ≥ 1, var ξ k t=2 f (X (k) t-1 , X (k) t ) ≤ 1 d 2 Sn 2d 2 tot B 2 i≥2 w 2 Sni (1 -λ i ) -4µ 2 (G Sn ) - 1 d Sn B 2 d tot + B 2 < B 2 2d 2 tot d 2 Sn δ + 1 .
Moreover,

E ξ k t=2 f (X (k) t-1 , X (k) t )
l < ∞ ∀l ≥ 0.

(ii).

var Sn ξ k t=2 f (X (k) t-1 , X (k) t )) ≥ 2 d tot d Sn r i=2 λ i 1 -λ i f, v i π (u i f ) + 1 d Sn (u,v)∈E f (u, v) 2 + 1 d tot d Sn (u,v)∈E f (u, v) 2 2 + 1 d tot d Sn u∈V d u u∼v f (u, v) 2 - 4 d 2 Sn (u,v)∈E f (u, v) 2 - 8 d tot (u,v)∈E f (u, v) 2 i≥2 w 2 Sni (1 -λ i ) - 4 d tot d Sn (u,v)∈E f (u, v) 2 . (6)
Proof. (i). The variance of the estimator at tour k ≥ 1 starting from node S n is var Sn

ξ k t=2 f (X (k) t-1 , X (k) t )) ≤ B 2 E[(ξ k -1) 2 ] -E ξ k t=2 f (X (k) t-1 , X (k) t )) 2 . ( 7
)
It is known from [1, Chapter 2 and 3] that

E[ξ 2 k ] = 2 i≥2 w 2 Sni (1 -λ i ) -1 + 1 π 2

Sn

.

RR n°8793

Using Theorem 1 eq. ( 7) can be written as

var ξ k t=2 f (X (k) t-1 , X (k) t )) ≤ 1 d 2 Sn 2d 2 tot B 2 ( i≥2 w 2 Snm (1 -λ i ) -1 ) -4µ 2 (G ) - 1 d Sn B 2 d tot + B 2 .
The latter can be upper-bounded by B 2 (2d 2 tot /(d 2 i δ) + 1). For the second part, we have

E ξ k t=2 f (X (k) t-1 , X (k) t ) l ≤ B l E[(ξ k -1) l )] ≤ C(E[(ξ k ) l ] + 1),
for a constant C > 0 using c r inequality. From [START_REF] Sean | Markov chains and stochastic stability[END_REF], it is known that there exists an a > 0, such that E[exp(a ξ k )] < ∞, and this implies that E[(ξ k ) l ] < ∞ for all l ≥ 0. This proves the theorem.

(ii). We denote

E π f for E π [f (Y 1 , Y 2 )
] and Normal(a, b) indicates Gaussian distribution with mean a and variance b. With the trivial extension of the central limit theorem of Markov chains [START_REF] Kipnis | Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions[END_REF] of node functions to edge functions, we have for the ergodic estimator fn

= n -1 n t=2 f (Y t-1 , Y t ), √ n( fn -E π f ) d -→ Normal(0, σ 2 a ), (8)
where

σ 2 a = Var(f (Y 1 , Y 2 )) + 2 n-1 l=2 (n -1) -l n Cov(f (Y 0 , Y 1 ), f (Y l-1 , Y l )) < ∞
We derive σ 2 a in Lemma 3. Note that σ 2 a is also the asymptotic variance of the ergodic estimator of edge functions.

Consider a renewal reward process at its k-th renewal, k ≥ 1, with inter-renewal time ξ k and

reward W k = ξ k t=2 f (X (k) t-1 , X (k)
t ). Let W (n) be the average cumulative reward gained up to m-th renewal, i.e., W (m) = m -1 m k=1 W k . From the central limit theorem for the renewal reward process [31, Theorem 2.2.5] after n total number of steps, with

l n = argmax k k j=1 1(ξ j ≤ n), yields √ n( W (l n ) -E π f ) d -→ Normal(0, σ 2 b ), (9)
with

σ 2 b = ν 2 E[ξ k ]
and

ν 2 = E[(W k -ξ k E π f ) 2 ] = E i W k -ξ k E[W k ] E[ξ k ] 2 = var Sn (W k ) + (E[W k ]) 2 + E[W k ] E[ξ k ] 2 E[(ξ k ) 2 ] -2 E[W k ] E[ξ k ] E[W k ξ k ].
In fact it can be shown that (see [24, Proof of Theorem 17.2.2])

| √ n( fn -E π f ) - √ n( W (l n ) -E π f )| → 0 a.s. . Therefore σ 2 a = σ 2 b .
Combing this result with Lemma 3 shown in the appendix we get [START_REF] Cooper | Fast low-cost estimation of network properties using random walks[END_REF].

Inria

We are now ready to derive the approximation [START_REF] Avrachenkov | Improving random walk estimation accuracy with uniform restarts[END_REF].

Proof. Let m = √ m . Given Fh = d Sn 2 √ m h √ m k=((h-1) √ m +1) ξ h t=2 f (X (k) t-1 , X (k) t ) .
and { Fh } m h=1 and because the tours are i.i.d. μ(D √ m (S n )) the marginal posterior density of µ is

P [µ|{ Fh } m h=1 ] = ∞ 0 P [µ|σ 2 , { Fh } m h=1 ]P [σ 2 |{ Fh } m h=1 ]dσ 2 .
For now assume that { Fh } m h=1 are i.i.d. normally distributed random variables, and let

σm = m h=1 ( Fh -μ(D m (S n ))) 2 , then [15, Proposition C.4] µ|σ 2 , { Fh } m h=1 ∼ Normal m 0 µ 0 + m h=1 Fh m0 + m , σ 2 m 0 + m , σ 2 |{ Fh } m h=1 ∼ Inverse-Gamma ν 0 + m 2 , ν 0 σ 2 0 + σm + m0m m0+m (µ 0 -μ(D m (S n ))) 2 2
are the posteriors of parameters µ and σ 2 , respectively. The non-standardized t-distribution can be seen as a mixture of normal distributions with equal mean and random variance inversegamma distributed [START_REF] Jackman | Bayesian analysis for the social sciences[END_REF]Proposition C.6]. Thus, if { Fh } m h=1 are i.i.d. normally distributed then the posterior of μ(D √ m (S n )) is a non-standardized t-distributed with parameters

t µ = m 0 µ 0 + m h=1 Fh m0 + m , σ 2 = ν 0 σ 2 0 + √ m k=1 ( Fk -μ(D m (S n ))) 2 + m0 √ m (μ(Dm(Sn))-µ0) 2 m0+ √ m (ν 0 + √ m )(m 0 + √ m ) , ν = ν 0 + √ m . ( 10
)
Left to show is that { Fh } m h=1 are converge in distribution to i.i.d. normal random variables as m → ∞. As the spectral gap of G Sn is greater than zero,

|λ 1 -λ 2 | > 0, Lemma 2 showns that for W k = ξ k -1 t=2 f (X (k) t-1 , X (k) t ) then σ 2 W = Var(W k ) < ∞ , ∀k .
From the renewal theorem we know that {W k } m k=1 are i.i.d. random variables and thus any subset of these variables is also i.i.d.. By construction F1 , . . . , Fm are also i.i.d. with mean µ(G Sn ) and finite variance 0 < σ 2 m < ∞. Applying the Lindeberg-Lévy central limit theorem [START_REF] Cramér | Mathematical methods of statistics[END_REF]Section 17.4

] yields √ m ( Fh -µ(G )) d → Normal(0, σ 2 W ), ∀h ,
where var( Fh ) = σ2 m . Thus, in the limit as m → ∞ and m → ∞ (recall that m = √ m ), the variables { Fh } m h=1 are i.i.d. normally distributed with

Fh ∼ Normal(µ(G ), σ 2 W /m ) , ∀h ,
and

(u,v)∈E s.t. u∈In or v∈In f (u, v)
is constant and known, which concludes our proof.

Illustrative example

Here we consider the classical example of low-conductance graph: the dumbbell graph. Here we Illustrate how the super-node solves the variance problem for random walk tours on graphs. A dumbbell graph consists of two complete graphs K n on n vertices connected by a single edge. The spectral gap δ = (1 -λ 2 ), where λ 2 is the second largest absolute eigenvalue of P, is roughly

δ = O(1/n 2 ).
It is known that the variance of the return time ξ k of tour k > 0 is related to δ as [START_REF] Aldous | Reversible Markov chains and random walks on graphs[END_REF] Var

(ξ k ) ≤ 2 δ π 2 Sn + 1 π Sn .
Drawing nodes from both components to create the super-node, the new graph G with the super-node will be more connected and hence δ improves, and so does the variance. Another way to view the impact of forming the super-node is that of the cover time of a random walk on dumbell graph. Without the super-node the cover time is Θ(n 2 ). If k = O(log n) random walks run in parallel with some conditions on distributing them, the covering time can be reduced to O(n) [START_REF] Alon | Many random walks are faster than one[END_REF]. In this view the super-node tours acts as multiple parallel random walks that quickly cover more of graph with less effort.

Experiments on Real-world Networks

In this section we demonstrate the effectiveness of the theory developed above with the experiments on real data sets of various social networks 2 . We assume the contribution from super-node to the true value is known a priori and hence we look for µ(G Sn ) in the experiments. In the case that the edges of the super-node are unknown, the estimation problem is easier and can be taken care separately. One option is to start multiple random walks in the graph and form connected subgraphs. Later, in order to estimate the bias created by this subgraph, do some random walk tours from the largest degree node in each of these sub graph and use the idea in Theorem 1.

In the figures we display both approximate posterior and empirical posterior generated from Fh . For the approximate posterior, we have used the following parameters m 0 = 0, ν 0 = 0, µ 0 = 0, σ 0 = 1. The green line in the plots shows the actual value µ(G Sn ).

In the numerical experiments, the super-node is formed in one of following ways: a) uniformly sample k nodes from the network without replacement; b) run random walk crawl starting from any node and cover around 10% of the graph, and form the super-node with the k largest degree nodes. In both the ways, if the network is disconnected, super-node should be initially created with at least one node from each of the connected component.

μ(D m (S n ))

Friendster

First we study a network of moderate size, a connected subgraph of Friendster network with 64,600 nodes and 1,246,479 edges (data publicly available at the SNAP repository [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF]). Friendster is an online social networking website where nodes are individuals and edges indicate friendship. Here, we consider two types of functions:

1. f 1 = d Xt .d Xt+1 2. f 2 = 1 if d Xt + d Xt+1 > 50 0 otherwise
These functions reflect assortative nature of the network. The super-node is formed from 10,000 uniformly sampled nodes just as a way to test our method. Figures 1 and2 display the results for functions f 1 and f 2 , respectively. A good match between the approximate and empirical posteriors can be observed from the figures. Moreover the true value µ(G Sn ) is also fitting well with the plots. The percentage of graph crawled is 24.44% in terms of edges and this drops to 7.43% if we use random walk based super-node formation.

Dogster network

The aim of this example is to check whether there is any affinity for making connections between the owners of same breed dogs [START_REF]Dogster and Catster friendships network dataset KONECT[END_REF]. In Figure 3, two cases are plotted. Function f 1 counts the number of connections with different breeds as pals and function f 2 counts connections between same breeds. The supernode is formed by 10,000 nodes which are uniformly selected at random. The percentage of the graph crawled in terms of edges is 5.02% and in terms of nodes is 37.17%. While using the random walk based super-node formation, the graph crawled drops to 2.72% (in terms of edges) and 14.86% (in terms of nodes) with the same super-node size. But these values can be reduced much further if we allow a bit less precision in the match between approximate distribution and histogram.

In order to better understand the correlation in forming edges, we now consider the configuration model. The configuration model is formed as follows: all the edges in the graph is cut and what is left is half edges for each node, and the number of half edges is the degree of the node. Now these half edges are paired uniformly. Such a configuration will create a graph whose edges are formed without any correlation between the end-nodes. We run our estimator on the configuration model and plot the histogram and distribution as we did for the original graph. Figure 4 compare function f 2 for the configuration model and original graph. The figure shows that in the correlated case (original graph), the affinity to form connection between same breed owners is around 7.5 times more than that in the uncorrelated case. Figure 5 shows similar figure in case of f 1 . It is important to note that one can create a configuration network model from the crawl and the knowledge of the complete network is not necessary. In the figures, we show the estimated true value from the configuration model created with the subgraph sampled by the estimator proposed in this paper (blue line in Figure 4 and red line in Figure 5). The estimator is simply µ

C (D(S n )) = (u,v)∈Ec f (u, v)|E|/|E c |
, where E c is the edge set in the configuration model subgraph. The number of edges |E| can be calculated from the techniques in [START_REF] Cooper | Fast low-cost estimation of network properties using random walks[END_REF]. Interestingly, this estimated value matches with the true value of the configuration model generated from the degree sequence of the entire graph.

ADD Health data

Though our main result in (3) is the approximation for large values of m, in this section we check with a small dataset. We consider ADD network project (http://www.cpc.unc.edu/projects/ addhealth), a friendship network among high school students in US. The graph has 1545 nodes and 4003 edges. We take two types of functions. Figure 6 shows the affinity in same gender or different gender friendships and Figure 7 displays the inclination towards same race or different race in friendships. The random walk tours covered around 10% of the graph. We find that the theory works reasonably well for this network data. We have not added the empirical posterior in the figures since for such small sample sizes, the empirical distribution can not converge.

Conclusions

In this work we have studied an efficient way to make the statistical inference on networks. We introduced a technique to make a quicker inference by crawling a very small percentage of a network which may be disconnected or having low conductance. The proposed method can also be performed in parallel. In the paper, first we presented a non-asymptotic unbiased estimator and derived the bounds on its variance showing the connection with the spectral gap. Later we proved that the approximate posterior of the estimator given the crawled data converges to a non-centralized student's t distribution. The numerical experiments on real-world networks of different sizes, large and small, demonstrate the correctness of the estimator. In particular, the simulations clearly show that the derived posterior distribution fits very well with the data even while crawling a small percentage of the graph. 6 Appendix Lemma 3.

lim n→∞ 1 n var π n k=2 f (Y k-1 , Y k ) = 2 r i=2 λ i 1 -λ i f, v i π (u i f ) + 1 d tot (i,j)∈E f (i, j) 2 + 1 d 2 tot ( (i.j)∈E f (i, j) 2 ) 2 + 1 d 2 tot i∈V d i i∼j f (i, j) 2
Proof. We extend the arguments in the proof of [START_REF] Brémaud | Markov chains: Gibbs fields, Monte Carlo simulation, and queue[END_REF]Theorem 6.5] to the edge functions. When the initial distribution is π, we have

Now the first term in [START_REF] Gjoka | 2.5 k-graphs: from sampling to generation[END_REF] is

var π (f (Y k-1 , Y k )) = f, f π -f, Π f π , (12)
where Π = 1π . For the second term in [START_REF] Gjoka | 2.5 k-graphs: from sampling to generation[END_REF],

cov π (f (Y 0 , Y 1 ), f (Y l-1 , Y l )) = E π (f (Y 0 , Y 1 ), f (Y l-1 , Y l )) -(E π [f (Y 0 , Y 1 )]) 2 . ( 13
)
E π (f (Y 0 , Y 1 ), f (Y l-1 , Y l )) = i j k m π i p ij p (l-2) jk p km f (i, j)f (k, m) = i j k π i p ij f (i, j) p
where the first term in (a) follows from the proof of [5, Theorem 6.5] and since lim n→∞ (P n -Π) = 0, the last term is zero using Cesaro's lemma [5, Theorem 1.5 of Appendix].

We have,

Z = I + r i=2 λ i 1 -λ i v i u i , Thus lim n→∞ 1 n var π n k=2 f (Y k-1 , Y k ) = f, f π -f, Π f π + 2 f, I + r i=2 λ i 1 -λ i v i u i -Π f π = f, f π + f, Π f π + 2 f, f π + 2 r i=2 λ i 1 -λ i f, v i π (u i f ) = 1 d tot (i,j)∈E f (i, j) 2 + 1 d 2 tot ( (i.j)∈E f (i, j) 2 ) 2 + 1 d 2 tot i∈V d i i∼j f (i, j) 2 + 2 r i=2 λ i 1 -λ i f, v i π (u i f ) (16

Inria 2 . 4 . 1

 241 Impact of spectral gap on varianceLet S = D 1/2 PD -1/2 , where P is the random walk transition probability matrix as defined in Section 2.1 and D = diag(d 1 , d 2 , . . . , d |V | ) is a diagonal matrix with the node degrees of G . The eigenvalues {λ i } of P and S are same and 1 = λ 1 > λ 2 ≥ . . . ≥ λ |V | ≥ -1. Let jth eigenvector of S be (w ji ), 1 ≤ i ≤ |V |. Let δ be the spectral gap, δ := 1 -λ 2 .

Figure 1 :

 1 Figure 1: Friendster subgraph, function f 1

Figure 2 :

 2 Figure 2: Friendster subgraph, function f 2

Inria

f 1 (Figure 3 :

 13 Figure 3: Dog pals network

Figure 4 :Figure 5 :

 45 Figure 4: Dog pals network: Comparison between configuration model and original graph for f 2 , number of connection between same breeds

Inria

  Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls 17 μ(D m (S n ))

Figure 6 :

 6 Figure 6: ADD network: effect of gender in relationships

Figure 7 :

 7 Figure 7: ADD network: effect of race in friendships

= 2 n- 1 l=2(n - 1 )

 211 f (Y k-1 , Y k )) + 2 k,j=2 k<j cov π (f (Y k-1 , Y k ), f (Y j-1 , Y j )) var π (f (Y k-1 , Y k )) + -l n cov π (f (Y 0 , Y 1 ), f (Y l-1 , Y l )).

  πij f (i, j) (P (l-2) f )(j) = f, P (l-2) f π . (14)Inria Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls 21 Therefore, cov π(f (Y 0 , Y 1 ), f (Y l-1 , Y l )) = f, (P (l-2) -Π) f π . -I) + (I -Π) = Z -Π,

  The network data is based on the social networking website Dogster. Each user (node) indicates the dog breed; the friendships between dogs form the edges. Number of nodes is 415,431 and number of edges is 8,265,511.

	5	×10 -6			For function f 2
							Approximate posterior
					True value		Empirical posterior
	4						No of tours: 50000
	3
	2
	1
	0
	0.6	0.8	1	μ(D m (S n )) 1.2	1.4	1.6	×10 6 1.8

The majority of the datasets in the public repositories SNAP[START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF] and KONECT[START_REF] Kunegis | Konect: the Koblenz network collection[END_REF] are partial website crawls, not complete datasets or uniform samples.RR n°8793

RR n°8793

The developed software is available here: http://www-sop.inria.fr/members/Jithin.Sreedharan/HypRW.zip Inria

Acknowledgements

The authors acknowledge the partial support by ADR "Network Science" of Inria -Bell Labs and by the joint Brazilian-French research team Thanes. This work was in part supported by NSF grant CNS-1065133 and ARL Cooperative Agreement W911NF-09-2-0053. The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either expressed or implied of the NSF, ARL, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon.