text: (cid:90) (cid:18) (cid:19) (cid:88) − − 1 n T 1 s t γ (s) (cid:48) t s 0 n,ij 0 B := K τ (θ (s), s)θ (t ) ds, n l h h h n,ij 0 0 0 h n 0 i,j=1 and τ (θ, s) = X (s)X (s)T exp(θT X (s)) was deﬁned in (2.15). If, in addition, n,ij n,ij n,ij n,ij | | →P | | Ln(t0) 1, then l can be replaced by L (t ) . ln n n 0 − n(n 1)P Recalling that l = (C (t ) = 1) (in the case of undirected networks) is the n 2 n,ij 0 eﬀective sample size, i.e., the expected number of pairs relevant for estimation of θ (t ), we 0 0 see that Theorem 2.1 is a classical asymptotic normality result up to the additional bias term B , which we will discuss next. It holds that n (cid:90) (cid:18) (cid:19) (cid:18) (cid:19) E |(cid:88)| ( B ) n − | − | ≤ (cid:90)1 n (cid:18)T 1 (cid:19)s t0 E γn,ij(s)(cid:107) (cid:107) (cid:107) (cid:48) (cid:107) t0 s K τ (θ (s), s) θ (t ) ds l h h h n,ij 0 0 0 h n 0 i,j=1 T 1 s −(cid:104)t P(C (t ) (cid:12)= 0, C (s) = 1) |t − s| (cid:105) · (cid:107) (cid:48) (cid:107) 0 n,12 0 (cid:12) n,12 0 = hK h hP(C(cid:12) (t ) = 1) h ds θ0(t0) 0 n,12 0 × E (cid:107) (cid:107) sup τ (θ (s), s) C (s) = 1, C (t ) = 1 . ∈ n,12 0 n,12 n,12 0 s U h This is of order O(1) by (2.12) and (2.8). Hence, we get that B = O (1). In general n P one cannot argue that the expectation converges to 0. Thus, in general we will have an − E additional bias term of order h2. Let us suppose that one can show B (B ) = o(1) by n n using some additional assumptions that bound the second moment of this term. We have that E(Bn) = o(1) if P(Cn,h1P2((tC0n)=,102,(Ct0n),=121()s)=1) = o(h). This assumption can only hold if only for a negligible minority of edges the membership to the active set changes. In particular, ≡ for the extreme case of C being constant, we have γ 0 and B = 0. Hence, the bias n,ij n,ij n term B is induced by a change in the sparsity of the active set. n 2.5 Direct network modeling We consider the following general model for the link-based dynamics of a random network, using a multivariate continuous-time counting process approach allowing for arbitrary de- pendence structure between the links by applying the model for dynamic interactions twice: Once for the formation of new links and once for the deletion of existing links (this sepa- { } ration can also be found in Krivitsky and Handcock (2014)). As before let V = 1, ..., n n be the set of vertices and L be the set of edges. Note that here we are considering undi- n rected networks. But directed networks can be handled similarly. For a given link (i, j), we 13 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: equation

text: n

text: T

text: s

text: t

text: γ

text: (s)

text: t

text: s

text: n,ij

text: B

text: K

text: τ

text: (θ

text: (s),

text: s)θ

text: (t

text: ds,

text: n

text: l

text: h

text: h

text: h

text: n,ij

text: h

text: n

text: and

text: τ

text: (θ,

text: s)

text: X

text: (s)X

text: (s)T

text: exp(θT

text: X

text: (s))

text: was

text: deﬁned

text: in

text: If,

text: in

text: addition,

text: n,ij

text: n,ij

text: n,ij

text: n,ij

text: →P

text: then

text: l

text: can

text: be

text: replaced

text: by

text: L

text: (t

text: ln

text: n

text: n

text: n(n

text: Recalling

text: that

text: l

text: (C

text: (t

text: (in

text: the

text: case

text: of

text: undirected

text: networks)

text: is

text: the

text: n

text: n,ij

text: eﬀective

text: sample

text: size,

text: i.e.,

text: the

text: expected

text: number

text: of

text: pairs

text: relevant

text: for

text: estimation

text: of

text: θ

text: (t

text: we

text: see

text: that

text: Theorem

text: is

text: a

text: classical

text: asymptotic

text: normality

text: result

text: up

text: to

text: the

text: additional

text: bias

text: term

text: B

text: which

text: we

text: will

text: discuss

text: next.

text: It

text: holds

text: that

text: n

text: E

text: B

text: n

text: n

text: E

text: s

text: K

text: τ

text: (θ

text: (s),

text: s)

text: θ

text: (t

text: ds

text: l

text: h

text: h

text: h

text: n,ij

text: h

text: n

text: T

text: s

text: P(C

text: (t

text: C

text: (s)

text: |t

text: s|

text: hK

text: h

text: (t

text: h

text: ds

text: E

text: sup

text: τ

text: (θ

text: (s),

text: s)

text: C

text: (s)

text: C

text: (t

text: s

text: U

text: h

text: This

text: is

text: of

text: order

text: by

text: and

text: Hence,

text: we

text: get

text: that

text: B

text: O

text: In

text: general

text: n

text: P

text: one

text: cannot

text: argue

text: that

text: the

text: expectation

text: converges

text: to

text: Thus,

text: in

text: general

text: we

text: will

text: have

text: an

text: E

text: additional

text: bias

text: term

text: of

text: order

text: Let

text: us

text: suppose

text: that

text: one

text: can

text: show

text: B

text: (B

text: by

text: n

text: n

text: using

text: some

text: additional

text: assumptions

text: that

text: bound

text: the

text: second

text: moment

text: of

text: this

text: term.

text: We

text: have

text: that

text: E(Bn)

text: if

text: o(h).

text: This

text: assumption

text: can

text: only

text: hold

text: if

text: only

text: for

text: a

text: negligible

text: minority

text: of

text: edges

text: the

text: membership

text: to

text: the

text: active

text: set

text: changes.

text: In

text: particular,

text: for

text: the

text: extreme

text: case

text: of

text: C

text: being

text: constant,

text: we

text: have

text: γ

text: and

text: B

text: Hence,

text: the

text: bias

text: n,ij

text: n,ij

text: n

text: term

text: B

text: is

text: induced

text: by

text: a

text: change

text: in

text: the

text: sparsity

text: of

text: the

text: active

text: set.

text: n

text: Direct

text: network

text: modeling

text: We

text: consider

text: the

text: following

text: general

text: model

text: for

text: the

text: link-based

text: dynamics

text: of

text: a

text: random

text: network,

text: using

text: a

text: multivariate

text: continuous-time

text: counting

text: process

text: approach

text: allowing

text: for

text: arbitrary

text: de-

text: pendence

text: structure

text: between

text: the

text: links

text: by

text: applying

text: the

text: model

text: for

text: dynamic

text: interactions

text: twice:

text: Once

text: for

text: the

text: formation

text: of

text: new

text: links

text: and

text: once

text: for

text: the

text: deletion

text: of

text: existing

text: links

text: (this

text: sepa-

text: ration

text: can

text: also

text: be

text: found

text: in

text: Krivitsky

text: and

text: Handcock

text: As

text: before

text: let

text: V

text: n

text: n

text: be

text: the

text: set

text: of

text: vertices

text: and

text: L

text: be

text: the

text: set

text: of

text: edges.

text: Note

text: that

text: here

text: we

text: are

text: considering

text: undi-

text: n

text: rected

text: networks.

text: But

text: directed

text: networks

text: can

text: be

text: handled

text: similarly.

text: For

text: a

text: given

text: link

text: (i,

text: j),

text: we

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Lemma 4.4. We have (cid:48) →P P (θ ) 0. (4.7) n 0,n ∈ { } For any k, l 1, ..., q , it holds that (cid:48)(cid:48) →P − P (θ ) Σ. (4.8) n 0,n (cid:12) (cid:12) Moreover, (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) ∂2 (cid:48) sup P (r)(θ) = O (1), (4.9) ∂θ ∂θ n P k,l,r,θ k l (cid:48) (cid:48) ∈ { } (r) where P denotes the r-th component of P , the supremum runs over k, l, r 1, ..., q , ∈n n and θ Θ. (cid:12) (cid:12) (cid:12) (cid:12) (cid:48) E (cid:107) (cid:48) (cid:107) Proof. We start by showing that P (θ ) = o (1). This holds, if ( P (θ ) ) = o(1). (cid:107) (cid:107) · n 0,n P − n 0,n Deﬁne ρ (θ, s) := X (s) exp(θ (s)T X (s)) exp(θT X (s)) . By positivity of n,ij n,ij 0 n,ij n,ij ρ (θ, s), we may apply Fubini’s Theorem, and thus we compute n,ij (cid:90) E (cid:107) (cid:48) (cid:88) (cid:107) ( P (θ ) ) n 0,n ≤ 1 n 1 E l (cid:88) (cid:90)− K(u) (Cn,ij(t0 + uh)ρn,ij(θ0,n, t0 + uh)) du n 1 i,j=1 1 n 1 P = K(u) (C (t + uh) = 1) l − n,ij 0 n 1 i,j=1 × E | (ρ (θ , t + uh) C (t + uh) = 1) du. n,ij 0,n 0 n,ij 0 The expectation in the integral expression can be bounded by applying a Taylor expansion: (cid:32) E (cid:90) (cid:16)| (cid:17) (ρ (θ , s ) C (s ) = 1) n,ij 0,n u n,ij u ≤ E 1 (cid:12)− · (cid:33)− exp [θ (s )(cid:12) α (θ (s ) θ )]T X (s ) dα 0 u (cid:12) 0 u 0,n n,ij u 0 (cid:12) (cid:12) × (cid:107) (cid:107) · (cid:107) − (cid:107) X (s ) 2 C (s ) = 1 θ (s ) θ , n,ij u n,ij u 0 u 0,n 27 ##LTLine## ##LTLine## ##LTLine##

text: Lemma

label: paragraph

text: We

text: have

text: →P

text: P

text: (θ

text: n

text: For

text: any

text: k,

text: l

text: q

text: it

text: holds

text: that

text: →P

text: P

text: (θ

text: Σ.

text: n

text: Moreover,

text: ∂2

text: sup

text: P

text: (r)(θ)

text: O

text: ∂θ

text: ∂θ

text: n

text: P

text: k,l,r,θ

text: k

text: l

text: (r)

text: where

text: P

text: denotes

text: the

text: r-th

text: component

text: of

text: P

text: the

text: supremum

text: runs

text: over

text: k,

text: l,

text: r

text: q

text: ∈n

text: n

text: and

text: θ

text: Θ.

text: E

text: Proof.

text: We

text: start

text: by

text: showing

text: that

text: P

text: (θ

text: o

text: This

text: holds,

text: if

text: P

text: (θ

text: n

text: P

text: n

text: Deﬁne

text: ρ

text: (θ,

text: s)

text: X

text: (s)

text: exp(θ

text: (s)T

text: X

text: (s))

text: exp(θT

text: X

text: (s))

text: By

text: positivity

text: of

text: n,ij

text: n,ij

text: n,ij

text: n,ij

text: ρ

text: (θ,

text: s),

text: we

text: may

text: apply

text: Fubini’s

text: Theorem,

text: and

text: thus

text: we

text: compute

text: n,ij

text: E

text: P

text: (θ

text: n

text: n

text: E

text: l

text: K(u)

text: uh))

text: du

text: n

text: n

text: P

text: K(u)

text: (C

text: (t

text: uh)

text: l

text: n,ij

text: n

text: E

text: (ρ

text: (θ

text: t

text: uh)

text: C

text: (t

text: uh)

text: du.

text: n,ij

text: n,ij

text: The

text: expectation

text: in

text: the

text: integral

text: expression

text: can

text: be

text: bounded

text: by

text: applying

text: a

text: Taylor

text: expansion:

text: E

text: (ρ

text: (θ

text: s

text: C

text: (s

text: n,ij

text: u

text: n,ij

text: u

text: E

text: exp

text: [θ

text: (s

text: α

text: (θ

text: (s

text: θ

text: )]T

text: X

text: (s

text: dα

text: u

text: u

text: n,ij

text: u

text: X

text: (s

text: C

text: (s

text: θ

text: (s

text: θ

text: n,ij

text: u

text: n,ij

text: u

text: u

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Moreover, it holds that (cid:101) (cid:101) 1 (cid:48)(cid:48) →P − ∂2(cid:96)(θ (t ), t ) = P (θ (t )) Σ. (4.29) l θ n 0 0 n n 0 n Proof. The proof of (4.27) follows by using similar arguments as in the proof of Lemma 4.4, with θ replaced by θ (s), and with K replaced by K2. 0,n 0 For the proof of claim (4.28), we calculate the expectation of the left hand side of (4.28). Because the integrand is positive, we can apply Fubini, and we get that the expectation is equal to (cid:90) (cid:20) (cid:18) (cid:13) (cid:18) (cid:19) (cid:13) (cid:19) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) − T E (cid:16)1 √1 K (cid:17)s(cid:12)(cid:12) t0 Xn,12(s(cid:35)) >(cid:18)(cid:15) (cid:107)Xn,(cid:19)12(s)(cid:107)2 l h (cid:12)h 0 n × exp θ0(cid:90)(s)T Xn,12(s) Cn,12(s) = 1 1 K s − t0 2 PP(Cn,12(s) = 1) ds h h (C (t ) = 1) n,12 0 ≤ 1 (cid:16)· √1 1 P(C (t + uh)(cid:12)= 1) (cid:17) K3(u) Pn,12 0 (cid:12)(cid:12) ε l h − (C (t ) = 1) (cid:18) n (cid:19) 1 n,12 0 E (cid:107) (cid:107) (cid:107) (cid:107) X (t + uh) 3eτ Xn,12(t0+uh) C (t + uh) = 1 du n,12 0 n,12 0 √1 = O = o(1). l h n ∞ Here we use (2.10), max− ≤ ≤ K(u) < and (2.9). This shows (4.28). 1 u 1 To see (4.29), we show that (cid:101) (cid:48)(cid:48) − (cid:48)(cid:48) P (θ ) P (θ (t )) = o (1). (4.30) n 0,n n n 0 P This then implies (4.29) because of (4.8). By using exactly the same(cid:101)arguments as in the proof of Lemma 4.5, we(cid:101)obtain − ≤ (cid:107) (cid:107) (cid:107) (cid:107) · (cid:107) − (cid:107) eθ0T,nXn,ij(s) eθn(t0)TnXn,ij(s) Xn,ij(s) eτ Xn,ij(s) θ0,n θn(t0) . (cid:101) This gives (cid:48)(cid:48) − (cid:48)(cid:48) P (θ ) P (θ (t )) n 0,n n n 0 37 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Moreover,

text: it

text: holds

text: that

text: →P

text: (t

text: t

text: P

text: (θ

text: (t

text: Σ.

text: l

text: θ

text: n

text: n

text: n

text: n

text: Proof.

text: The

text: proof

text: of

text: follows

text: by

text: using

text: similar

text: arguments

text: as

text: in

text: the

text: proof

text: of

text: Lemma

text: with

text: θ

text: replaced

text: by

text: θ

text: (s),

text: and

text: with

text: K

text: replaced

text: by

text: For

text: the

text: proof

text: of

text: claim

text: we

text: calculate

text: the

text: expectation

text: of

text: the

text: left

text: hand

text: side

text: of

text: Because

text: the

text: integrand

text: is

text: positive,

text: we

text: can

text: apply

text: Fubini,

text: and

text: we

text: get

text: that

text: the

text: expectation

text: is

text: equal

text: to

text: T

text: E

text: √1

text: K

text: l

text: h

text: n

text: exp

text: K

text: s

text: ds

text: h

text: h

text: (C

text: (t

text: √1

text: P(C

text: (t

text: ε

text: l

text: h

text: (C

text: (t

text: n

text: E

text: X

text: (t

text: uh)

text: C

text: (t

text: uh)

text: du

text: √1

text: O

text: l

text: h

text: n

text: Here

text: we

text: use

text: max−

text: K(u)

text: and

text: This

text: shows

text: u

text: To

text: see

text: we

text: show

text: that

text: P

text: (θ

text: P

text: (θ

text: (t

text: o

text: n

text: n

text: n

text: P

text: This

text: then

text: implies

text: because

text: of

text: By

text: using

text: exactly

text: the

text: as

text: in

text: the

text: proof

text: of

text: Lemma

text: Xn,ij(s)

text: eτ

text: Xn,ij(s)

text: This

text: gives

text: P

text: (θ

text: P

text: (θ

text: (t

text: n

text: n

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Clustering Coefficient=0.134791 in 1 3 Clustering Coefficient=0.148673 in 2 4 0.14 0.16 0.18 0.20 0.10 0.15 0.20 0.25 Clustering Coefficients Clustering Coefficients (a) Only edges with tour frequency (b) Only edges with tour frequency between one and three between two and four Clustering Coefficient=0.103448 in 3 5 Clustering Coefficient=0.144578 in 4 6 0.10 0.15 0.20 0.25 0.05 0.10 0.15 0.20 0.25 0.30 Clustering Coefficients Clustering Coefficients (c) Only edges with tour frequency (d) Only edges with tour frequency between three and ﬁve between four and six Clustering Coefficient=0.081522 in 5 12 Clustering Coefficient=0.105263 in 10 10000 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.0 0.1 0.2 0.3 0.4 0.5 0.6 Clustering Coefficients Clustering Coefficients (e) Only edges with tour frequency (f) Only edges with tour frequency between ﬁve and twelve larger than ten Figure 7: Histograms of clustering coeﬃcients of the graphs which arise by taking diﬀerent edges into account (see individual caption) from simulations for 7th December 2012. In the title of the plot the observed value is shown. 48 ycneuqerF ycneuqerF ycneuqerF 007 006 005 004 003 002 001 0 0021 0001 008 006 004 002 0 007 006 005 004 003 002 001 0 ycneuqerF ycneuqerF ycneuqerF 008 006 004 002 0 008 006 004 002 0 0001 008 006 004 002 0 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Clustering

font: default

text: in

text: Clustering

text: in

text: Clustering

text: Coefficients

text: Clustering

text: Coefficients

text: (a)

text: Only

label: caption

text: edges

text: with

text: tour

text: frequency

text: (b)

text: Only

text: edges

text: with

text: tour

text: frequency

text: between

text: one

text: and

text: three

text: between

text: two

text: and

text: four

text: Clustering

text: in

text: Clustering

text: in

text: Clustering

text: Coefficients

text: Clustering

text: Coefficients

text: (c)

text: Only

text: edges

text: with

text: tour

text: frequency

text: (d)

text: Only

text: edges

text: with

text: tour

text: frequency

text: between

text: three

text: and

text: ﬁve

text: between

text: four

text: and

text: six

text: Clustering

text: in

text: Clustering

text: in

text: Clustering

text: Coefficients

text: Clustering

text: Coefficients

text: (e)

text: Only

text: edges

text: with

text: tour

text: frequency

text: (f)

text: Only

text: edges

text: with

text: tour

text: frequency

text: between

text: ﬁve

text: and

text: twelve

text: larger

text: than

text: ten

text: Figure

text: Histograms

text: of

text: clustering

text: coeﬃcients

text: of

text: the

text: graphs

text: which

text: arise

text: by

text: taking

text: diﬀerent

text: edges

text: into

text: account

text: (see

text: individual

text: caption)

text: from

text: simulations

text: for

text: December

text: In

text: the

text: title

text: of

text: the

text: plot

text: the

text: observed

text: value

text: is

text: shown.

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Degree Distribution 1 3 Degree Distribution 2 4 0 5 10 15 20 25 0 5 10 15 Degrees Degrees (a) Only edges with tour frequency (b) Only edges with tour frequency between one and three between two and four Degree Distribution 3 5 Degree Distribution 4 6 0 2 4 6 8 10 12 0 2 4 6 8 10 Degrees Degrees (c) Only edges with tour frequency (d) Only edges with tour frequency between three and ﬁve between four and six Degree Distribution 5 12 Degree Distribution 10 10000 0 2 4 6 8 10 12 0 2 4 6 8 Degrees Degrees (e) Only edges with tour frequency (f) Only edges with tour frequency between ﬁve and twelve between larger than ten Figure 8: Degree distributions of the graphs which arise by taking diﬀerent edges into account (see individual caption) from simulations for 18th April 2014. Dotted lines show 10% and 90% quantiles of simulations and solid line shows true distributions. 49 ycneuqerF ycneuqerF ycneuqerF 05 04 03 02 01 0 08 06 04 02 0 051 001 05 0 ycneuqerF ycneuqerF ycneuqerF 06 04 02 0 021 001 08 06 04 02 0 002 051 001 05 0 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Degree

text: Distribution

text: Degree

text: Distribution

text: Degrees

text: Degrees

text: (a)

text: Only

text: edges

text: with

text: tour

text: frequency

text: (b)

text: Only

text: edges

text: with

text: tour

text: frequency

text: between

text: one

text: and

text: three

text: between

text: two

text: and

text: four

text: Degree

text: Distribution

text: Degree

text: Distribution

text: Degrees

text: Degrees

text: (c)

text: Only

text: edges

text: with

text: tour

text: frequency

text: (d)

text: Only

text: edges

text: with

text: tour

text: frequency

text: between

text: three

text: and

text: ﬁve

text: between

text: four

text: and

text: six

text: Degree

text: Distribution

text: Degree

text: Distribution

text: Degrees

text: Degrees

text: (e)

text: Only

text: edges

text: with

text: tour

text: frequency

text: (f)

text: Only

text: edges

text: with

text: tour

text: frequency

text: between

text: ﬁve

text: and

text: twelve

text: between

text: larger

text: than

text: ten

text: Figure

text: Degree

text: distributions

text: of

text: the

text: graphs

text: which

text: arise

text: by

text: taking

text: diﬀerent

text: edges

text: into

text: account

text: (see

text: individual

text: caption)

text: from

text: simulations

text: for

text: April

text: Dotted

text: lines

text: show

text: and

text: quantiles

text: of

text: simulations

text: and

text: solid

text: line

text: shows

text: true

text: distributions.

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Degree Distribution 1 3 Degree Distribution 2 4 0 5 10 15 20 25 0 5 10 15 Degrees Degrees (a) Only edges with tour frequency (b) Only edges with tour frequency between one to three between two to four Degree Distribution 3 5 Degree Distribution 4 6 0 2 4 6 8 10 12 0 2 4 6 8 10 Degrees Degrees (c) Only edges with tour frequency (d) Only edges with tour frequency between three to ﬁve between four to six Degree Distribution 5 12 Degree Distribution 10 10000 0 2 4 6 8 10 0 2 4 6 8 Degrees Degrees (e) Only edges with tour frequency (f) Only edges with tour frequency between ﬁve to twelve more than ten Figure 11: Degree distributions of the graphs, which arise by taking diﬀerent tour frequen- cies into account (see individual caption) from simulations for 10th July 2015. Dotted lines show 10% and 90% quantiles of simulations and solid line shows true distributions. 52 ycneuqerF ycneuqerF ycneuqerF 05 04 03 02 01 0 001 08 06 04 02 0 021 001 08 06 04 02 0 ycneuqerF ycneuqerF ycneuqerF 08 06 04 02 0 051 001 05 0 051 001 05 0 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Degree

text: Distribution

text: Degree

text: Distribution

text: Degrees

text: Degrees

text: (a)

text: Only

text: edges

text: with

text: tour

text: frequency

text: (b)

text: Only

text: edges

text: with

text: tour

text: frequency

text: between

text: one

text: to

text: three

text: between

text: two

text: to

text: four

text: Degree

text: Distribution

text: Degree

text: Distribution

text: Degrees

text: Degrees

text: (c)

text: Only

text: edges

text: with

text: tour

text: frequency

text: (d)

text: Only

text: edges

text: with

text: tour

text: frequency

text: between

text: three

text: to

text: ﬁve

text: between

text: four

text: to

text: six

text: Degree

text: Distribution

text: Degree

text: Distribution

text: Degrees

text: Degrees

text: (e)

text: Only

text: edges

text: with

text: tour

text: frequency

text: (f)

text: Only

text: edges

text: with

text: tour

text: frequency

text: between

text: ﬁve

text: to

text: twelve

text: more

text: than

text: ten

text: Figure

text: Degree

text: distributions

text: of

text: the

text: graphs,

text: which

text: arise

text: by

text: taking

text: diﬀerent

text: tour

text: frequen-

text: cies

text: into

text: account

text: (see

text: individual

text: caption)

text: from

text: simulations

text: for

text: July

text: Dotted

text: lines

text: show

text: and

text: quantiles

text: of

text: simulations

text: and

text: solid

text: line

text: shows

text: true

text: distributions.

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ycneuqerF

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Deriving this expression with respect to µ, setting the derivative equal to zero, and rear- ranging terms, yields (to save space we use here a fraction, although the denominator is a matrix) θˆ(cid:80) (t ) − θ ((cid:16)t ) (cid:17) (cid:82) (cid:16) (cid:17) K 0 0 0 ≈ (i,j)∈Ln h1 K(cid:80) t−ht0 ∆N(cid:82) n,ij(t)(cid:16)Xn−,ij((cid:17)t)− 0T h1 K t−ht0 Cn,ij(t)Xn,ijeθ0(t0)TXn,ij(t)dt. (i,j)∈Lm 0T h1 K t ht0 Xn,ij(t)Xn,ij(t)Teθ0(t0)TXn,ij(t)dt E | · P Using the notation y1 := (Xn,ij(t0)eθ0(t0)TXn,ij(t0) Cn,ij(t0) = 1) (Cn,ij(t0) = 1) and E | · P y2 := (Xn,ij(t0)Xn,ij(t0)T eθ0(t0)TXn,ij(t0) Cn,ij(t0) = 1) (Cn,ij(t0) = 1), we obtain the approximation (cid:80) (cid:80) (cid:0) (cid:1) − − θˆ (t ) − θ (t ) ≈ (i,j)∈Ln 0<t≤T h1 K t ht0 ∆Nn,ij(t)Xn,ij(t) y1 . (6.2) K 0 0 0 y 2 Now deﬁne the local linear estimator θˆ (t ), with respect to a kernel K, as the value of LC,K 0 ∈ µ maximizing the following expression over (µ , µ ) Θ2 : 0 0 1 (cid:18) (cid:19) (cid:88) (cid:88) − 1 t t − K (cid:90) 0(cid:88) (cid:18)∆Nn,ij((cid:19)t)[µ0 + µ1(t t0)]T Xn,ij(t) ≤ h h ∈ 0<t T (i,j) Ln − − T 1 t t − K 0 e[µ0+µ1(t t0)]TXn,ij(t)dt. 0 ∈ h h (i,j) Ln Using the same approximations as in the usual kernel estimation setting, and deriving the resulting approximate likelihood, we obtain (cid:80) − (cid:80) (cid:0) (cid:1) θˆ θ (t ) LC,K 0 0 ≈(cid:82) (i,j)∈Ln 0<t≤T h1 K t−ht0 M2M−2t−−hMt012M1 ∆Nn,ij(t)Xn,ij(t) − y1 , y 2 where M := −1 ukK(u)du. The previous computations were just a heuristic. But never- k 1 theless, the similarity between the previous display and (6.2) suggests that the local linear estimator θˆ using the kernel K is actually just a regular kernel estimator θˆ with kernel LC,K L function 57 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Deriving

text: this

text: expression

text: with

text: respect

text: to

text: µ,

text: setting

text: the

text: derivative

text: equal

text: to

text: zero,

text: and

text: rear-

text: ranging

text: terms,

text: yields

text: (to

text: save

text: space

text: we

text: use

text: here

text: a

text: fraction,

text: although

text: the

text: denominator

text: is

text: a

text: matrix)

text: (t

text: θ

text: K

text: (i,j)∈Ln

text: K

text: (i,j)∈Lm

text: K

text: t

text: E

text: P

text: Using

text: the

text: notation

text: and

text: E

text: P

text: we

text: obtain

text: the

text: approximation

text: θˆ

text: (t

text: θ

text: (t

text: (i,j)∈Ln

text: K

text: t

text: ∆Nn,ij(t)Xn,ij(t)

text: K

text: y

text: Now

text: deﬁne

text: the

text: local

text: linear

text: estimator

text: θˆ

text: (t

text: with

text: respect

text: to

text: a

text: kernel

text: K,

text: as

text: the

text: value

text: of

text: LC,K

text: µ

text: maximizing

text: the

text: following

text: expression

text: over

text: (µ

text: µ

text: Θ2

text: t

text: t

text: K

text: Xn,ij(t)

text: h

text: h

text: T

text: (i,j)

text: Ln

text: T

text: t

text: t

text: K

text: h

text: h

text: (i,j)

text: Ln

text: Using

text: the

text: same

text: approximations

text: as

text: in

text: the

text: usual

text: kernel

text: estimation

text: setting,

text: and

text: deriving

text: the

text: resulting

text: approximate

text: likelihood,

text: we

text: obtain

text: θˆ

text: θ

text: (t

text: LC,K

text: (i,j)∈Ln

text: K

text: ∆Nn,ij(t)Xn,ij(t)

text: y

text: where

text: M

text: −1

text: ukK(u)du.

text: The

text: previous

text: computations

text: were

text: just

text: a

text: heuristic.

text: But

text: never-

text: k

text: theless,

text: the

text: similarity

text: between

text: the

text: previous

text: display

text: and

text: suggests

text: that

text: the

text: local

text: linear

text: estimator

text: θˆ

text: using

text: the

text: kernel

text: K

text: is

text: actually

text: just

text: a

text: regular

text: kernel

text: estimator

text: θˆ

text: with

text: kernel

text: LC,K

text: L

text: function

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: → ∞ as n . This way sparsity in the observations can be captured in the model. For the asymptotic result (Theorem 2.1) to hold, the network cannot be too sparse (essentially an increase in the number of actors must lead to an increase in the number of selected pairs). This will be made precise in the assumptions given in Section . 2.2 Estimation in time-varying coeﬃcient models In time series applications, it turns out that powerful ﬁts can be achieved by letting the time series parameters depend on time, and this is what we consider here as well. We will use the above model with θ in (1.1) depending on t, or in other words, θ = θ(t) is now a parameter function. An estimator of this parameter function at a given point t can be obtained by maximizing 0 the following local likelihood function in µ which is obtained by localizing the likelihood (2.1) for a constant parameter at time t by means of a kernel K (cid:18) 0 (cid:19) (cid:88) (cid:88) − 1 t t (cid:96)T (µ, t0) = (cid:90) K (cid:88) 0 (cid:18) ∆(cid:19)Nn,ij(t) log λn,ij(µ, t) (2.2) ≤ h h ∈ 0<t T (i,j) Ln − − T 1 t t 0 K λ (µ, t)dt, n,ij 0 ∈ h h (i,j) Ln where K is a kernel function (positive and integrating to one), and h = h is the bandwidth. n The corresponding local MLE is deﬁned as θˆ(t ) = arg max (cid:96) (θ, t ), (2.3) 0 ∈ T 0 θ Θ with Θ being the allowed range of the parameter function θ. Recall that we use the following Cox-type form of the intensity: (cid:8) (cid:9) λ (θ, t) = C (t) exp θ(t)T X (t) . (2.4) n,ij n,ij n,ij Using the hazard functions from (2.4), the local log-likelihood can be written as: (cid:18)(cid:90) (cid:18) (cid:19) (cid:88) − n 1 T t t (cid:96) (θ, t ) = K 0 θT X (t)dN (t) T 0 n,ij n,ij h h 0 i,j=1 6 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: as

text: n

text: This

text: way

text: sparsity

text: in

text: the

text: observations

text: can

text: be

text: captured

text: in

text: the

text: model.

text: For

text: the

text: asymptotic

text: result

text: (Theorem

text: to

text: hold,

text: the

text: network

text: cannot

text: be

text: too

text: sparse

text: (essentially

text: an

text: increase

text: in

text: the

text: number

text: of

text: actors

text: must

text: lead

text: to

text: an

text: increase

text: in

text: the

text: number

text: of

text: selected

text: pairs).

text: This

text: will

text: be

text: made

text: precise

text: in

text: the

text: assumptions

text: given

text: in

text: Section

label: section

text: Estimation

text: in

text: time-varying

text: coeﬃcient

text: models

text: In

text: time

text: series

text: applications,

text: it

text: turns

text: out

text: that

text: powerful

text: ﬁts

text: can

text: be

text: achieved

text: by

text: letting

text: the

text: time

text: series

text: parameters

text: depend

text: on

text: time,

text: and

text: this

text: is

text: what

text: we

text: consider

text: here

text: as

text: well.

text: We

text: will

text: use

text: the

text: above

text: model

text: with

text: θ

text: in

text: depending

text: on

text: t,

text: or

text: in

text: other

text: words,

text: θ

text: θ(t)

text: is

text: now

text: a

text: parameter

text: function.

text: An

text: estimator

text: of

text: this

text: parameter

text: function

text: at

text: a

text: given

text: point

text: t

text: can

text: be

text: obtained

text: by

text: maximizing

text: the

text: following

text: local

text: likelihood

text: function

text: in

text: µ

text: which

text: is

text: obtained

text: by

text: localizing

text: the

text: likelihood

text: for

text: a

text: constant

text: parameter

text: at

text: time

text: t

text: by

text: means

text: of

text: a

text: kernel

text: K

text: t

text: t

text: (µ,

text: K

text: log

text: λn,ij(µ,

text: t)

text: h

text: h

text: T

text: (i,j)

text: Ln

text: T

text: t

text: t

text: K

text: λ

text: (µ,

text: t)dt,

text: n,ij

text: h

text: h

text: (i,j)

text: Ln

text: where

text: K

text: is

text: a

text: kernel

text: function

text: (positive

text: and

text: integrating

text: to

text: one),

text: and

text: h

text: h

text: is

text: the

text: bandwidth.

text: n

text: The

text: corresponding

text: local

text: MLE

text: is

text: deﬁned

text: as

text: θˆ(t

text: arg

text: max

text: (θ,

text: t

text: T

text: θ

text: Θ

text: with

text: Θ

text: being

text: the

text: allowed

text: range

text: of

text: the

text: parameter

text: function

text: θ.

text: Recall

text: that

text: we

text: use

text: the

text: following

text: Cox-type

text: form

text: of

text: the

text: intensity:

text: λ

text: (θ,

text: t)

text: C

text: (t)

text: exp

text: θ(t)T

text: X

text: (t)

text: n,ij

text: n,ij

text: n,ij

text: Using

text: the

text: hazard

text: functions

text: from

text: the

text: local

text: log-likelihood

text: can

text: be

text: written

text: as:

text: n

text: T

text: t

text: t

text: (θ,

text: t

text: K

text: θT

text: X

text: (t)dN

text: (t)

text: T

text: n,ij

text: n,ij

text: h

text: h

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:90) (cid:18) (cid:19) (cid:19) − − T t t K 0 C (t) exp(θT X (t))dt . (2.5) n,ij n,ij h 0 The maximum likelihood estimator θˆ (t ) studied in this paper is deﬁned as the maximizer n 0 of (2.5) over θ. Denote by L (t ) the set of active edges, i.e., the set of all pairs (i, j), such n 0 | | that, C (t ) = 1. We denote by L (t ) the size of the set L (t ). Our main theoretical n,ij 0 n 0 ∈ n 0 result, given below, says that for a given t (0, T ), the maximum likelihood estimator 0 θˆ (t ) exists, is asymptotically consistent, and is asymptotically normal. n 0 To formulate our main result, the following technical assumptions are needed. 2.3 Assumptions Our assumptions do not specify the dynamics of the covariates X (t) and of the censoring n,ij variable C (t). Instead of this, we assume that the stochastic behavior of these variables n,ij → ∞ stabilizes for n . Assumption (A1) is speciﬁc to our setting and it states our general understanding of the dynamics, while assumptions (A2), (A3) and (A5) are standard. As- sumption (A4) guarantees that the covariates are well behaved and can be found similarly in Perry and Wolfe (2013). Finally, (A6) and (A7) speciﬁcally describe the dependence situation in our context. They quantify how we make the idea mathematically precise that while the network grows the actors get further and further apart and hence inﬂuence each other less and less. The structure in the following is that we ﬁrstly state an assumption and then discuss its meaning and the intuition behind them. ∈ − (A1) For every n and for any t [t h, t + h], the joint distribution of (C (t), X (t)) 0 0 ∈ − n,ij n,ij is identical for all pairs (i, j). Furthermore, for any s, t [t h, t + h], the conditional 0 0 distribution of the covariate X (t) given that C (s) = 1, has a density f (y) with n,ij n,ij s,t R respect to a measure µ on q, and this conditional distribution does not depend on (i, j) → ∞ → and n. We use the shorthand notation f for f . Finally, it holds that: n , h 0, and with l := n(n−1) P(C (t ) = 1) →s∞, wes,hsave l h → ∞, and l h5 = O(1). n 2 n,12 0 n n n(n−1) · P Note that, l = (C (t ) = 1) is the eﬀective sample size at time t , because − n 2 n,12 0 0 n(n 1) is the number of possible links between vertices, of which, in average, we observe 2 − P n(n 1) the fraction (C (t ) = 1). (For directed networks, one simply has to replace by − n,12 0 2 n(n 1) in the deﬁnition of l .) With this in mind, the assumptions on the bandwidth are n standard. The most restrictive assumption in (A1) is that the conditional distribution of X (t), given C (s) = 1, does not depend on i, j. Observe that this holds if the array of n,ij n,ij (C , X ) is jointly exchangeable in (i, j) for any ﬁxed n. The additional assumption n,ij n,ij i,j that the conditional distribution of X (t), given C (s), does not change with n is not n,ij n,ij very restrictive, because it is natural to assume that the distribution depends only on the local structure of the network. For instance, if we assume that a ﬁxed vertex i has only a bounded number of close interaction partners j while the network grows, then it is natural to assume that the local structure given by the interacting partners does not undergo major 7 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: T

text: t

text: t

text: K

text: C

text: (t)

text: exp(θT

text: X

text: (t))dt

text: n,ij

text: n,ij

text: h

text: The

text: maximum

text: likelihood

text: estimator

text: θˆ

text: (t

text: studied

text: in

text: this

text: paper

text: is

text: deﬁned

text: as

text: the

text: maximizer

text: n

text: of

text: over

text: θ.

text: Denote

text: by

text: L

text: (t

text: the

text: set

text: of

text: active

text: edges,

text: i.e.,

text: the

text: set

text: of

text: all

text: pairs

text: (i,

text: j),

text: such

text: n

text: that,

text: C

text: (t

text: We

text: denote

text: by

text: L

text: (t

text: the

text: size

text: of

text: the

text: set

text: L

text: (t

text: Our

text: main

text: theoretical

text: n,ij

text: n

text: n

text: result,

text: given

text: below,

text: says

text: that

text: for

text: a

text: given

text: t

text: T

text: the

text: maximum

text: likelihood

text: estimator

text: θˆ

text: (t

text: exists,

text: is

text: asymptotically

text: consistent,

text: and

text: is

text: asymptotically

text: normal.

text: n

text: To

text: formulate

text: our

text: main

text: result,

text: the

text: following

text: technical

text: assumptions

text: are

text: needed.

text: Assumptions

text: Our

text: assumptions

text: do

text: not

text: specify

text: the

text: dynamics

text: of

text: the

text: covariates

text: X

text: (t)

text: and

text: of

text: the

text: censoring

text: n,ij

text: variable

text: C

text: (t).

text: Instead

text: of

text: this,

text: we

text: assume

text: that

text: the

text: stochastic

text: behavior

text: of

text: these

text: variables

text: n,ij

text: stabilizes

text: for

text: n

text: Assumption

text: is

text: speciﬁc

text: to

text: our

text: setting

text: and

text: it

text: states

text: our

text: general

text: understanding

text: of

text: the

text: dynamics,

text: while

text: assumptions

text: and

text: are

text: standard.

text: As-

text: sumption

text: guarantees

text: that

text: the

text: covariates

text: are

text: well

text: behaved

text: and

text: can

text: be

text: found

text: similarly

text: in

text: Perry

text: and

text: Wolfe

text: Finally,

text: and

text: speciﬁcally

text: describe

text: the

text: dependence

text: situation

text: in

text: our

text: context.

text: They

text: quantify

text: how

text: we

text: make

text: the

text: idea

text: mathematically

text: precise

text: that

text: while

text: the

text: network

text: grows

text: the

text: actors

text: get

text: further

text: and

text: further

text: apart

text: and

text: hence

text: inﬂuence

text: each

text: other

text: less

text: and

text: less.

text: The

text: structure

text: in

text: the

text: following

text: is

text: that

text: we

text: ﬁrstly

text: state

text: an

text: assumption

text: and

text: then

text: discuss

text: its

text: meaning

text: and

text: the

text: intuition

text: behind

text: them.

text: For

text: every

text: n

text: and

text: for

text: any

text: t

text: [t

text: h,

text: t

text: h],

text: the

text: joint

text: distribution

text: of

text: (C

text: (t),

text: X

text: (t))

text: n,ij

text: n,ij

text: is

text: identical

text: for

text: all

text: pairs

text: (i,

text: j).

text: Furthermore,

text: for

text: any

text: s,

text: t

text: [t

text: h,

text: t

text: h],

text: the

text: conditional

text: distribution

text: of

text: the

text: covariate

text: X

text: (t)

text: given

text: that

text: C

text: (s)

text: has

text: a

text: density

text: f

text: (y)

text: with

text: n,ij

text: n,ij

text: s,t

text: R

text: respect

text: to

text: a

text: measure

text: µ

text: on

text: q,

text: and

text: this

text: conditional

text: distribution

text: does

text: not

text: depend

text: on

text: (i,

text: j)

text: and

text: n.

text: We

text: use

text: the

text: shorthand

text: notation

text: f

text: for

text: f

text: Finally,

text: it

text: holds

text: that:

text: n

text: h

text: and

text: with

text: l

text: P(C

text: (t

text: →s∞,

text: wes,hsave

text: l

text: h

text: and

text: l

text: n

text: n

text: n

text: P

text: Note

text: that,

text: l

text: (C

text: (t

text: is

text: the

text: eﬀective

text: sample

text: size

text: at

text: time

text: t

text: because

text: n

text: n(n

text: is

text: the

text: number

text: of

text: possible

text: links

text: between

text: vertices,

text: of

text: which,

text: in

text: average,

text: we

text: observe

text: P

text: n(n

text: the

text: fraction

text: (C

text: (t

text: (For

text: directed

text: networks,

text: one

text: simply

text: has

text: to

text: replace

text: by

text: n(n

text: in

text: the

text: deﬁnition

text: of

text: l

text: With

text: this

text: in

text: mind,

text: the

text: assumptions

text: on

text: the

text: bandwidth

text: are

text: n

text: standard.

text: The

text: most

text: restrictive

text: assumption

text: in

text: is

text: that

text: the

text: conditional

text: distribution

text: of

text: X

text: (t),

text: given

text: C

text: (s)

text: does

text: not

text: depend

text: on

text: i,

text: j.

text: Observe

text: that

text: this

text: holds

text: if

text: the

text: array

text: of

text: n,ij

text: n,ij

text: (C

text: X

text: is

text: jointly

text: exchangeable

text: in

text: (i,

text: j)

text: for

text: any

text: ﬁxed

text: n.

text: The

text: additional

text: assumption

text: n,ij

text: n,ij

text: i,j

text: that

text: the

text: conditional

text: distribution

text: of

text: X

text: (t),

text: given

text: C

text: (s),

text: does

text: not

text: change

text: with

text: n

text: is

text: not

text: n,ij

text: n,ij

text: very

text: restrictive,

text: because

text: it

text: is

text: natural

text: to

text: assume

text: that

text: the

text: distribution

text: depends

text: only

text: on

text: the

text: local

text: structure

text: of

text: the

text: network.

text: For

text: instance,

text: if

text: we

text: assume

text: that

text: a

text: ﬁxed

text: vertex

text: i

text: has

text: only

text: a

text: bounded

text: number

text: of

text: close

text: interaction

text: partners

text: j

text: while

text: the

text: network

text: grows,

text: then

text: it

text: is

text: natural

text: to

text: assume

text: that

text: the

text: local

text: structure

text: given

text: by

text: the

text: interacting

text: partners

text: does

text: not

text: undergo

text: major

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: → ∞ changes for n (we discuss after assumption (A6) in more detail how this scenario gets incorporated in the C ). We make this additional assumption mainly to avoid stating n,ij lengthy technical assumptions allowing to interchange the order of diﬀerentiation and inte- gration at several places in the proof. (cid:82) W(cid:82) e add some standard assumptions on the kernel. − 1 (A2) The kernel K is positive and supported on [ 1, 1], and it satisﬁes − K(u)du = 1, ∞ 1 −1 K(u)udu = 0 and max− ≤ ≤ K(u) < . 1 1 u 1 The next condition makes smoothness assumptions for the parameter curve θ and the 0 density f (y). s (cid:107) (cid:107) ∞ (A3) The parameter space Θ is compact and convex. Let τ := sup ∈ θ < . The θ Θ parameter function θ (t) takes values in Θ, and, in a neighborhood of t , it is twice contin- 0 0 uously diﬀerentiable. The value θ (t ) lies in the interior of Θ. 0 0 We continue with some tail conditions on f (y) and its derivatives. They are fulﬁlled if, s e.g., the covariates are bounded. (A4) For µ-almost all y (see (A1) for a deﬁnition of µ), the density f (y) is twice contin- s − uously diﬀerentiable in s. For an open neighborhood U of t and U := [t h, t + h] it 0 h 0 0 holds for all pairs (i, j) and (k, l) (cid:90) (cid:26) (cid:12) (cid:12) (cid:0) (cid:1) (cid:0) (cid:1) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:107)(cid:12) (cid:107) (cid:107) (cid:107) (cid:12) (cid:107) (cid:107) | | (cid:27) (cid:107) (cid:107) (cid:107) (cid:107) d sup 1 + (cid:12)y + y 2(cid:12)+ y 3 f (y) + 1 + y + y 2 f (y) s∈U (cid:12)(cid:12) (cid:12)(cid:12) s ds s (cid:18) (cid:107) (cid:107) d2 (cid:107) (cid:107) · · · (cid:107) (cid:107) ∞ + (1 + y ) f (y) + y 2 f (y) exp(τ y )dµ(y) < , (2.6) ds2 s s,t0 E (cid:107) (cid:107) · (cid:107) (cid:12)(cid:107) (cid:17) sup X (s) 2 X (t)(cid:12) 2 ∈ n,ij n,kl (cid:12) s,t U h · (cid:107) (cid:107) (cid:107) (cid:107) (cid:18) eτ( Xn,ij(s) + Xn,kl(t) ) (cid:12)(cid:12)Cn,ij(t0) = 1, Cn,kl(t0) = 1(cid:19) = O(1), (2.7) ∈ { } (cid:12) For k 2, 3 : (cid:12) (cid:18) E (cid:107) (cid:107) (cid:107) (cid:107) sup (cid:2)X (s) keτ Xn,12(s) C (s) = 1, C (t ) = 0 = O(cid:3) (1), (2.8) ∈ n,12 n,12 n,12 0 s U h E sup (cid:107)X (s)(cid:107) + (cid:107)X (s)(cid:107)2 + (cid:107)X (cid:12)(cid:12) (s)(cid:107)3 + (cid:107)X(cid:19) (s)(cid:107)4 ∈ n,12 n,12 n,(cid:12)12 n,12 s U (cid:12) h · (cid:107) (cid:107) ∞ eτ Xn,12(s) C (s) = 1 < + . (2.9) n,12 8 ##LTLine## ##LTLine##

text: changes

text: for

text: n

text: (we

text: discuss

text: after

text: assumption

text: in

text: more

text: detail

text: how

text: this

text: scenario

text: gets

text: incorporated

text: in

text: the

text: C

text: We

text: make

text: this

text: additional

text: assumption

text: mainly

text: to

text: avoid

text: stating

text: n,ij

text: lengthy

text: technical

text: assumptions

text: allowing

text: to

text: interchange

text: the

text: order

text: of

text: diﬀerentiation

text: and

text: inte-

text: gration

text: at

text: several

text: places

text: in

text: the

text: proof.

text: e

text: add

text: some

text: standard

text: assumptions

text: on

text: the

text: kernel.

text: The

text: kernel

text: K

text: is

text: positive

text: and

text: supported

text: on

text: and

text: it

text: satisﬁes

text: K(u)du

text: −1

text: K(u)udu

text: and

text: max−

text: K(u)

text: u

text: The

text: next

text: condition

text: makes

text: smoothness

text: assumptions

text: for

text: the

text: parameter

text: curve

text: θ

text: and

text: the

text: density

text: f

text: (y).

text: s

text: The

text: parameter

text: space

text: Θ

text: is

text: compact

text: and

text: convex.

text: Let

text: τ

text: sup

text: θ

text: The

text: θ

text: Θ

text: parameter

text: function

text: θ

text: (t)

text: takes

text: values

text: in

text: Θ,

text: and,

text: in

text: a

text: neighborhood

text: of

text: t

text: it

text: is

text: twice

text: contin-

text: uously

text: diﬀerentiable.

text: The

text: value

text: θ

text: (t

text: lies

text: in

text: the

text: interior

text: of

text: Θ.

text: We

text: continue

text: with

text: some

text: tail

text: conditions

text: on

text: f

text: (y)

text: and

text: its

text: derivatives.

text: They

text: are

text: fulﬁlled

text: if,

text: s

text: e.g.,

text: the

text: covariates

text: are

text: bounded.

text: For

text: µ-almost

text: all

text: y

text: (see

text: for

text: a

text: deﬁnition

text: of

text: µ),

text: the

text: density

text: f

text: (y)

text: is

text: twice

text: contin-

text: s

text: uously

text: diﬀerentiable

text: in

text: s.

text: For

text: an

text: open

text: neighborhood

text: U

text: of

text: t

text: and

text: U

text: [t

text: h,

text: t

text: h]

text: it

text: h

text: holds

text: for

text: all

text: pairs

text: (i,

text: j)

text: and

text: (k,

text: l)

text: d

text: sup

text: y

text: y

text: f

text: (y)

text: y

text: y

text: f

text: (y)

text: s∈U

text: s

text: ds

text: s

text: y

text: f

text: (y)

text: y

text: f

text: (y)

text: exp(τ

text: y

text: )dµ(y)

text: s

text: E

text: sup

text: X

text: (s)

text: X

text: n,ij

text: n,kl

text: s,t

text: U

text: h

text: eτ(

text: Xn,ij(s)

text: Xn,kl(t)

text: For

text: k

text: E

text: sup

text: (s)

text: keτ

text: C

text: (s)

text: C

text: (t

text: s

text: U

text: h

text: E

text: sup

text: s

text: U

text: h

text: eτ

text: C

text: (s)

text: ##LTLine##

text: ##LTLine##


text: The next assumption guarantees identiﬁability. (A5) θT X (t ) = 0 a.s. (w.r.t. f ) implies that θ = 0. n,12 0 t0 The following assumption addresses the asymptotic behavior of the distributions of the processes C (t). In particular, for t in a neighborhood of t , the assumptions address n,ij 0 asymptotic stability of the marginal distribut(cid:82)ions of these processes, and also a certain kind |{ } ∩ { }| of asymptotic independence of C and C for i, j k, l = 0. n,ij n,kl (A6) For w(u) = K(u) an(cid:90)d w(u) = K2(u)/ K2(v)dv it holds that P 1 (C (t + uh) = 1) → n,12 0 w(u) P du 1 (2.10) − (C (t ) = 1) 1 n,12 0 → ∞ for n . For (cid:90) (cid:90) A n,ij,kl P 1 1 (C (t + uh) = 1, C (t + vh) = 1) n,ij 0 n,kl 0 := w(u)w(v) P dudv, − − (C (t ) = 1)2 1 1 n,12 0  we assume that  |{ } ∩ { }|  o(n2) for i, j k, l = 2, |{ } ∩ { }| A = o(n) for i, j k, l = 1, (2.11) n,ij,kl |{ } ∩ { }| 1 + o(1) for i, j k, l = 0. Furthermore, it(cid:90)holds tha(cid:18)t (cid:19) − P T 1 s t (C (t ) = 0, C (s) = 1) 0 n,12 0 n,12 K P ds = O(h), (2.12) h h (C (t ) = 1) 0 n,12 0 |{ } ∩ { }| ≤ and for edges with i, j k, l 1 (cid:0) (cid:1) P (C (t ) = 1, C (t ) = 1) n,ij 0 n,kl 0 = O(1). (2.13) P 2 (C (t ) = 1) n,12 0 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: The

text: next

text: assumption

text: guarantees

text: identiﬁability.

text: θT

text: X

text: (t

text: a.s.

text: (w.r.t.

text: f

text: implies

text: that

text: θ

text: The

text: following

text: assumption

text: addresses

text: the

text: asymptotic

text: behavior

text: of

text: the

text: distributions

text: of

text: the

text: processes

text: C

text: (t).

text: In

text: particular,

text: for

text: t

text: in

text: a

text: neighborhood

text: of

text: t

text: the

text: assumptions

text: address

text: n,ij

text: asymptotic

text: stability

text: of

text: the

text: marginal

text: of

text: these

text: processes,

text: and

text: also

text: a

text: certain

text: kind

text: of

text: asymptotic

text: independence

text: of

text: C

text: and

text: C

text: for

text: i,

text: j

text: k,

text: l

text: n,ij

text: n,kl

text: For

text: w(u)

text: K(u)

text: w(u)

text: it

text: holds

text: that

text: P

text: (C

text: (t

text: uh)

text: w(u)

text: P

text: du

text: (C

text: (t

text: for

text: n

text: For

text: A

text: n,ij,kl

text: P

text: (C

text: (t

text: uh)

text: C

text: (t

text: vh)

text: n,ij

text: n,kl

text: w(u)w(v)

text: P

text: dudv,

text: (C

text: (t

text: we

text: assume

text: that

text: for

text: i,

text: j

text: k,

text: l

text: A

text: o(n)

text: for

text: i,

text: j

text: k,

text: l

text: n,ij,kl

text: for

text: i,

text: j

text: k,

text: l

text: Furthermore,

text: P

text: T

text: s

text: t

text: (C

text: (t

text: C

text: (s)

text: K

text: P

text: ds

text: O(h),

text: h

text: h

text: (C

text: (t

text: and

text: for

text: edges

text: with

text: i,

text: j

text: k,

text: l

text: P

text: (C

text: (t

text: C

text: (t

text: n,ij

text: n,kl

text: P

text: (C

text: (t

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Note that the exact travel vector of a is also uniquely determined by Q , by i t Lemma 8. 5.5 Three Agents Are Not Suﬃcient We now conclude our lower bound proof with Theorem 1. Roughly speaking, Lemma 11 certiﬁes that the behavior of the agents between any two subsequent occurrences of the same ﬁxed information tuple Q is reasonably similar. Since t there are only ﬁnitely many diﬀerent Q that actually occur, it follows that the t behavior of the agents loops, in a very informal sense. From this, we can derive a contradiction to the assumption that all cells are explored. Theorem 1. Three agents are not suﬃcient to explore the grid. Proof. Suppose for a contradiction that three agents suﬃce to explore the grid. From the deﬁnition of a travel meeting pair, it follows that there are points in ≤ ≤ time t < u t < u t < . . . such that (t , u ) is a travel meeting pair for 1≥ 1 2 2 3 (cid:48)j (cid:48)j ≥ (cid:48) any j 1 and for every travel meeting pair (t , u ) there is a j 1 with t = t (cid:48) j and u = u . j Recall the deﬁnition of Q in Lemma 11. Let T be suﬃciently large so that ≥ t T T holds (where T is just T for D = 1) and Lemmas 6, 7, 9 and 11 apply, 1 1 D ≥ and let k be an index such that t T and there is a h > k with Q = Q . k tk th Such a k must exist since there is only a ﬁnite number of tuples of the general form Q (after time T) and the number of traveling meeting pairs is inﬁnite, by t Lemma 5. Note that the ﬁniteness of the number of tuples, in particular the ﬁniteness of the (combinations of the) relative locations of the agents modulo (x, y), relies on the fact that the possible travel vectors after time T are restricted by Lemma 9. Consider the sequence ((t , u ), (t , u ), . . . , (t , u )) of traveling meeting k k k+1 k+1 h h − pairs, where h is the smallest index such that h > k holds, h k is even, and Q = Q . We examine the cells that are explored by the source agent for (t , u ) tk th k k between time t and t , by the destination agent for (t , u ) (which is the k k+1 k+1 k+1 same as the aforementioned source agent) between time t and t , and by k+1 k+2 the traveling agent for (t , u ) between time u and t . Then we iterate k+1 k+1 k+1 k+2 this examination, in each iteration increasing the indices by 2, and stop at time t . We say that the cells explored in the described way are explored during even h explorations. In the ﬁrst iteration, the explored cells are uniquely determined by the tuple Q and the exact location of the source agent for (t , u ) at time tk k k t , in the next iteration by the tuple Q and the exact location of the source k tk+2 agent for (t , u ) at time t , and so on. The tuples Q , Q , . . . are k+2 k+2 k+2 tk+2 tk+4 all uniquely determined by Q , and the locations of the respective source agents tk at times t , t , . . . are all uniquely determined by Q and the location of k+2 k+4 tk the source agent for (t , u ) at time t . Hence, the cells explored during an even k k k exploration between time t and t are uniquely determined by Q and the k h tk location of the source agent for (t , u ) at time t . k k k We obtain the following picture: The location of the source agent for (t , u ) k k at time t together with Q uniquely determines both Q and the location k tk th of the source agent for (t , u ) at time t , which, in turn, uniquely determine h h h Q and the location of the source agent for (t − , u − ) at time th+(h−k) h+(h k) h+(h k) t − , and so on. Hence, there is a vector (w, z) such that the locations h+(h k) of the respective source agents at times t , t , t − , t − , . . . are c, c + k h h+(h k) h+2(h k) 18 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Note

text: that

text: the

text: exact

text: travel

text: vector

text: of

text: a

text: is

text: also

text: uniquely

text: determined

text: by

text: Q

text: by

text: i

text: t

text: Lemma

text: Three

text: Agents

text: Are

text: Not

text: Suﬃcient

text: We

text: now

text: conclude

text: our

text: lower

text: bound

text: proof

text: with

text: Theorem

text: Roughly

text: speaking,

text: Lemma

text: certiﬁes

text: that

text: the

text: behavior

text: of

text: the

text: agents

text: between

text: any

text: two

text: subsequent

text: occurrences

text: of

text: the

text: same

text: ﬁxed

text: information

text: tuple

text: Q

text: is

text: reasonably

text: similar.

text: Since

text: t

text: there

text: are

text: only

text: ﬁnitely

text: many

text: diﬀerent

text: Q

text: that

text: actually

text: occur,

text: it

text: follows

text: that

text: the

text: t

text: behavior

text: of

text: the

text: agents

text: loops,

text: in

text: a

text: very

text: informal

text: sense.

text: From

text: this,

text: we

text: can

text: derive

text: a

text: contradiction

text: to

text: the

text: assumption

text: that

text: all

text: cells

text: are

text: explored.

text: Theorem

text: Three

text: agents

text: are

text: not

text: suﬃcient

text: to

text: explore

text: the

text: grid.

text: Proof.

text: Suppose

text: for

text: a

text: contradiction

text: that

text: three

text: agents

text: suﬃce

text: to

text: explore

text: the

text: grid.

text: From

text: the

text: deﬁnition

text: of

text: a

text: travel

text: meeting

text: pair,

text: it

text: follows

text: that

text: there

text: are

text: points

text: in

text: time

text: t

text: u

text: t

text: u

text: t

text: such

text: that

text: (t

text: u

text: is

text: a

text: travel

text: meeting

text: pair

text: for

text: 1≥

text: any

text: j

text: and

text: for

text: every

text: travel

text: meeting

text: pair

text: (t

text: u

text: there

text: is

text: a

text: j

text: with

text: t

text: t

text: j

text: and

text: u

text: u

text: j

text: Recall

text: the

text: deﬁnition

text: of

text: Q

text: in

text: Lemma

text: Let

text: T

text: be

text: suﬃciently

text: large

text: so

text: that

text: t

text: T

text: T

text: holds

text: (where

text: T

text: is

text: just

text: T

text: for

text: D

text: and

text: Lemmas

text: and

text: apply,

text: D

text: and

text: let

text: k

text: be

text: an

text: index

text: such

text: that

text: t

text: T

text: and

text: there

text: is

text: a

text: h

text: k

text: with

text: Q

text: Q

text: k

text: tk

text: th

text: Such

text: a

text: k

text: must

text: exist

text: since

text: there

text: is

text: only

text: a

text: ﬁnite

text: number

text: of

text: tuples

text: of

text: the

text: general

text: form

text: Q

text: (after

text: time

text: T)

text: and

text: the

text: number

text: of

text: traveling

text: meeting

text: pairs

text: is

text: inﬁnite,

text: by

text: t

text: Lemma

text: Note

text: that

text: the

text: ﬁniteness

text: of

text: the

text: number

text: of

text: tuples,

text: in

text: particular

text: the

text: ﬁniteness

text: of

text: the

text: (combinations

text: of

text: the)

text: relative

text: locations

text: of

text: the

text: agents

text: modulo

text: (x,

text: y),

text: relies

text: on

text: the

text: fact

text: that

text: the

text: possible

text: travel

text: vectors

text: after

text: time

text: T

text: are

text: restricted

text: by

text: Lemma

text: Consider

text: the

text: sequence

text: ((t

text: u

text: (t

text: u

text: (t

text: u

text: of

text: traveling

text: meeting

text: k

text: k

text: h

text: h

text: pairs,

text: where

text: h

text: is

text: the

text: smallest

text: index

text: such

text: that

text: h

text: k

text: holds,

text: h

text: k

text: is

text: even,

text: and

text: Q

text: Q

text: We

text: examine

text: the

text: cells

text: that

text: are

text: explored

text: by

text: the

text: source

text: agent

text: for

text: (t

text: u

text: tk

text: th

text: k

text: k

text: between

text: time

text: t

text: and

text: t

text: by

text: the

text: destination

text: agent

text: for

text: (t

text: u

text: (which

text: is

text: the

text: k

text: same

text: as

text: the

text: aforementioned

text: source

text: agent)

text: between

text: time

text: t

text: and

text: t

text: and

text: by

text: the

text: traveling

text: agent

text: for

text: (t

text: u

text: between

text: time

text: u

text: and

text: t

text: Then

text: we

text: iterate

text: this

text: examination,

text: in

text: each

text: iteration

text: increasing

text: the

text: indices

text: by

text: and

text: stop

text: at

text: time

text: t

text: We

text: say

text: that

text: the

text: cells

text: explored

text: in

text: the

text: described

text: way

text: are

text: explored

text: during

text: even

text: h

text: explorations.

text: In

text: the

text: ﬁrst

text: iteration,

text: the

text: explored

text: cells

text: are

text: uniquely

text: determined

text: by

text: the

text: tuple

text: Q

text: and

text: the

text: exact

text: location

text: of

text: the

text: source

text: agent

text: for

text: (t

text: u

text: at

text: time

text: tk

text: k

text: k

text: t

text: in

text: the

text: next

text: iteration

text: by

text: the

text: tuple

text: Q

text: and

text: the

text: exact

text: location

text: of

text: the

text: source

text: k

text: agent

text: for

text: (t

text: u

text: at

text: time

text: t

text: and

text: so

text: on.

text: The

text: tuples

text: Q

text: Q

text: are

text: all

text: uniquely

text: determined

text: by

text: Q

text: and

text: the

text: locations

text: of

text: the

text: respective

text: source

text: agents

text: tk

text: at

text: times

text: t

text: t

text: are

text: all

text: uniquely

text: determined

text: by

text: Q

text: and

text: the

text: location

text: of

text: tk

text: the

text: source

text: agent

text: for

text: (t

text: u

text: at

text: time

text: t

text: Hence,

text: the

text: cells

text: explored

text: during

text: an

text: even

text: k

text: k

text: k

text: exploration

text: between

text: time

text: t

text: and

text: t

text: are

text: uniquely

text: determined

text: by

text: Q

text: and

text: the

text: k

text: h

text: tk

text: location

text: of

text: the

text: source

text: agent

text: for

text: (t

text: u

text: at

text: time

text: t

text: k

text: k

text: k

text: We

text: obtain

text: the

text: following

text: picture:

text: The

text: location

text: of

text: the

text: source

text: agent

text: for

text: (t

text: u

text: k

text: k

text: at

text: time

text: t

text: together

text: with

text: Q

text: uniquely

text: determines

text: both

text: Q

text: and

text: the

text: location

text: k

text: tk

text: th

text: of

text: the

text: source

text: agent

text: for

text: (t

text: u

text: at

text: time

text: t

text: which,

text: in

text: turn,

text: uniquely

text: determine

text: h

text: h

text: h

text: Q

text: and

text: the

text: location

text: of

text: the

text: source

text: agent

text: for

text: (t

text: u

text: at

text: time

text: th+(h−k)

text: h+(h

text: k)

text: h+(h

text: k)

text: t

text: and

text: so

text: on.

text: Hence,

text: there

text: is

text: a

text: vector

text: (w,

text: z)

text: such

text: that

text: the

text: locations

text: h+(h

text: k)

text: of

text: the

text: respective

text: source

text: agents

text: at

text: times

text: t

text: t

text: t

text: t

text: are

text: c,

text: c

text: k

text: h

text: h+(h

text: k)

text: k)

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 3 2 3 2 4 1 4 1 4 4 4 3 3 4 1 1 1 2 2 1 3 2 3 2 4 1 3 2 4 4 4 3 4 4 1 1 1 2 1 1 3 2 3 2 3 2 3 2 Figure 3: The outcome of a mirroring above a diagonal. In the ﬁgure, the circles represent the cells of the grid and the edges denote the ports connecting the cells. (cid:48) a a Figure 4: Let a be an agent traveling according to a horizontal travel vector (cid:48) towards a . To ﬁnd a suitable spot for the diagonal below which we mirror, denoted by the dashed black line, we ﬁnd intersections of vertical and diagonal lines that could potentially lead to some agent, denoted by the blue and red areas. Given that the band according to which a travels is long enough, we can always guarantee the existence of a safe subband, denoted by the black area. (cid:48) For the diagonal case, consider two adjacent cells c and c that are both aﬀected and let us assume that these cells are connected through ports 1 and 4. According to the deﬁnition of the mirroring, either both ports are changed (to 2 and 3, respectively) or they remain unchanged. The remaining case is shown analogously and thus, the claim follows. 6.1 Agents Cannot Travel Alone Without a Compass In the following lemma, we show that an agent without a compass cannot travel alone. Assuming that this agent has to travel a long distance without any agents nearby, we can use mirroring to change the port numbering, and thereby changing the travel vector, which leads to not meeting any agent anymore. We will use the schedule deﬁned in the three agent case, adjusted so that the fourth agent is always scheduled after the other three. Please refer to Figure 4 for an illustration of the following lemma. Lemma 13. Assume that agent a is scheduled until a meets another agent and a has a non-zero travel vector. Additionally, assume that the distance from a to any other agent is more than 16N3 + 12N. Then, there is a mirroring operation 20 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Figure

text: The

text: outcome

text: of

text: a

text: mirroring

text: above

text: a

text: diagonal.

text: In

text: the

text: ﬁgure,

text: the

text: circles

text: represent

text: the

text: cells

text: of

text: the

text: grid

text: and

text: the

text: edges

text: denote

text: the

text: ports

text: connecting

text: the

text: cells.

text: a

text: a

text: Figure

text: Let

text: a

text: be

text: an

text: agent

text: traveling

text: according

text: to

text: a

text: horizontal

text: travel

text: vector

text: towards

text: a

text: To

text: ﬁnd

text: a

text: suitable

text: spot

text: for

text: the

text: diagonal

text: below

text: which

text: we

text: mirror,

text: denoted

text: by

text: the

text: dashed

text: black

text: line,

text: we

text: ﬁnd

text: intersections

text: of

text: vertical

text: and

text: diagonal

text: lines

text: that

text: could

text: potentially

text: lead

text: to

text: some

text: agent,

text: denoted

text: by

text: the

text: blue

text: and

text: red

text: areas.

text: Given

text: that

text: the

text: band

text: according

text: to

text: which

text: a

text: travels

text: is

text: long

text: enough,

text: we

text: can

text: always

text: guarantee

text: the

text: existence

text: of

text: a

text: safe

text: subband,

text: denoted

text: by

text: the

text: black

text: area.

text: For

text: the

text: diagonal

text: case,

text: consider

text: two

text: adjacent

text: cells

text: c

text: and

text: c

text: that

text: are

text: both

text: aﬀected

text: and

text: let

text: us

text: assume

text: that

text: these

text: cells

text: are

text: connected

text: through

text: ports

text: and

text: According

text: to

text: the

text: deﬁnition

text: of

text: the

text: mirroring,

text: either

text: both

text: ports

text: are

text: changed

text: (to

text: and

text: respectively)

text: or

text: they

text: remain

text: unchanged.

text: The

text: remaining

text: case

text: is

text: shown

text: analogously

text: and

text: thus,

text: the

text: claim

text: follows.

text: Agents

text: Cannot

text: Travel

text: Alone

text: Without

text: a

text: Compass

text: In

text: the

text: following

text: lemma,

text: we

text: show

text: that

text: an

text: agent

text: without

text: a

text: compass

text: cannot

text: travel

text: alone.

text: Assuming

text: that

text: this

text: agent

text: has

text: to

text: travel

text: a

text: long

text: distance

text: without

text: any

text: agents

text: nearby,

text: we

text: can

text: use

text: mirroring

text: to

text: change

text: the

text: port

text: numbering,

text: and

text: thereby

text: changing

text: the

text: travel

text: vector,

text: which

text: leads

text: to

text: not

text: meeting

text: any

text: agent

text: anymore.

text: We

text: will

text: use

text: the

text: schedule

text: deﬁned

text: in

text: the

text: three

text: agent

text: case,

text: adjusted

text: so

text: that

text: the

text: fourth

text: agent

text: is

text: always

text: scheduled

text: after

text: the

text: other

text: three.

text: Please

text: refer

text: to

text: Figure

text: for

text: an

text: illustration

text: of

text: the

text: following

text: lemma.

text: Lemma

text: Assume

text: that

text: agent

text: a

text: is

text: scheduled

text: until

text: a

text: meets

text: another

text: agent

text: and

text: a

text: has

text: a

text: non-zero

text: travel

text: vector.

text: Additionally,

text: assume

text: that

text: the

text: distance

text: from

text: a

text: to

text: any

text: other

text: agent

text: is

text: more

text: than

text: Then,

text: there

text: is

text: a

text: mirroring

text: operation

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: to the speciﬁcation of our initialization procedure. Given that the simulation method always visits all the cells visited by the simulated agents, the two things left to show are that, 1) every agent in the three agent protocol has all the information to simulate the corresponding agent(s) in the four agent protocol, and 2) for every agent in the four agent protocol, inﬁnitely many steps are simulated. Otherwise, the four agent schedule that is simulated would not adhere to the speciﬁcations of a schedule. For the ﬁrst property, the information needed to simulate a step of the four agent protocol is the state and the location of the simulated agent, and the information of what other agents are in the same cell as the simulated agent, and in what states they are. Since the simulating agent always knows the location(s) of the agent(s) it simulates, and before simulating a step, it gathers the data about any nearby simulated agent(s) during the checking phase, we get the ﬁrst property. For property 2), note that in the three agent schedule, any agent gets scheduled inﬁnitely often. Furthermore, once agent α starts the checking phase, it will execute a simulation step latest in the following subschedule of its own: If the subschedule of α is stopped by meeting another agent during the checking, the other agent will end its subschedule in at most one time step letting α ﬁnish the simulation. Thus, the only obstacle could be that some agent α will be prevented from starting a checking phase by, always at the start of its subschedule, sharing its cell with an agent β performing the checking. However, since the simulation performed by β lasts until the simulated agent(s) either meet(s) some agent or enter(s) the same state cell combination again, it has to be the case that after a ﬁnite amount of time steps, either the distance between β and α is larger than the checking radius or at least one of the agents simulated by β meets one of the agents simulated by α upon which the subschedule of β ends. This ﬁnishes the proof. The following theorem follows by combining Lemma 14 and Theorem 1. Theorem 4. Four asynchronous agents do not suﬃce to explore the grid in the port numbering model. 7 Five Agent Compass-Free Protocol In this section, we show a matching upper bound to the lower bound result yielded by Theorem 4. The main underlying technique is to locally simulate a compass using two agents and thus, being able to move to some speciﬁc direction. Roughly speaking, the idea is to encode one of the cardinal directions in the relative positions of the agents and after every movement, ensure that this encoding is not broken. Note that given the lack of compass, the agents do not know which of the actual cardinal directions they have encoded. The diﬃculty lies in the lack of “proper” local vision, i.e., the two agents have to ensure that they can always ﬁnd their way back to their companion using the very limited memory. Throughout, our protocols can be implemented asynchronously. To break the ties of which agent performs their actions in which order, we can put encode 24 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: to

text: the

text: speciﬁcation

text: of

text: our

text: initialization

text: procedure.

text: Given

text: that

text: the

text: simulation

text: method

text: always

text: visits

text: all

text: the

text: cells

text: visited

text: by

text: the

text: simulated

text: agents,

text: the

text: two

text: things

text: left

text: to

text: show

text: are

text: that,

text: every

text: agent

text: in

text: the

text: three

text: agent

text: protocol

text: has

text: all

text: the

text: information

text: to

text: simulate

text: the

text: corresponding

text: agent(s)

text: in

text: the

text: four

text: agent

text: protocol,

text: and

text: for

text: every

text: agent

text: in

text: the

text: four

text: agent

text: protocol,

text: inﬁnitely

text: many

text: steps

text: are

text: simulated.

text: Otherwise,

text: the

text: four

text: agent

text: schedule

text: that

text: is

text: simulated

text: would

text: not

text: adhere

text: to

text: the

text: speciﬁcations

text: of

text: a

text: schedule.

text: For

text: the

text: ﬁrst

text: property,

text: the

text: information

text: needed

text: to

text: simulate

text: a

text: step

text: of

text: the

text: four

text: agent

text: protocol

text: is

text: the

text: state

text: and

text: the

text: location

text: of

text: the

text: simulated

text: agent,

text: and

text: the

text: information

text: of

text: what

text: other

text: agents

text: are

text: in

text: the

text: same

text: cell

text: as

text: the

text: simulated

text: agent,

text: and

text: in

text: what

text: states

text: they

text: are.

text: Since

text: the

text: simulating

text: agent

text: always

text: knows

text: the

text: location(s)

text: of

text: the

text: agent(s)

text: it

text: simulates,

text: and

text: before

text: simulating

text: a

text: step,

text: it

text: gathers

text: the

text: data

text: about

text: any

text: nearby

text: simulated

text: agent(s)

text: during

text: the

text: checking

text: phase,

text: we

text: get

text: the

text: ﬁrst

text: property.

text: For

text: property

text: note

text: that

text: in

text: the

text: three

text: agent

text: schedule,

text: any

text: agent

text: gets

text: scheduled

text: inﬁnitely

text: often.

text: Furthermore,

text: once

text: agent

text: α

text: starts

text: the

text: checking

text: phase,

text: it

text: will

text: execute

text: a

text: simulation

text: step

text: latest

text: in

text: the

text: following

text: subschedule

text: of

text: its

text: own:

text: If

text: the

text: subschedule

text: of

text: α

text: is

text: stopped

text: by

text: meeting

text: another

text: agent

text: during

text: the

text: checking,

text: the

text: other

text: agent

text: will

text: end

text: its

text: subschedule

text: in

text: at

text: most

text: one

text: time

text: step

text: letting

text: α

text: ﬁnish

text: the

text: simulation.

text: Thus,

text: the

text: only

text: obstacle

text: could

text: be

text: that

text: some

text: agent

text: α

text: will

text: be

text: prevented

text: from

text: starting

text: a

text: checking

text: phase

text: by,

text: always

text: at

text: the

text: start

text: of

text: its

text: subschedule,

text: sharing

text: its

text: cell

text: with

text: an

text: agent

text: β

text: performing

text: the

text: checking.

text: However,

text: since

text: the

text: simulation

text: performed

text: by

text: β

text: lasts

text: until

text: the

text: simulated

text: agent(s)

text: either

text: meet(s)

text: some

text: agent

text: or

text: enter(s)

text: the

text: same

text: state

text: cell

text: combination

text: again,

text: it

text: has

text: to

text: be

text: the

text: case

text: that

text: after

text: a

text: ﬁnite

text: amount

text: of

text: time

text: steps,

text: either

text: the

text: distance

text: between

text: β

text: and

text: α

text: is

text: larger

text: than

text: the

text: checking

text: radius

text: or

text: at

text: least

text: one

text: of

text: the

text: agents

text: simulated

text: by

text: β

text: meets

text: one

text: of

text: the

text: agents

text: simulated

text: by

text: α

text: upon

text: which

text: the

text: subschedule

text: of

text: β

text: ends.

text: This

text: ﬁnishes

text: the

text: proof.

text: The

text: following

text: theorem

text: follows

text: by

text: combining

text: Lemma

text: and

text: Theorem

text: Theorem

text: Four

text: asynchronous

text: agents

text: do

text: not

text: suﬃce

text: to

text: explore

text: the

text: grid

text: in

text: the

text: port

text: numbering

text: model.

text: Five

text: Agent

text: Compass-Free

text: Protocol

text: In

text: this

text: section,

text: we

text: show

text: a

text: matching

text: upper

text: bound

text: to

text: the

text: lower

text: bound

text: result

text: yielded

text: by

text: Theorem

text: The

text: main

text: underlying

text: technique

text: is

text: to

text: locally

text: simulate

text: a

text: compass

text: using

text: two

text: agents

text: and

text: thus,

text: being

text: able

text: to

text: move

text: to

text: some

text: speciﬁc

text: direction.

text: Roughly

text: speaking,

text: the

text: idea

text: is

text: to

text: encode

text: one

text: of

text: the

text: cardinal

text: directions

text: in

text: the

text: relative

text: positions

text: of

text: the

text: agents

text: and

text: after

text: every

text: movement,

text: ensure

text: that

text: this

text: encoding

text: is

text: not

text: broken.

text: Note

text: that

text: given

text: the

text: lack

text: of

text: compass,

text: the

text: agents

text: do

text: not

text: know

text: which

text: of

text: the

text: actual

text: cardinal

text: directions

text: they

text: have

text: encoded.

text: The

text: diﬃculty

text: lies

text: in

text: the

text: lack

text: of

text: “proper”

text: local

text: vision,

text: i.e.,

text: the

text: two

text: agents

text: have

text: to

text: ensure

text: that

text: they

text: can

text: always

text: ﬁnd

text: their

text: way

text: back

text: to

text: their

text: companion

text: using

text: the

text: very

text: limited

text: memory.

text: Throughout,

text: our

text: protocols

text: can

text: be

text: implemented

text: asynchronously.

text: To

text: break

text: the

text: ties

text: of

text: which

text: agent

text: performs

text: their

text: actions

text: in

text: which

text: order,

text: we

text: can

text: put

text: encode

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##