11institutetext: UMR MIA-Paris, AgroParisTech, INRAe, Université Paris-Saclay,
France
22institutetext: Orange Labs, 44 Avenue de la république, Châtillon, France

#  Early Classification of Time Series is Meaningful

Youssef Achenchabe 1122 Alexis Bondu 22
Antoine Cornuéjols 11 and Vincent Lemaire 22

###### Abstract

Many approaches have been proposed for early classification of time series in
light of its significance in a wide range of applications including
healthcare, transportation and finance. However, recently a preprint saved on
Arxiv claims that all research done for almost 20 years now on the Early
Classification of Time Series is useless, or, at the very least, ill-oriented
because severely lacking a strong ground. In this paper, we answer in detail
the main issues and misunderstandings raised, and propose directions to
further expand the fields of application of early classification of time
series.

###### Keywords:

early classification cost estimation online decision making

##  1 Introduction

An increasing number of applications require to recognize the class of an
incoming time series as quickly as possible without unduly compromising the
accuracy of the prediction [30, 2, 24, 10, 28, 14, 8]. For example, in
emergency wards of hospitals [17], in control rooms of national or
international electrical power grids, in government councils assessing
emergency situations, in all kinds of contexts, it is essential to make timely
decisions in absence of complete knowledge of the true outcome (e.g. should
the patient undergo a risky surgical operation?). The issue facing the
decision makers is that, usually, the longer the decision is delayed, the
clearer is the likely outcome (e.g. the critical or not critical state of the
patient) but, also, the higher the cost that will be incurred if only because
earlier decisions allow one to be better prepared. How to optimize online the
tradeoff between the earliness and the accuracy of the decision is the object
of the Early Classification of Time Series problem (ECTS).

To the best of our knowledge, [3] is the earliest paper explicitly mentioning
“classification when only part of the series are presented to the classifier”,
and the main thrust of it is to show how the boosting method can be employed
to the classification of incomplete time series.

The ECTS community has produced a large diversity of models that can predict
the class of incoming subsequence, after only seeing a fraction of the data.
This community has published his work on diverse venues in prestigious
conferences or journals [26, 33, 25, 11, 19, 22, 9, 18, 20, 31, 29, 16, 4, 35,
15, 13, 27, 1, 34]. Thus, step after step, this community is doing progress
towards solving this interesting problem.

However, a recent preprint [32] essentially claims that all research done for
almost 20 years now on the Early Classification of Time Series is useless, or,
at the very least, ill-oriented because severely lacking a strong ground.

##  2 Arguments against ECTS

Once [32] dissected and the line of reasoning made apparent, in fact, the
critic laid down in the paper boils down to three arguments:

  1. 1.

The paper exhibits cases where early classification of time series is doomed
to lead to numerous false positives and false negatives, so as to be
effectively useless. The paper claims that this must be the general case. The
fact that no real application is to be found in the scientific litterature, so
it is said, is a testimony of the fact that ECTS is a false problem.

  2. 2.

The research conducted on ECTS has mostly, if not exclusively, used the UCR
repository, and hence has produced results that are misleading. There would be
three reasons for this. First, the UCR datasets contain only time series of
the same length and starting at the same time. This is hardly what can be
expected in the real world. Second, most of the time series in these datasets
can be classified observing only their starting subsequence. This would credit
ECTS systems with classification performances that are unearned. And third,
the authors claim that most ECTS system require a z-normalization of the data,
which can only be obtained afterwards and thus removes all relevance to making
early classification in the first place.

  3. 3.

Since, it is easy to obtain similar performances as ECTS systems with just
fumbling a little bit with the data and using classical time series
classification algorithms, it is not worth resorting to the overhead of ECTS
systems.

Let us consider each argument in turn.

##  3 Discussion

###  3.1 ECTS is a false and flawed problem

It is interesting that Evolution has not entirely wiped out this argument.
Every creature on earth who said to itself “Ah, I see an animal in that tree
that looks like a feline, a leopard maybe or a saber-toothed tiger, but I’m
not sure. It’s partly hidden in the foliage. Funny, these movements, maybe
it’s getting ready to jump in my direction. It’s not completely clear though.
Would it want to eat me? Maybe I’m wrong. Let’s wait to find out more. Early
danger classification is a false problem, a recent paper stated’’ must be dead
and without descendant. In the wild, animals behave appropriately by fleeing
at the right moment in front of a predator, by finding a compromise between
the earliness and the accuracy of their decision. To illustrate this
compromise, an animal should not flee at the slightest noise because it would
waste its energy most of the time, and it should flee before its decision is
completely confident, i.e. when the predator is fully visible and pouncing on
it. Optimizing such a compromise is the essence of ECTS.

In [32] the authors of the paper make the point that it is actually a very
risky enterprise to classify time series on the basis of a starting
subsequence since, so they argue, it is so common that such subsequences are
followed by different continuations. But here, the argument is flawed on two
accounts at least.

First, the particular examples presented by the authors do not constitute
evidence validating their point of view in its generality, but only a
confirmation bias in order to support author’s prior beliefs. In particular,
the metaphor drawing a parallel between the ECTS and word recognition in
textual data distorts the problem111In the case of ECTS, labels are assigned
to an entire time series, which has a beginning and an end. Moreover, the
class is not necessarily defined by a local pattern to be found., which does
not help the reader to correctly understand the ECTS. The example from
Levicitus 2:1 is reductive and far-fetched. Certainly, there are many examples
of words that share subparts, but ECTS is not reduced to that. Definitely,
such examples do not constitute a proof that “the space of possible domains
where ECTS could be meaningly applied is vanishingly small” as authors claim.
And even if that was the case, remember that general relativity was long
believed to have no practical applications until the GPS appeared. Now, we
could simply not do without general relativity. But this is not the major
shortcoming of the critic addressed by the authors.

The second shortcoming is that ECTS systems are designed to learn from
training data that potentially includes ambiguous examples, but this point
does not seem to be addressed in [32]. When such ambiguous examples in the
input signal, these systems just wait to have more information before making
their decision. So, if indeed the syllables “cat” on one hand, and “dog” on
the other hand, are shared by different words that appear statistically often,
like “catalog” and “cattle” or “dogmatic” and “doggedly”, then these systems
will simply not base their decisions on these syllables alone. That’s all
there is to it.

In a way, we can liken the work on ECTS to what is studied in control theory
[6, 5]. Control theory is concerned as well with online decision making. This
is the case with anti-aircraft guns that must point ahead of the plane in
order to hit it. And the farther away is the plane from the gun, the more
ahead of the plane should the pointing be. Here also, the plane could try to
evade the antigun shots by changing its trajectory. The very same course can
be followed by different ones. Does that render control theory useless? Notice
that a whole lot of standard rules in control theory use as well integration
of measurements over some time interval, thus taking stock of the past to take
decisions, exactly as ECTS does. Early classification of time series goes one
step further though, and tries to learn second order knowledge. The idea is to
learn when there will be enough information to decide in such a way as to
optimize both the expectation of the misclassification cost and the cost
associated with delaying the decision.

At this point, it is interesting to discuss what the authors [32] believe is a
counter example of the usefulness of ECTS. They dispute the usefulness of a
early warning system in hospitals which would be able to detect early on
abnormal ECG, because, so they say, these systems would only bring a gain of
at most seconds in detection when surgical operations often take days to be
planned. This just points out that, in this context, the cost of delaying
decision is in fact very low. And, in consequence, there is no need to hurry
the classification of time series. In other contexts, such as planning the
start-up of thermal power plants from consumption measurements to face a peak
of consumption on the day, gaining just one half an hour can be critical. So,
this is not the ECTS systems that are at fault. Their added value depends both
on the misclassification costs and the cost associated with delaying the
decision. If the later is low, then the best course of action can be to wait
for all information to be available before committing to a decision.

The thing is though, that it is not always clear that all the information is
available. Everyday, we have to take decisions from incomplete information.
For instance, I decide to sit on this brown contraption of which I see only
two legs because my past history of encounters with such things leads me to
predict that it is a chair. Should I bother to control that all four legs are
indeed present each time I plan to seat on what appears to be a chair, but may
be not? We make such inferences all the time from incomplete information with
the risk of course to make faulty interpretations and predictions. Should we
stop doing this222In [32], as of the date 03-02-2021 “the community should
stop publishing on this topic”., as the authors of the paper seem to imply and
demand? Would that only be possible? Would this even be viable?

As Machine Learning will gain in prominence and be employed in all facets of
life, learning under budget constraints will become quite a significant topic.
Reducing the number of measurements can be crucial in some applications, and
this is what gives so much value to innovative methods like compressive
sensing [7]. ECTS belongs to this family of methods that seek to be
parsimonious in the measurements they need.

###  3.2  The research has been ill-oriented because of the almost exclusive
use of UCR time series

We think claim that this line of criticism is circumstantial and does not put
into question the validity of the interest for ECTS. One reason for using the
UCR datasets is simply that everyone does this, and that it helps making
comparisons between the various proposed approaches.

Another reason is that, in fact, applications where ECTS is useful exist [30,
2, 24, 10, 28, 14, 8] but they have still to realize their full potential.
Companies are becoming more and more aware of the problem and are now starting
to integrate ECTS into their projects.

Let us now discuss the objections made in turn. The first one is that the UCR
datasets contain only time series of the same length and starting at the same
time. This indeed facilitates the task of devising and learning classifiers
that make predictions given some part of the time series. But it must be said
that the point of ECTS is not to devise new classifiers, or classifiers that
are particularly effective. The problem instead is to take existing
classifiers and look at ways to define a criterion that combines the
misclassification costs and delay cost, and then to devise ways to optimize
it. A fair comparison between ECTS methods must therefore use the very same
classifiers. Now, if datasets exist where time series are not of the same
length and same starting point, this would indeed be interesting, but
comparisons of ECTS methods would still require that the same classifiers be
used, here classifiers able to deal with these other scenario.

Another objection is that numerous of the oldest methods of classification of
time series imply the use of distances such as the Euclidian distance or DTW
which are quite sensitive to the fact that the data has been z-normalized333
The use of such data is explained by the fact that the first research works on
ECTS first exploited methods based on distances or similarity measures, like
K-Nearest Neighbor, etc. For this reason, some of the UCR data donors have
provided pre-normalized datasets.. Because z-normalization is based on the
knowledge of the whole time series, this means that the start of a time series
“leaks” information about its remaining part, and this in turn biases the
performances that are reported for some ECTS systems. This interesting remark,
while casting doubts on the absolute performance reported for some ECTS
systems, does not however condemn the whole field of ECTS since many methods
do not require this normalization (e.g. SR [20], Economy-$\gamma$ [1] and all
other approaches that do not use a similarity measure). In addition, more and
more datasets are now put in UCR and in other data bases which are not
z-normalized a priori. It is recommended that the community exclude the few
z-normalized datasets from the reference benchmark to compare ECTS approaches.

Finally, [32] observes that most of the time series in these datasets can be
classified observing only their starting subsequence. This would allow ECTS
systems to be credited with unearned classification performance. Again, the
point of the research in ECTS is not to show that it is possible to label time
series given some starting (small) subsequences. It is to show that the
combined misclassification cost and delay cost can be lowered using ECTS. This
is what must be evaluated. Believing that what counts is the proportion of the
time series needed to label it, is a misunderstanding of the ECTS problem.

###  3.3 It is not worth resorting to the overhead of ECTS systems

This is an interesting question. If ECTS claims to take into account the delay
cost in the classification problem, which is not considered classically, then
it would only seem fair to take also into account the cost of using the
machinery needed to perform ECTS. So, what are the overheads implied with ECTS
systems?

Let us take a very recent system, which explicitly optimizes the combined
misclassification cost and delay cost in a non myopic manner, that is by
predicting at each time step what is the expected best instant to make a
decision, and which exhibits state of the art performances [1].

There, the cost of using this system is entailed by:

  * •

training $N$ classifiers, when the length of the time series is divided into
$N$ intervals. Thus, a classifier $h_{i}(i\in\\{1,\ldots,N\\})$ is trained to
label time series when the first $i$ time intervals are provided.

  * •

computing groups of time series. In [1], it is shown that this can be done in
several ways, supervised or unsupervised.

These steps are performed during training. They therefore not entail cost
during recognition.

When in use, at the time interval $i$, the cost comes from the evaluation of
the future combined cost for all remaining $N-i$ time steps. This evaluation
is fast, involving assigning the incoming time series to a group of time
series, and then estimating the expected misclassification cost in this group
and the delay cost, which is a function of time. If the time seems optimal to
take a decision, then the incoming time series is labeled according to the
current classifier.

The overhead incurred during recognition is therefore quite low. And all the
process is automated, while what [32] describe as “this took common sense and
a few minutes of low-code exploration of the data” in order to be able to
label time series with some prefix subsequence does not guarantee the quality
of the result in any quantitative way, and certainly not the optimization of
the combined misclassification cost and delay cost.

##  4 Sum up

Our artificial classification systems, as ourselves, must perform inferences
from incomplete and ambiguous input data all the time. The problem is to act
as well as possible given this limited information. ECTS goes one step
further. It tries to estimate when misclassification costs combined with a
delay cost can be optimized. Note that the delay cost can include the cost of
acquiring one more measurement. This is thus a very significant line of
research. Giving examples where early classification of time series is risky
does not provide evidence of the uselessness of ECTS. These systems would
detect the high risk of misclassification given the sparse information
provided and would balance it against the cost of delaying decision. If the
delay cost is low enough, they would wait for more measurements. Otherwise,
they would take the (high) risk of miclassification because it is still less
than the cost of delaying decision.

That the research carried out so far has not lead to applications is to our
opinion a mistaken critic [30, 2, 24, 10, 28, 14, 8]. Real applications are:
i) either hidden from the academic world because of their sensitive nature;
ii) or under development, as this is a relatively new problem whose awareness
is recent. Furthermore, it is fortunate that entire fields of research have
not been terminated in the past because of the apparent lack of potential
applications. We would still be relying on Chappe’s telegraph to exchange
information at distance, since Maxwell’s research on electromagnetism was
deemed to be without any concrete applications. And we would not have
computers because Turing’s early research was completely abstract.

Finally, the current stance on using datasets with special properties (i.e.
the UCR dataset), while being worth of warnings, does not condemn the field to
a very limited set of applications. It was necessary to test the various
methods on a shared test bed. ECTS is now moving toward new questions, for
example early detection of anomalies in data streams. Recent papers propose
solid formalizations of the ECTS problem [1, 21, 23, 12], which are not
considered in the state of the art presented in [32] that is biased towards
oldest works related to ECTS.

##  5 Conclusion and open challenges

Early Classification of Time Series is definitely a meaningful problem for
several reasons. First, numerous applications require ECTS, and all organisms
on Earth are confronted to this problem. Saying that this is too hard a
problem and therefore that research efforts aimed at it are worthless amounts
to renouncing to do science. Besides, the main criticism raised by Wu et al.
[32] about the high risk of misclassification in ECTS is not new. This is the
issue ever present in supervised learning. The problem is to learn what is
relevant, or discriminant, in the input signal and what is not or what is
ambiguous. The novelty in ECTS is that, at test time, a tradeoff between the
leisure to take as much information as possible before making a classification
and a cost for waiting has to be solved. Directly confronting the problem has
been shown to increase the performance as compared to approaches that do not.

ECTS raises interesting problems that can be matched with problems in control
theory. As in control theory, decisions have to be made online and must take
into account what is the most likely future given what is known about the
past, but, in addition, ECTS seeks to anticipate the best moment to take a
decision under delay costs.

There are also other open challenges and future topics of research in early
classification as for example: (i) extend ECTS to the classification of
portions of data streams (e.g.: to tackle predictive maintenance, or anomaly
detection usecases); (ii) extend ECTS to revocable decisions allowing to
correct a bad decision when the recent measurements suggest that the predicted
class is wrong (e.g.: useful for monitoring systems); (iii) extend ECTS to
unsupervised or weakly supervised learning tasks (e.g. outliers or anomaly
detection). These three points open interesting research perspectives that
would allow to redefine and extend the ECTS problem, and therefore to further
expand its fields of application. To conclude, we consider that ECTS is a
well-defined problem thanks to the years of sustained work in this field [1,
21, 23, 12]. We encourage the scientific community to work on ECTS, as we are
convinced that it is a promising area.

## References

  * [1] Achenchabe, Y., Bondu, A., Cornuéjols, A.: Early classification of time series. cost-based optimization criterion and algorithms. Mach Learn (2021)
  * [2] Alipour-Fanid, A., Dabaghchian, M., Wang, N., Wang, P., Zhao, L., Zeng, K.: Machine learning-based delay-aware uav detection over encrypted wi-fi traffic. In: 2019 IEEE Conference on Communications and Network Security (CNS). pp. 1–7. IEEE (2019)
  * [3] Alonso González, C.J., Diez, J.J.R.: Boosting interval-based literals: Variable length and early classification. In: Data mining in time series databases, pp. 149–171. World Scientific (2004)
  * [4] Anderson, H.S., Parrish, N., Tsukida, K., Gupta, M.: Early time-series classification with reliability guarantee. Sandria Report (2012)
  * [5] Bellman, R.: Control theory. Scientific American 211(3), 186–201 (1964)
  * [6] Bennett, S.: A history of control engineering, 1930-1955. No. 47, IET (1993)
  * [7] Candes, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 59(8), 1207–1223 (2006)
  * [8] Dachraoui, A., Bondu, A., Cornuejols, A.: Early classification of individual electricity consumptions. RealStream2013 (ECML) pp. 18–21 (2013)
  * [9] Dachraoui, A., Bondu, A., Cornuéjols, A.: Early classification of time series as a non myopic sequential decision making problem. In: Appice, A., Rodrigues, P.P., Santos Costa, V., Soares, C., Gama, J., Jorge, A. (eds.) Machine Learning and Knowledge Discovery in Databases. pp. 433–447. Springer International Publishing, Cham (2015)
  * [10] Fahrenkrog-Petersen, S.A., Tax, N., Teinemaa, I., Dumas, M., de Leoni, M., Maggi, F.M., Weidlich, M.: Fire now, fire later: alarm-based systems for prescriptive process monitoring. arXiv preprint arXiv:1905.09568 (2019)
  * [11] Ghalwash, M.F., Radosavljevic, V., Obradovic, Z.: Utilizing temporal patterns for estimating uncertainty in interpretable early decision making. KDD ’14, Association for Computing Machinery (2014)
  * [12] Hartvigsen, T., Sen, C., Kong, X., Rundensteiner, E.: Adaptive-halting policy network for early classification. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 101–110 (2019)
  * [13] He, G., Zhao, W., Xia, X.: Confidence-based early classification of multivariate time series with multiple interpretable rules. Pattern Analysis and Applications 23, 567–580 (2019)
  * [14] Loyola, J.M., Errecalde, M.L., Escalante, H.J., y Gomez, M.M.: Learning when to classify for early text classification. In: Argentine Congress of Computer Science. pp. 24–34. Springer (2017)
  * [15] Lv, J., Hu, X., Li, L., Li, P.: An effective confidence-based early classification of time series. IEEE Access 7, 96113–96124 (2019). https://doi.org/10.1109/ACCESS.2019.2929644
  * [16] Martinez, C., Perrin, G., Ramasso, E., Rombaut, M.: A deep reinforcement learning approach for early classification of time series. In: 2018 26th European Signal Processing Conference (EUSIPCO). pp. 2030–2034. IEEE (2018)
  * [17] Mathukia, C., Fan, W., Vadyak, K., Biege, C., Krishnamurthy, M.: Modified early warning system improves patient safety and clinical outcomes in an academic community hospital. Journal of community hospital internal medicine perspectives 5(2), 26716 (2015)
  * [18] Mori, U., Mendiburu, A., Dasgupta, S., Lozano, J.: Early classification of time series from a cost minimization point of view. In: Proceedings of the NIPS Time Series Workshop (2015)
  * [19] Mori, U., Mendiburu, A., Keogh, E.J., Lozano, J.A.: Reliable early classification of time series based on discriminating the classes over time. Data Mining and Knowledge Discovery 31, 233–263 (2016)
  * [20] Mori, U., Mendiburu, A., Dasgupta, S., Lozano, J.A.: Early classification of time series by simultaneously optimizing the accuracy and earliness. IEEE transactions on neural networks and learning systems 29(10), 4569–4578 (2017)
  * [21] Mori, U., Mendiburu, A., Miranda, I.M., Lozano, J.A.: Early classification of time series using multi-objective optimization techniques. Information Sciences 492, 204–218 (2019)
  * [22] Parrish, N., Anderson, H., Gupta, M., Hsiao, D.Y.: Classifying with confidence from incomplete information. J. Mach. Learn. Res. 14, 3561–3589 (2013)
  * [23] Rußwurm, M., Lefèvre, S., Courty, N., Emonet, R., Körner, M., Tavenard, R.: End-to-end learning for early classification of time series. arXiv preprint arXiv:1901.10681 (2019)
  * [24] Rußwurm, M., Tavenard, R., Lefèvre, S., Körner, M.: Early classification for agricultural monitoring from satellite time series. arXiv preprint arXiv:1908.10283 (2019)
  * [25] Rußwurm, M., Lefèvre, S., Courty, N., Emonet, R., Körner, M., Tavenard, R.: End-to-end learning for early classification of time series (2019)
  * [26] Schäfer, P., Leser, U.: Teaser: early and accurate time series classification. Data Mining and Knowledge Discovery pp. 1–27 (2020)
  * [27] Sharma, A., Singh, S.K.: Early classification of time series based on uncertainty measure. In: 2019 IEEE Conference on Information and Communication Technology. pp. 1–6 (2019). https://doi.org/10.1109/CICT48419.2019.9066213
  * [28] Sharma, A., Kumar Singh, S.: A novel approach for early malware detection. Transactions on Emerging Telecommunications Technologies p. e3968 (2020)
  * [29] Tavenard, R., Malinowski, S.: Cost-aware early classification of time series. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. pp. 632–647. Springer (2016)
  * [30] Teinemaa, I., Tax, N., de Leoni, M., Dumas, M., Maggi, F.M.: Alarm-based prescriptive process monitoring. In: International Conference on Business Process Management. pp. 91–107. Springer (2018)
  * [31] Wang, W., Chen, C., Wang, W., Rai, P., Carin, L.: Earliness-aware deep convolutional networks for early time series classification. ArXiv abs/1611.04578 (2016)
  * [32] Wu, R., Der, A., Keogh, E.J.: When is early classification of time series meaningful? arXiv preprint arXiv:2102.11487 (2021)
  * [33] Xing, Z., Pei, J., Yu, P.S.: Early classification on time series. Knowl. Inf. Syst. (KAIS) 31(1), 105–127 (2012), http://dx.doi.org/10.1007/s10115-011-0400-x
  * [34] Yan, W., Li, G., Wu, Z., Wang, S., Yu, P.S.: Extracting diverse-shapelets for early classification on time series. World Wide Web pp. 1–27 (2020)
  * [35] Yao, L., Li, Y., Zhang, H., Huai, M., Gao, J., Zhang, A.: Dtec: Distance transformation based early time series classification. In: SDM (2019)


#  Connectivity of 1d random geometric graphs

Alexander P. Kartun-Giles<EMAIL_ADDRESS>School of Mathematics,
University of Bristol, Fry Building, Woodland Road, Bristol, BS8 1UG, United
Kingdom  Kostas Koufos<EMAIL_ADDRESS>Nicolas Privault
<EMAIL_ADDRESS>School of Mathematics, University of Bristol, Fry
Building, Woodland Road, Bristol, BS8 1UG, United Kingdom

###### Abstract

A 1d random geometric graph (1d RGG) is built by joining a random sample of
$n$ points from an interval of the real line with probability $p$. We count
the number of $k$-hop paths between two vertices of the graph in the case
where the space is the 1d interval $[0,1]$. We show how the $k$-hop path count
between two vertices at Euclidean distance $|x-y|$ is in bijection with the
volume enclosed by a uniformly random $d$-dimensional lattice path joining the
corners of a $(k-1)$-dimensional hyperrectangular lattice. We are able to
provide the probability generating function and distribution of this $k$-hop
path count as a sum over lattice paths, incorporating the idea of restricted
integer partitions with limited number of parts. We therefore demonstrate and
describe an important link between spatial random graphs, and lattice path
combinatorics, where the $d$-dimensional lattice paths correspond to spatial
permutations of the geometric points on the line.

Keywords: Random geometric graphs, unit disk model, connectivity, $k$-hop
paths, Ferrers diagrams, lattice paths, Gaussian binomial coefficients.

Mathematics Subject Classification (2020): 05C80, 05C40, 11B65.

###### Contents

  1. 1 Introduction
  2. 2 Summary of results
    1. 2.1 Introduction and notation
    2. 2.2 Results
    3. 2.3 The three-hop case
  3. 3 Preliminaries
    1. 3.1 1d random geometric graphs
    2. 3.2 Lattice paths
      1. 3.2.1 Projections
      2. 3.2.2 Volume under the lattice path
      3. 3.2.3 Volume under the path as a restricted integer partition
    3. 3.3 Integer partitions and generating functions
    4. 3.4 Example case
  4. 4 Proofs
    1. 4.1 Distribution of $k$-hop path counts
      1. 4.1.1 Lenses
      2. 4.1.2 Overlapping lenses
      3. 4.1.3 Proof
    2. 4.2 Probability generating function of $k$-hop path counts
  5. A Appendix A: Code for Monte Carlo corroboration

##  1 Introduction

Perhaps the simplest example of a random spatial network [1, 2, 3, 4, 5, 6, 7,
8, 9] is the 1d random geometric graph (1d RGG) [10, 11, 12, 13, 14, 15, 16].
1d problems are widely studied in order to first understand a simpler case,
such as the Ising and Heisenberg models of magnetism studied by Ising and Hans
Bethe in 1924 and 1931 respectively, in the later case resulting in the famous
Bethe ansatz, as well as more modern examples of e.g. 1d statistical mechanics
of nucleosome positioning on genomic DNA, or 1d stochastic traffic flow models
[17, 18, 19, 20].

The 1d case of the random geometric graph has appeared in three major places.
Firstly, as random spatial models in the physics of complex systems, see for
example the 1d soft random geometric graph [10] used in complex networks by
Krioukov et al. in network geometry [21]. Secondly, in Poisson-Boolean
continuum percolation [13, 22, 23, 24], and thirdly, in vehicular
communications [25, 26, 27, 10, 11, 14, 28, 29, 30, 31, 32, 33, 34, 32, 35,
36, 37, 38, 39]. For 1d spatial models similar to the 1d RGG, see the 1d
exponential random geometric graph [40], random interval graphs where the
connection is between overlapping intervals of random length [41, 28], or
various models of one-dimensional mathematical physics [13, 17, 18]. For a
historical introduction to the similar problem of covering a line by random
overlapping intervals, see Domb [42].

1d RGGs do not undergo the connectivity phase transition in the same, non-
trivial way as their 2d counterparts [17]. This has the advantage of
simplifying the underlying geometric probability. M. D. Penrose specifically
points out that the connectivity transition in [43, Theorem 6.1], “is
different (when $d=1$) because 1-space is less connected”. The connectivity
transition in 1d has in fact been been solved by A. Drory in the hard case,
via a statistical physics approach using the Potts model [13]. Study of
connectivity in the soft case can be found in Wilsher et al. [10], where hard
and soft connectivity in the 1d case are compared, and connectivity in the
soft case is studied. The soft case [14, 11, 29, 30, 31, 32] remains unsolved.

The value of understanding the mathematics of the 1d case is well motivated
based on some recent problems in spatial complex networks [44, 2, 45, 46, 6,
47, 14, 48], particularly betweenness centrality [44], which involves counting
the number of paths between two nodes in a complex network [45, 2]. Therefore,
in this article, we focus on counting the integer number $\sigma_{k}$ of
$k$-hop paths which run between two fixed vertices of the 1d RGG. The problem
links random geometric graphs to the problem of counting multidimensional
lattice paths on the $d$-dimensional integer lattice.

The main point of interest of this article is a connection between paths in
random geometric graphs, and the volume beneath a multidimensional lattice
path. This also links the problem to the theory of integer partitions, since
the volume under the path is a restricted integer partition with a limited
number of parts. We put the restriction Eq. (2.5) on the connection range
$r_{0}$ of the vertices in the random geometric graph, to avoid an important
complication known as “overlapping lenses”, see Section 4.1.2. This may at a
later stage be overcome by consisdering a more sophisticated lattice path
counting problem involving downward steps rather than just up, right, and so
on, working toward the terminal point at the corner of the lattice, but the
link to lattice path enumeration remains, which is the focus of the article.
We leave relaxing Eq. (2.5) it to a later study.

Our results are expressions for the probability mass function (p.m.f.) and
probability generating function (p.g.f) for the number $\sigma_{k}$ of $k$-hop
paths between two vertices of the 1d RGG, in terms of the point process
density $\lambda$, and the connection range $r_{0}$. The focus is on the role
lattice paths, spatially random permutations, and random integer partitions
play. A closely related article is Janson [49, Section 3], where the
distribution of the area under a multidimensional lattice path is considered
as a U-statistic, though this is not related to 1d RGGs.

This paper is organised as follows. In Section 2 we summarise our results on
1d RGGs. In Section 3, we introduce some preliminary ideas about lattice paths
and Ferrers diagrams that appear throughout the paper, and define our
notation. In Section 4, we provide proofs of an expression in terms of a sum
over lattice paths for the p.m.f. of the number of $k$-hop paths between two
nodes, and provide proof of a p.g.f for this quantity, as is typical in
enumeration problems. We also include some Mathematica code for the problem in
Appendix A.

##  2 Summary of results

Figure 2.1: The two lenses $L_{1}$ and $L_{2}$, and their nodes (red and blue
respectively). The nodes in the left lens $L_{1}$ connect to the nodes in the
right lens $L_{2}$ when they are within a range $r_{0}$. This is depicted with
the red bars in $L_{2}$, which are bins which give path counts via each nodes.
The three-hop path count in this case is $\sigma_{3}=1+1+2+3=7$.

Figure 2.2: The three lenses $L_{1},L_{2}$ and $L_{3}$, and their nodes (red,
blue and green, respectively). The nodes in the left lens $L_{1}$ connect to
the nodes in the right lens $L_{2}$ when they are within a range $r_{0}$, and
similarly for $L_{2}$ and $L_{3}$. This is depicted with the red bars in
$L_{2}$ and the blue bars in $L_{3}$. The value of $\sigma_{4}$, in this case,
is $\sigma_{4}=0+0+10+10=20$.

Figure 2.3: In this case, is $\sigma_{4}=2+4+4+10=20$. The six lattice paths
which give this exact partition of 20 are depicted in Fig. 4.1. Since there
are six, the partition degeneracy of $2+4+4+10\vdash 20$ is $6$.

Figure 2.4: In this case, is $\sigma_{4}=2+4+7+7=20$. The partition degeneracy
in this case is 2. We add the partition degeneracy of all partitions to get
the total number of lattice paths to which it corresponds.

###  2.1 Introduction and notation

Consider the 1d random geometric graph $G$ defined in Section 3.1. We are able
to state the probability mass function of the number of $k$-hop paths in $G$
which run between the two vertices conditioned to exist at the endpoints of
the domain $[0,1]$ as a sum over lattice paths, in the following way. Consider
the $d$-dimensional hyperrectangle intersecting $\mathbb{Z}^{d}$, which is the
hyperrectangular lattice

$\mathcal{M}_{d}:=\\{0,\dots,m_{1}\\}\times\dots\times\\{0,\dots,m_{d}\\},$
(2.1)

Given two lattice points $A,\Omega\in\mathcal{M}_{d}$, a set of steps
$\mathbb{S}$ (i.e. unit vector movements between adjacent lattice sites), and
an integer $m>0$, we denote by $L_{m}(A\to\Omega;\mathbb{S})$ the set of
lattice paths from $A$ to $\Omega$ with $m$ steps in the set $\mathbb{S}$.
Then with $e_{i}$ denoting the vector with a 1 in the $i^{\text{th}}$
position, and 0 elsewhere, we consider

$\mathcal{P}([m_{k_{1}}\times\dots\times
m_{k_{n}}]):=L_{m}(\mathbf{0}\to(m_{k_{1}},\dots,m_{k_{n}});\\{e_{i}:1\leq
i\leq n\\})$ (2.2)

to be the set of lattice paths between $\mathbf{0}$ and
$(m_{k_{1}},\dots,m_{k_{n}})$ in the lattice $[m_{k_{1}}\times\dots\times
m_{k_{n}}]$. Then, consider a lattice path
$\Pi_{k-1}\in\mathcal{P}(\mathcal{M}_{k-1})$. We need six further
straightforward ingredients derived from $\Pi_{k}$. Firstly, as shown in Fig.
3.2, the projections $\Pi_{ij}(\Pi_{k-1})$ of $\Pi_{k-1}$ onto the faces of
$\mathcal{M}_{k-1}$, which are ${m_{i}+m_{j}\choose m_{i}}$-letter words
composed of two types of letter. Secondly, the integer partition
$\pi_{ij}\left(\Pi_{k-1}\right)$ corresponding to the Ferrers diagram under
the projection $\Pi_{ij}(\Pi_{k-1})$, which is a sequence of $m_{i}$ integers
each of size no larger than $m_{j}$, and whose $t^{\text{th}}$ part is
$\pi_{ij}(t)$, where the context is clear that we are considering the
$t^{\text{th}}$ part of the integer sequence $\pi_{ij}\left(\Pi_{k-1}\right)$.
When the subscripts are omitted in the case $\pi(\Pi)$, this denotes the
integer partition corresponding to the 2d lattice path $\Pi$, though the
context will be clear.

Thirdly, since the hypervolume $V$ under the path may be interpreted as a
restricted integer partition of $V$ using exactly $m_{k-1}$ parts from the set
$S(\Pi_{k-2})$, we need the integer sequences of Eq. (3.13), which we detail
there. We write

$S(\Pi_{k-1})=\left(S_{i}(\Pi_{k-1})\right)_{i=0,\dots,m_{k-2}}$ (2.3)

to distinguishing the individual parts. Fourth, we need the multiplicity of
each part of the partition $\pi_{ij}$, denoted $\pi_{ij}^{\star}$, so with the
partition $1+1+3+3=8$ represented as a sequence is $\pi_{ij}=(1,1,3,3)$, and
then $\pi_{ij}^{\star}=(0,2,0,2,0)$, so two 1’s and two 3’s. Fifth, we need
the notion of the complement of a Ferrers diagram. For $1\leq i<j\leq k-1$ we
let $\pi_{j,i}$ denote the complement of $\pi_{i,j}$. For example, the diagram
of $\pi_{i,j}=(1,1,3,3)$ has complement $\pi_{j,i}=(0,2,2,4)$, and
$\pi_{j,i}^{\star}=(1,0,2,0,1)$. Finally, for some lattice path
$\Pi_{\gamma}$, another lattice path $\Pi$, and some integer partition
$\pi(\Pi)$, we define the “dot product” of two equal length sequences

$S(\Pi_{\gamma})\cdot\pi(\Pi):=S_{0}(\Pi_{\gamma})\pi(0)+\cdots+S_{m_{\gamma}}(\Pi_{\gamma})\pi(m_{\gamma}).$
(2.4)

A simple example of the use of all the notation in this article is given in
detail in Section 3.4.

###  2.2 Results

For density $\lambda\geq 0$, number of hops $k\in\mathbb{N}^{+}$, a connection
range $r_{0}$ satisfying

$\frac{1}{k}<r_{0}<\frac{1}{k-1}$ (2.5)

and with $|x-y|$ the Euclidean distance between two points $x,y\in[0,1]$,
consider the 1d hard random geometric graph on the Poisson point process
$\mathcal{P}_{\lambda}\subset[0,1]$, and two further points conditioned to
exist at $0,1\in[0,1]$, forming the vertex set $V:=P_{\lambda}\cup\\{0,1\\}$,
and with edge set $E:=\\{\\{x,y\\}\in V^{2}:|x-y|<r_{0}\\}$, denoted $G(V,E)$.
Consider $m_{1},\dots,m_{k-1}\sim\textrm{Poisson}(\lambda|L|)$, where $|L|$ is
given by Eq. (4.2). Then we have the following statements for the distribution
of the number of $k$-hop paths $\sigma_{k}$ between the endpoints $0,1$.

Firstly concerning the trivial case when $k=1$, then
$\sigma_{1}=\mathbf{1}_{\\{r_{0}\geq 1\\}}$. When $k=2$, the Poisson number
$m_{1}$ of vertices in $L_{1}$ implies
$\sigma_{2}\sim\text{Poisson}(2r_{0}-1)$. Now consider the case $k\geq 3$ of
the following theorem.

######  Theorem 1 (Distribution of $\sigma_{k}$).

Assume that $k\geq 3$. The probability of observing $n$ $k$-hop paths
connecting the two vertices at the boundary of $[0,1]$ in $G(V,E)$ is given by

$\mathbb{P}(\sigma_{k}=n)=\frac{1}{{m_{1}+\dots+m_{k-1}\choose
m_{1},\ldots,m_{k-1}}}\sum_{\Pi_{k-2}\in\mathcal{P}\left(\mathcal{M}_{k-2}\right)}\sum_{\Pi\in{\cal
P}([m_{k-2}\times m_{k-1}])\atop
S(\Pi_{k-2})\cdot\pi^{\star}(\Pi)=n}\prod_{r=0}^{m_{k-2}}{\pi^{\star}(r)+\sum_{l=1}^{k-3}\pi_{k-2,l}^{\star}(r)\choose\pi^{\star}(r)},$
(2.6)

Using the coefficient extraction operator $[u^{n}]$ of Eq. (3.18), which is
standard notation for the coefficient of $u^{n}$ in a series it precedes, we
have the following result.

######  Theorem 2 (Probability generating function for $\sigma_{k}$).

Let $k\geq 2$. Then the p.g.f. of the number of $k$-hop paths connecting the
two vertices at the boundary of $[0,1]$ in $G(V,E)$ is given by

$\mathbb{E}\big{[}q^{\sigma_{k}}\big{]}=\frac{1}{{m_{1}+\cdots+m_{k-1}\choose
m_{1},\ldots,m_{k-1}}}[u^{m_{k-1}}]\sum_{\Pi\in\mathcal{P}\left(\mathcal{M}_{k-2}\right)}\prod_{t=0}^{m_{k-2}}\frac{1}{(1-uq^{S_{t}(\Pi)})^{1+\sum_{l=1}^{k-3}\pi_{k-2,l}^{\star}(t)}}.$
(2.7)

The coefficients of Eq. 2.7 are corroborated via Monte Carlo simulation of the
1d RGG for the case $k=3,4$ in Figs. 4.6 and 4.7.

###  2.3 The three-hop case

######  Corollary 2.1 (The distribution in the case $k=3$).

Theorem 1 implies that, since $\mathcal{P}(\mathcal{M}_{1})$ contains only one
path, the probability of observing $n$ three-hop paths connecting the two
vertices at the boundary of $[0,1]$ in $G(V,E)$ is given by

$\mathbb{P}(\sigma_{3}=n)=\frac{1}{{m_{1}+m_{2}\choose
m_{1}}}\sum_{\Pi\in{\cal P}(\mathcal{M}_{2})\atop
S(\Pi_{2})\cdot\pi^{\star}(\Pi)=n}1,$ (2.8)

######  Corollary 2.2 (The p.g.f. in the case $k=3$).

Theorem 2 implies that the p.g.f. of the number of $3$-hop paths connecting
the two vertices at the boundary of $[0,1]$ in $G(V,E)$ is given by a
normalised $q$-binomial coefficient of Eq. (3.21),

$\mathbb{E}\big{[}q^{\sigma_{3}}\big{]}=\frac{1}{{m_{1}+m_{2}\choose
m_{1}}}[u^{m_{2}}]\prod_{t=0}^{m_{1}}\frac{1}{1-uq^{t}}=\frac{1}{{m_{1}+m_{2}\choose
m_{1}}}{m_{1}+m_{2}\choose m_{1}}_{q}.$ (2.9)

##  3 Preliminaries

The following preliminary sections introduce our notation, the 1d RGG,
multidimensional lattice paths and their projections, and the associated
restricted integer partitions.

###  3.1 1d random geometric graphs

To define the homogeneous Poisson point process
$\mathcal{P}_{\lambda}\subset[0,1]$, of intensity $\lambda$ times Lebesgue
measure $||\cdot||$ on $[0,1]$, for $a,b\in[0,1]$, with $a\leq b$, and with
$N(a,b]$ the count of points in $\mathcal{P}_{\lambda}\cap(a,b]$, then we have
that

$\mathbb{P}(N(a,b]=n)=\frac{\left(\lambda\left(b-a\right)\right)^{n}}{n!}e^{-\lambda(b-a)},$
(3.1)

and furthermore, that the counts of points in any pair of disjoint intervals
of $[0,1]$ are independent. Then, for density $\lambda\geq 0$ points per unit
length, connection range $r_{0}>0$, and with $|x-y|$ the Euclidean distance
between two points $x,y\in[0,1]$, then with the Poisson point process
$\mathcal{P}_{\lambda}\subset[0,1]$, and two further points conditioned to
exist at $0,1\in[0,1]$, forming the vertex set $V:=P_{\lambda}\cup\\{0,1\\}$,
and with edge set $E:=\\{\\{x,y\\}\in V^{2}:|x-y|<r_{0}\\}$, then the 1d hard
random geometric graph is the graph $G(V,E)$. This model is used throughout
this article.

Figure 3.1: The three restricted integer partitions of 20 using exactly
$m_{3}=4$ parts from the restricted set of integers
$S(\Pi_{3})=\\{0,2,4,7,10\\}$. (a) $0+0+10+10\vdash 20$, (b) $2+4+4+10\vdash
20$ and (c) $2+4+7+7\vdash 20$.

###  3.2 Lattice paths

In layman’s terms, a lattice path is a path from the lower left to top right
of a rectangular lattice. It may be high-dimensional, so between the extreme
corners of a $d$-dimensional lattice. The area under a lattice path is major
topic in combinatorics.

######  Definition 3.1.

Given two lattice points $A$ and $\Omega$, a set of steps $\mathbb{S}$, and an
integer $m>0$, we denote by $L_{m}(A\to\Omega;\mathbb{S})$ the set of lattice
paths from $A$ to $\Omega$ with $m$ steps in the set $\mathbb{S}$.

######  Definition 3.2.

With $e_{i}$ denoting the vector with a 1 in the $i^{\text{th}}$ position, and
0 elsewhere, we consider

$\mathcal{P}([m_{k_{1}}\times\dots\times
m_{k_{n}}]):=L_{m}(\mathbf{0}\to(m_{k_{1}},\dots,m_{k_{n}});\\{e_{i}:1\leq
i\leq n\\})$ (3.2)

to be the set of lattice paths between $\mathbf{0}$ and
$(m_{k_{1}},\dots,m_{k_{n}})$ in the lattice $[m_{k_{1}}\times\dots\times
m_{k_{n}}]$.

Consequently,

$\mathcal{P}(\mathcal{M}_{d})=L_{m}(\mathbf{0}\to\mathbf{m};\\{e_{i}:1\leq
i\leq d\\})$ (3.3)

is the set of lattice paths between $\mathbf{0}$ and $\mathbf{m}$ in
$\mathcal{M}_{d}$.

The lattice paths of Def. 3.1 resemble natural $d$-dimensional versions of the
up-right lattice paths in $\mathcal{M}_{2}$. We can equivalently regard
$\mathcal{P}({\cal M}_{d})$ as the set of permutations of the multiset

$e_{1}^{m_{1}}e_{2}^{m_{2}}\dots
e_{d}^{m_{d}}:=\\{\underbrace{e_{1},e_{1},\dots,e_{1}}_{m_{1}\text{
times}},\underbrace{e_{2},e_{2},\dots,e_{2}}_{m_{2}\text{
times}},\dots,\underbrace{e_{d},e_{d},\dots,e_{d}}_{m_{d}\text{ times}}\\}$
(3.4)

where direction $e_{1}$ occurs $m_{1}$ times, $e_{2}$ occurs $m_{2}$ times,
and so on, until all $m_{1}+\dots+m_{d}$ directed lattice steps have been
taken, and the path arrives at the boundary point $\mathbf{m}$.

Figure 3.2: Projecting the path onto the faces of the lattice, determining the
volume beneath. With
$\Pi_{3}=\left(e_{3},e_{1},e_{1},e_{2},e_{3},e_{2}\right)$ (black lattice
path), the steps (a)-(c) show the three projections
$\Pi_{12}(\Pi_{3})=\\{e_{1},e_{1},e_{2},e_{2}\\},\Pi_{13}(\Pi_{3})=\\{e_{3},e_{2},e_{3},e_{2}\\}$
and $\Pi_{23}(\Pi_{3})=\\{e_{3},e_{1},e_{1},e_{3}\\}$ (red lattice paths) onto
the white, yellow and blue faces respectively, of the lattice
$\mathcal{M}_{3}=[2\times 2\times 2]$, used to determine the exact 3d volume
shown in (d) (stacked cubes).

####  3.2.1 Projections

In addition, for $1\leq i<j\leq d$ we denote by $\Pi_{i,j}(\Pi_{k-1})$ the
projection of the path $\Pi_{k-1}$ onto the $2$-dimensional face $m_{i}\times
m_{j}$ generated by $(e_{i},e_{j})$. Therefore

$\Pi_{i,j}(\Pi_{k-1})\in L_{m_{i}+m_{j}}(\mathbf{0}\to
m_{i}e_{i}+m_{j}e_{j};\\{e_{i},e_{j}\\}).$ (3.5)

This is depicted in Fig. 3.2, where we have $e_{1}=(1,0,0)$ as right,
$e_{1}=(0,1,0)$ as up, $e_{1}=(0,0,1)$ as in,
$\Pi_{2}=(e_{1},e_{2},e_{2},e_{3},e_{1},e_{3})$, and so
$\Pi_{1,2}(\Pi_{2})=(e_{1},e_{2},e_{2},e_{1})$,
$\Pi_{2,3}(\Pi_{2})=(e_{2},e_{2},e_{3},e_{3})$, and
$\Pi_{1,3}(\Pi_{2})=(e_{1},e_{3},e_{1},e_{3})$. In the specific example of
Fig. 3.2, since $\pi_{1,2}=(2,2)$, $\pi_{2,3}=(0,1)$ and $\pi_{1,3}=(0,2)$, we
have the restricted set of integers $S(\Pi_{3})=(0,0+2,0+2+2)=(0,2,4)$, and
the partition $\pi_{2,3}^{\star}\cdot S(\Pi_{3})\vdash
2=(1,1,0)\cdot(0,2,4)\vdash 2=0+2\vdash 2$. This black lattice path is the
only lattice path which corresponds to this restricted integer partition of
$0+2\vdash 2$, and so in this case
$\text{Degeneracy}\left(\pi_{2,3}^{\star}\cdot S(\Pi_{3})\vdash
2\right)=\text{Degeneracy}\left(\left(1,1,0\right)\cdot\left(0,2,4\right)\vdash
2)\right)=1$.

####  3.2.2 Volume under the lattice path

In Section 3.2.1, we discussed the projections $\Pi_{ij}(\Pi_{k-1})$ of
$\Pi_{k-1}$ onto the faces of $\mathcal{M}_{k-1}$. These projections are
themselves Ferrers diagrams, depicted in Fig. 3.2. Therefore, given a lattice
path $\Pi_{k-1}$, consider the integer partition
$\pi_{ij}\left(\Pi_{k-1}\right)$, which is a sequence of $m_{i}$ integers each
of size no larger than $m_{j}$, and whose $t^{\text{th}}$ part is
$\pi_{ij}(t)$. The context will be clear that we are considering by
$\pi_{ij}(t)$ the $t^{\text{th}}$ part of the integer sequence
$\pi_{ij}\left(\Pi_{k-1}\right)$.

We now define the volume under the lattice path. Consider the
$(k-1)$-dimensional lattice cell

$\displaystyle\mathrm{cell}\left(x_{1},\dots,x_{k-1}\right):=[x_{1},x_{1}+1]\times[x_{2},x_{2}+1]\times\dots\times[x_{k-1},x_{k-1}+1]$
(3.6)

and its $(u,v)$-face

$\displaystyle\mathrm{cell}_{u,v}\left(x_{1},\dots,x_{k-1}\right):=[x_{u},x_{u}+1]\times[x_{v},x_{v}+1]$
(3.7)

Then, we mean that the $(k-1)$-dimensional volume under the lattice path
$\Pi_{k-1}$ is

$\displaystyle
V(\Pi_{k-1}):=\\#\\{\mathrm{cell}_{u,v}\left(x_{1},\dots,x_{k-1}\right):x_{v}<\pi_{u,v}(x_{u}),1\leq
u<v\leq k-1\\}.$ (3.8)

####  3.2.3 Volume under the path as a restricted integer partition

The volume $V$ defined in Eq. 3.8 is an integer partition in the following
way. Consider the lattice path $\Pi_{k-1}$ enclosing a volume $V(\Pi_{k-1})$.
Then consider the integer sequences

$\displaystyle S(\Pi_{2})$ $\displaystyle:=\left(0,1,\dots,m_{1}\right)$ (3.9)
$\displaystyle S(\Pi_{3})$
$\displaystyle:=\Bigg{(}\sum_{i_{1}=1}^{t}\pi_{1,2}(i_{1})\Bigg{)}_{t=0,\ldots,m_{2}}$
(3.10) $\displaystyle S(\Pi_{4})$
$\displaystyle:=\Bigg{(}\sum_{i_{2}=1}^{t}\sum_{i_{1}=1}^{\pi_{2,3}(i_{2})}\pi_{1,2}(i_{1})\Bigg{)}_{t=0,\ldots,m_{3}}$
(3.11) $\displaystyle S(\Pi_{5})$
$\displaystyle:=\Bigg{(}\sum_{i_{3}=1}^{t}\sum_{i_{2}=1}^{\pi_{3,4}(i_{3})}\sum_{i_{1}=1}^{\pi_{2,3}(i_{2})}\pi_{1,2}(i_{1})\Bigg{)}_{t=0,\ldots,m_{4}}$
(3.12) $\displaystyle\;\;\;\vdots$ $\displaystyle S(\Pi_{k-1})$
$\displaystyle:=\Bigg{(}\sum_{i_{k-3}=1}^{t}\sum_{i_{k-2}=1}^{\pi_{k-3,k-2}(i_{k-3})}\cdots\sum_{i_{1}=1}^{\pi_{2,3}(i_{2})}\pi_{1,2}(i_{1})\Bigg{)}_{t=0,\ldots,m_{k-2}}.$
(3.13)

where the empty sum is the first element in each sequence $S$, since the case
$t=0$ gives a sum with no summands each time, and so gives zero by definition.
We write $S(\Pi_{k-2})=\left(S_{i}(\Pi_{k-2})\right)_{i=0,\dots,m_{k-3}}$ to
distingusihing the individual parts. Recall that the multiplicity of each part
of the partition $\pi_{ij}$ is denoted $\pi_{ij}^{\star}$, so for example the
partition $8=1+1+3+3$ may be represented by the sequence $\pi_{ij}=(1,1,3,3)$,
and $\pi_{ij}^{\star}=(0,2,0,2,0)$, where we have considered the case where we
use four parts from the set $\\{0,1,2,3,4\\}$.

Now consider, alongside Eq. (3.13), the integer partition
$\pi_{k-2,k-1}(\Pi_{k-1})$. Then, consider the integer $n$, and the integer
partition $\Lambda(\Pi_{k-1})\vdash n$ corresponding to the volume under the
lattice path. Then

$\Lambda(\Pi_{k-1})=\pi_{k-2,k-1}^{\star}\cdot S(\Pi_{k-2}).$ (3.14)

$\Lambda(\Pi_{k-1})$ is therefore a restricted integer partition of the volume
under the path $\Pi_{k-1}$, using exactly $m_{k-1}$ parts from the set
$S(\Pi_{k-2})$. This is depicted in Fig. 3.1, where the three restricted
integer partitions of 20 using exactly $m_{3}=4$ parts from the restricted set
of integers $S(\Pi_{3})=\\{0,2,4,7,10\\}$ are shown.

###  3.3 Integer partitions and generating functions

We use the notation $\Lambda\vdash n$ to denote that $\Lambda$ is an integer
partition of $n$. For example, with $n=20$, we write $2+4+4+10\vdash 20$ when
$\Lambda=(2,4,4,10)$. The partition function $p(n)$ counts the number of
possible partitions of an integer $n$. Two sums differing only by the order of
their summands are not considered to be distinct partitions. They are however
distinct compositions. It is common to use a generating function

$\sum_{n=0}^{\infty}p(n)q^{n}=\prod_{r=1}^{\infty}\frac{1}{1-q^{r}}.$ (3.15)

Consider the number $p(n,r)$ of integer partitions of $n$ into exactly $r$
parts. Then we have a generating function in two variables,

$\sum_{r=0}^{\infty}u^{r}\sum_{n=r}^{\infty}p(n,r)q^{n}=\prod_{r=1}^{\infty}\frac{1}{1-uq^{r}},$
(3.16)

and define the linear coefficient extraction operator $[u^{n}]A(u)$, acting on
any formal power series

$A(u)=\sum_{n\geq 0}a_{n}u^{n}$ (3.17)

as the operator which extracts the $n^{\text{th}}$ coefficient in the series,

$[u^{n}]A(u):=a_{n},\qquad n\geq 0.$ (3.18)

Then, we may write the integer partition function

$p(n,r)=[q^{n}][u^{r}]\prod_{r=1}^{\infty}\frac{1}{1-uq^{r}},$ (3.19)

Given a set of integers $S$, the number of integer partitions $p_{S}(n,r)$ of
$n$ into $r$ parts chosen from the set $S$ satisfies

$\sum_{r=0}^{\infty}u^{r}\sum_{n=r}^{r\max(S)}p_{S}(n,r)q^{n}=\prod_{k\in
S}\frac{1}{1-uq^{k}},$ (3.20)

The probability generating function of the area under a uniformly random
lattice path from $(0,0)$ to $(m_{1},m_{2})$ in $\mathcal{M}_{2}$ is given by
the $q$-binomial coefficient, which is, for $r\leq m$,

${m\choose
r}_{q}=\frac{(1-q^{m})(1-q^{m-1})\cdots(1-q^{m-r+1})}{(1-q)(1-q^{2})\cdots(1-q^{r})}$
(3.21)

This may be written

${m_{1}+m_{2}\choose
m_{1}}_{q}=\sum_{n=0}^{m_{1}m_{2}}p_{\\{0,1,\ldots,m_{1}\\}}(n,m_{2})q^{n}.$
(3.22)

giving a generating function for restricted integer partitions in $m_{2}$
parts no larger than $m_{1}$.

###  3.4 Example case

Consider Figs. 2.4, 2.4, 2.4 and 2.4. A simple example case is the following,
for the case $k=4$. We have the cuboid lattice $\mathcal{M}_{3}=[m_{1}\times
m_{2}\times m_{3}]$. A lattice path starting at $(0,0,0)$ and terminating at
$(m_{1},m_{2},m_{3})$ consists of three types of movements, $e_{1}$, $e_{2}$
and $e_{3}$ (right, up, and in). The lattice path $\Pi_{k-1}=\Pi_{3}$ encloses
a 3d volume beneath, bounded by the the domain walls, and itself, in a new way
discussed in Section 3.2.2. Each of the six projections
$\Pi_{1,2},\Pi_{1,3},\dots,\Pi_{3,2}$ onto the six faces of the cuboid are
themselves Ferrers diagrams. Consider the example lattice path shown in Fig.
4.1 (a), which is
$\Pi_{4}=(\text{up},\text{up},\text{in},\text{right},\text{in},\text{right},\text{right},\text{up},\text{in},\text{in},\text{right},\text{up})$.
Then we have, on the white face,
$\Pi_{1,2}=(\text{up},\text{up},\text{in},\text{in},\text{up},\text{in},\text{in},\text{up})$
and therefore the corresponding partition $\pi_{1,2}=(2,2,3,3)$, as well as,
on the blue face,

$\Pi_{1,3}=(\text{up},\text{up},\text{right},\text{right},\text{right},\text{up},\text{right},\text{up})$
(3.23)

and therefore the corresponding partition $\pi_{1,3}=(2,2,2,3)$, and finally
on the yellow face
$\Pi_{2,3}=(\text{in},\text{right},\text{in},\text{right},\text{right},\text{in},\text{in},\text{right})$
and therefore the corresponding partition $\pi_{2,3}=(1,2,2,4)$. The
projections $\Pi_{2,1},\Pi_{3,1}$ and $\Pi_{3,2}$ are the same as their
counterparts $\Pi_{1,2},\Pi_{1,3}$ and $\Pi_{2,3}$, since they represent the
projection of the lattice path onto the opposing face. In our case, we
therefore have

$\displaystyle S(\Pi_{3})$
$\displaystyle=\Bigg{(}\sum_{i_{1}=1}^{t}\pi_{1,2}(i_{1})\Bigg{)}_{t=0,1,\ldots,4}$
(3.24)
$\displaystyle=\left(0,\pi_{1,2}(1),\pi_{1,2}(1)+\pi_{1,2}(2),\dots,\pi_{1,2}(1)+\pi_{1,2}(2)+\pi_{1,2}(3)+\pi_{1,2}(4)\right)$
(3.25) $\displaystyle=\left(0,2,4,7,10\right)$ (3.26)

For the multiplicities and part counts, we have $\pi_{2,1}=(0,0,2,4)$,
$\pi_{3,1}=(0,0,3,4)$, $\pi_{3,2}=(0,1,3,4)$, $\pi_{2,1}^{\star}=(2,0,1,0,1)$,
$\pi_{3,1}^{\star}=(2,0,0,1,1)$ and $\pi_{3,2}^{\star}=(1,1,0,1,1)$. We would
also have

$\displaystyle S(\Pi_{4})$
$\displaystyle=\Bigg{(}\sum_{i_{2}=1}^{t}\sum_{i_{1}=1}^{\pi_{2,3}(i_{2})}\pi_{1,2}(i_{1})\Bigg{)}_{t=0,\ldots,4}$
(3.27)
$\displaystyle=\Bigg{(}0,\sum_{i_{1}=1}^{1}\pi_{1,2}(i_{1}),\dots,\sum_{i_{1}=1}^{1}\pi_{1,2}(i_{1})+\sum_{i_{1}=1}^{2}\pi_{1,2}(i_{1})+\sum_{i_{1}=1}^{2}\pi_{1,2}(i_{1})+\sum_{i_{1}=1}^{4}\pi_{1,2}(i_{1})\Bigg{)}$
(3.28) $\displaystyle=\left(0,2,\dots,2+(2+2)+(2+2+3)+(2+2+3+3)\right)$ (3.29)
$\displaystyle=\left(0,2,6,10,20\right)$ (3.30)

##  4 Proofs

Figure 4.1: Six lattice paths between $\mathbf{0}$ and $(4,4,4)$ in the
lattice $[4\times 4\times 4]$. Each path encloses the same area, and the area
is the same partition of $20=2+4+4+10$. The degeneracy in this case is
therefore six.

###  4.1 Distribution of $k$-hop path counts

Consider $m_{1},\dots,m_{k-1}\sim\textrm{Poisson}(\lambda|L|)$, where $|L|$ is
given by Eq. (4.2). We denote by $\sigma_{k}(0,1)=\sigma_{k}$ the number of
$k$-hop paths between the vertices $0,1$ in the vertex set of the graph
$G(V,E)$. In this section, for $n\leq 0$, $k\geq 2$, we compute the p.m.f.
$P(\sigma_{k}=n)$ for all $k$. We now detail the proof of Theorem 1, with a
short introduction to the intersecting intervals known as lenses.

####  4.1.1 Lenses

Figure 4.2: The overlapped lenses from Fig. 2.4. The are five “gaps” between
the blue balls, in which lie unbroken sequences of red and green balls.

Figure 4.3: The permutation of Fig. 2.4, but with two of the nodes in the 3rd
blue gap (from the left) swapped. This gives a new lattice path, but not a new
integer partition of the number of paths. The product of the number of ways of
permuting the red and green nodes, within each a blue gap, leads to the
partition degeneracy of Eq. (4.9).

Since in the case $r_{0}\leq 1/k$ we necessarily have $\sigma_{k}=0$, in what
follows, we assume that $r_{0}>1/k$. With $B(a,b)$ the ball centered at $a$ of
radius $b$, we define disjoint intervals $L_{1}<\cdots<L_{k-1}$,

$L_{j}:=B(0,jr_{0})\cap B(1,(k-j)r_{0}),\qquad j=1,\ldots,d,$ (4.1)

called “lenses”, of same length

$|L_{i}|=kr_{0}-1>0,$ (4.2)

where, using $\\#A$ for the cardinality of a set $A$, the number of points in
the intersection of the lens and the points $P_{\lambda}$,

$\\#\\{\mu:\mu\in L_{j}\cap P_{\lambda}\\}=m_{j}.$ (4.3)

Importantly, we also have an upper bound on the connection range $r_{0}$,
where we therefore restrict

$\frac{1}{k}<r_{0}<\frac{1}{k-1}$ (4.4)

to stop the lenses overlapping. We therefore consider i.i.d. random variables
$m_{1},\dots,m_{k-1}\sim\textrm{Poisson}(\lambda|L|)$.

####  4.1.2 Overlapping lenses

The lenses will overlap for large enough values of $r_{0}$ for each choice of
$k$, not considering the restriction of Eq. 2.5, but since the paths will
still hop between the lenses sequentially, this does not affect the
combinatorial idea of lattice path enumeration determining the $k$-hop path
count $\sigma_{k}$. See e.g. Fig 2.4 for a depiction of the non-overlapping
case for $k=3$, and Fig. 2.4 for a depiction in the case $k=4$. We leave the
complete solution to all ranges of $r_{0}$ to a later work, focusing on
showing as clearly as possible this link with lattice path combinatorics, and
integer partitions.

####  4.1.3 Proof

###### Proof of Theorem 1.

When $k=1$, then $\sigma_{1}=\mathbf{1}_{\\{r_{0}\geq 1\\}}$. When $k=2$ there
exists a two-hop path if and only if $L_{1}$ contains $m_{1}>0$ vertices of
$\mathcal{X}$, and $\sigma_{2}\sim\text{Poisson}(2r_{0}-1)$. Now consider
$k=3$. This is depicted in Fig. 2.4. By overlapping the lenses and considering
the relative locations of the nodes in $L_{1}$ and $L_{2}$ in a new lens of
unit width, we represent the locations of nodes $\\{1,\ldots,m_{1}\\}$ in
$[0,|L_{1}|]$, or of the nodes $\\{m_{1},\ldots,m_{1}+m_{2}\\}$ in
$[0,|L_{2}|]$ using a sequence $\\{Y_{i}\\}_{i=1}^{m_{1}+m_{2}}$, with
$Y_{i}\sim\text{Uniform}[0,1]$, then letting

$X_{i}:=\begin{cases}1&\text{for }1\leq i\leq m_{1}\\\ 2&\text{for
}m_{1}+1\leq i\leq m_{1}+m_{2},\end{cases}$ (4.5)

then $\sigma_{3}$ may be written

$\sigma_{3}=\sum_{j=1}^{m_{2}}\sum_{i=1}^{m_{1}}\mathbf{1}_{\\{X_{i}>X_{j}\\}}\mathbf{1}_{\\{Y_{i}<Y_{j}\\}}$
(4.6)

Since the $m_{1}+m_{2}$ nodes are in a specific permutation given by their
relative locations $Y_{i},1\leq i\leq m_{1}+m_{2}$, we observe that
$\sigma_{3}$ can be written as the area under a 2d lattice path
$\Pi_{2}\in\mathcal{M}_{2}$ of $m_{1}+m_{2}$ steps. For example, with
$e_{1}=(1,0)$ a right turn, and $e_{2}=(0,1)$ an up turn, Fig. 2.4 depicts the
case

$\Pi_{k-2}=(e_{2},e_{1},e_{1},e_{2},e_{1},e_{2},e_{1},e_{2})$ (4.7)

where we are reading the steps from the right end of $L_{2}$, to its left end.
The volume this path encloses is the Ferrers diagram of the integer partition
$\pi_{1,2}=(1,1,2,3)$, so $\pi_{1,2}\vdash\sigma_{3}$, and
$\sigma_{3}=1+2+3+3=7$.

Notice that each lattice path $\Pi_{2}\in\mathcal{P}(\mathcal{M}_{2})$ occurs
uniformly at random, and so we have

$\mathbb{P}(\sigma_{3}=n)=\frac{1}{{m_{1}+m_{2}\choose
m_{1}}}\\#\\{\Pi_{2}\in\mathcal{P}(\mathcal{M}_{2}):\pi_{1,2}\cdot
S(\Pi_{2})=n\\}$ (4.8)

which implies Eq. (2.8).

For each case $k\geq 2$, we have a sequence of integers $S(\Pi_{k-1})$ out of
which we select $m_{k-1}$ parts to from a partition
$\pi_{k-2,k-1}^{\star}\cdot S(\Pi_{k-2})\vdash\sigma_{k}$. For $n\geq 0$, the
more partitions $\pi_{k-2,k-1}^{\star}\cdot S(\Pi_{k-2})\vdash n$ restricted
to the set $S$, and the more sets $S$ which can provide at least one integer
partition of $n$, the greater $\mathbb{P}(\sigma_{k}=n)$. An example for the
case $k=4$ is given in Section 2.

The main difference from the case $k\leq 3$ is the idea of partition
degeneracy. This is depicted in Figs. 2.4, 2.4 and 2.4, as well as in Figs.
4.3 and 4.3. This is the following observation. A given integer partition
$\pi_{k-2,k-1}^{\star}\cdot S(\Pi_{k-2})\vdash\sigma_{k}$ is determined by a
fixed set of sub-partitions $\pi_{1,2},\pi_{2,3},\dots,\pi_{k-2,k-1}$, but is
insensitive to the other details of $\pi_{1,3},\pi_{1,4},\dots$ i.e. where the
subscripts are not adjacent integers. Altering the details of
$\pi_{1,3},\pi_{1,4},\dots$ etc. will modify only the corresponding lattice
path $\Pi_{k-1}$, but not the enclosed volume $V(\Pi_{k-1})$, nor the
partition $\pi_{k-2,k-1}\cdot S(\Pi_{k-2})\vdash\sigma_{k}$. As such, in the
case $k\geq 4$, each integer partition of $\sigma_{k}$ may have more than one
lattice path to which it corresponds. The number of different lattice paths
corresponding to a specific integer partition $\pi_{k-2,k-1}\cdot
S(\Pi_{k-2})\vdash\sigma_{k}$ is the integer-valued partition degeneracy

$\text{Degeneracy}(\pi_{k-2,k-1}^{\star}\cdot
S(\Pi_{k-2})\vdash\sigma_{k})=\prod_{t=0}^{m_{k-2}}{\pi_{k-2,k-1}^{\star}(t)+\sum_{l=1}^{k-3}\pi_{k-2,l}^{\star}(t)\choose\pi_{k-2,k-1}^{\star}(t)}.$
(4.9)

In the example in Fig. 4.1 there are six paths (a)-(f), and so
$\text{Degeneracy}(\pi_{2,3}^{\star}\cdot
S(\Pi_{3})\vdash\sigma_{4})=\text{Degeneracy}(\\{0,1,2,0,1\\}\cdot\\{0,2,4,7,10\\}\vdash
20)=\text{Degeneracy}(2+4+4+10\vdash 20)=6$. See also Figs. 4.5 and 4.5. Eq.
(4.9) is then summed over all partitions $\pi_{k-2,k-1}^{\star}\cdot
S(\Pi_{k-2})\vdash n$ to give the theorem. ∎

Figure 4.4: Partition degeneracy: (a) This partition
$3+3+9+27+27+27+27+27\vdash 150$ has a partition degeneracy of zero, since one
cannot alter the red lattice path without altering the exact arrangement of
the cubes beneath. It has no right turns followed by up turns, and vice versa,
nor does the path walk on the walls of the cube.

Figure 4.5: (b) We depict $2+2+8+21+21+21+21+21\vdash 117$. The partition
degeneracy is this case is 13. Walking on the walls of $\mathcal{M}_{3}$
corresponds to a partition degeneracy, as can seen by the 10 different choices
of routes in the final 5 steps on the red lattice path. This corresponds to
the placement of balls in bins with label zero, which may be altered without
affecting the overall partition. Counting these carefully may lead to a
formula for the probability of zero paths.

###  4.2 Probability generating function of $k$-hop path counts

Figure 4.6: Monte Carlo simulations (black dots), compared with our analytical
calculations of Eq. 2.6 (red line). We take $k=3$, and with two lenses in this
case, we have $m_{1},m_{2}=7$. Figure 4.7: Monte Carlo simulations (black
dots), compared with our analytical calculations of Eq. 2.6 (red line). We
take $k=4$, and with three lenses in this case, we have $m_{1},m_{2},m_{3}=5$.

###### Proof of Theorem 2.

Recall that when $k=1$, then $\sigma_{1}=\mathbf{1}_{\\{r_{0}\geq 1\\}}$, and
when $k=2$ there exists a two-hop path if and only if $L_{1}$ contains
$m_{1}>0$ vertices of $\mathcal{X}$, and
$\sigma_{2}\sim\text{Poisson}(2r_{0}-1)$. The pg.f. for the trivial case
$1\leq k\leq 2$ then follows straightforwardly. When $k=3$, we have
$S(\Pi_{2})=\\{0,1,\dots,m_{1}\\}$, then Eq. (2.8) implies, via the generating
function Eq. (3.20), that

$\mathbb{E}[q^{\sigma_{3}}]=\frac{1}{{m_{1}+m_{2}\choose
m_{1}}}[u^{m_{2}}]\left(\frac{1}{\left(1-u\right)\left(1-uq\right)\cdots\left(1-uq^{m_{1}}\right)}\right)$
(4.10)

gives the p.g.f. of the number of integer partitions into $m_{2}$ parts
selected from the set $S(\Pi_{2})$.

Using the series expansion

$\frac{1}{(1-q)^{1+l}}=\sum_{n=0}^{\infty}{n+l\choose n}q^{n},\qquad l\geq 0,$

we find that the generating function of Eq. (2.7) may be written

$\sum_{\Pi\in\mathcal{P}\left(\mathcal{M}_{k-2}\right)}\prod_{t=0}^{m_{k-2}}\frac{1}{(1-uq^{S_{t}(\Pi)})^{1+\sum_{l=1}^{k-3}\pi_{k-2,l}^{\star}(t)}}\\\
=\sum_{\Pi\in\mathcal{P}\left(\mathcal{M}_{k-2}\right)}\prod_{t=0}^{m_{k-2}}\sum_{n=0}^{\infty}{n+\sum_{l=1}^{k-3}\pi_{k-2,l}^{\star}(t)\choose
n}u^{n}q^{nS_{t}(\Pi)}$ (4.11)

Due to the technique used when constructing a basic, bivariate generating
function for restricted integer partitions, we straightforwardly have that the
r.h.s. of Eq. (4.11) may be written

$\sum_{\Pi\in\mathcal{P}\left(\mathcal{M}_{k-2}\right)}\prod_{t=0}^{m_{k-2}}\sum_{n=0}^{\infty}{n+\sum_{l=1}^{k-3}\pi_{k-2,l}^{\star}(t)\choose
n}u^{n}q^{nS_{t}(\Pi)}\\\
=\sum_{m_{k-1}=0}^{\infty}\sum_{\nu=0}^{\infty}\left[\sum_{\Pi\in\mathcal{P}([m_{k-2}\times
m_{k-1}])\atop
S(\Pi_{k-2})\cdot\pi^{\star}(\Pi)=\nu}\prod_{t=0}^{m_{k-2}}{\pi^{\star}(t)+\sum_{l=1}^{k-3}\pi_{k-2,l}^{\star}(t)\choose\pi^{\star}(t)}\right]q^{\nu}u^{m_{k-1}},$
(4.12)

and so the univariate generating function of Eq. (2.7) may be written as the
following power series,

$\frac{1}{{m_{1}+\cdots+m_{k-1}\choose
m_{1},\ldots,m_{k-1}}}[u^{m_{k-1}}]\sum_{\Pi\in\mathcal{P}\left(\mathcal{M}_{k-2}\right)}\prod_{t=0}^{m_{k-2}}\frac{1}{(1-uq^{S_{t}(\Pi)})^{1+\sum_{l=1}^{k-3}\pi_{k-2,l}^{\star}(t)}}\\\
=\frac{1}{{m_{1}+\cdots+m_{k-1}\choose
m_{1},\ldots,m_{k-1}}}\sum_{n=0}^{\infty}\left[\sum_{\Pi\in\mathcal{P}\left(\mathcal{M}_{k-2}\right)}\sum_{\pi\in{\cal
P}([m_{k-2}\times m_{k-1}])\atop
S(\Pi)\cdot\pi^{\star}=n}\prod_{t=0}^{m_{k-2}}{\pi^{\star}(t)+\sum_{l=1}^{k-3}\pi_{k-2,l}^{\star}(t)\choose\pi^{\star}(t)}\right]q^{n},$
(4.13)

which provides the conclusion. ∎

#### Acknowledgements

We thank Marc Barthelemy, Ginestra Bianconi, Carl P. Dettmann, Orestis
Georgiou, Suhanya Jayaprakasam, Jon Keating, Sunwoo Kim, Georgie Knight and
Dusit Niyato for many helpful discussions. This research is supported by the
Ministry of Education, Singapore, under its AcRF Tier 1 grant
MOE2018-T1-001-201 RG25/18. The first author was also partially supported by
the EPSRC grant Random Walks on Random Networks, Institutional Sponsorship
2015, and thanks Jürgen Jost for kind hospitality at the Max Plank Institute
for Mathematics in the Sciences, Leipzig, during part of this study in 2018.
We would also like to thank Szabolcs Horvát for his development of the IGraphM
package in Mathematica [50], used throughout this research.

## References

  * [1] M. Barthelemy, _Morphogenesis of Spatial Networks_. Springer International Publishing, 2018.
  * [2] A. P. Kartun-Giles, M. Barthelemy, and C. P. Dettmann, “Shape of shortest paths in random spatial networks,” _Phys. Rev. E_ , vol. 100, p. 032315, 2019\.
  * [3] O. Georgiou, C. Dettmann, and J. Coon, “Network connectivity through small openings,” _Proc. ISWCS ’13, Ilmenau, Germany_ , pp. 1–5, August 2013.
  * [4] O. Georgiou, M. Z. Bocus, M. R. Rahman, C. P. Dettmann, and J. P. Coon, “Network connectivity in non-convex domains with reflections,” _IEEE Communications Letters_ , vol. 19, no. 3, pp. 427–430, Mar. 2015.
  * [5] O. Georgiou, “Algebraic connectivity of keyhole random geometric graphs,” _IEEE Communications Letters_ , vol. 20, no. 10, pp. 2079–2082, Oct. 2016\.
  * [6] A. P. Giles, O. Georgiou, and C. P. Dettmann, “Connectivity of soft random geometric graphs over annuli,” _J. Stat. Phys._ , vol. 162, no. 4, p. 1068–1083, January 2016.
  * [7] D. Mulder and G. Bianconi, “Network geometry and complexity,” _Journal of Statistical Physics_ , vol. 173, no. 3-4, pp. 783–805, Jul. 2018.
  * [8] W. Cunningham, K. Zuev, and D. Krioukov, “Navigability of random geometric graphs in the universe and other spacetimes,” _Scientific Reports_ , vol. 7, no. 1, Aug. 2017.
  * [9] N. Fountoulakis and J. Yukich, “Limit theory for isolated and extreme points in hyperbolic random geometric graphs,” _Electronic Journal of Probability_ , vol. 25, no. 0, 2020.
  * [10] M. Wilsher, C. P. Dettmann, and A. Ganesh, “Connectivity in one-dimensional soft random geometric graphs,” 2020.
  * [11] A. P. Kartun-Giles, K. Koufos, X. Lu, N. Privault, and D. Niyato, “Two-hop connectivity to the roadside in a vanet under the random connection model,” 2020\.
  * [12] M. Penrose, _Random Geometric Graphs_. Oxford University Presss, May 2003.
  * [13] A. Drory, “Exact solution of a one-dimensional continuum percolation model,” _Physical Review E_ , vol. 55, no. 4, pp. 3878–3885, Apr. 1997.
  * [14] G. Knight, A. P. Kartun-Giles, O. Georgiou, and C. P. Dettmann, “Counting geodesic paths in 1-d vanets,” _IEEE Wireless Communications Letters_ , vol. 6, no. 1, pp. 110–113, Feb 2017.
  * [15] G. Grimmett, _Probability on Graphs_. Cambridge University Press, 2010.
  * [16] M. Boguna, I. Bonamassa, M. D. Domenico, S. Havlin, D. Krioukov, and M. A. Serrano, “Network geometry,” 2020.
  * [17] E. H. Lieb, D. C. Mattis, and F. J. Dyson, “Mathematical physics in one dimension: Exactly soluble models of interacting particles,” _Physics Today_ , vol. 20, no. 9, pp. 81–82, Sep. 1967.
  * [18] ——, “Mathematical physics in one dimension: Exactly soluble models of interacting particles,” _Physics Today_ , vol. 20, no. 9, pp. 81–82, Sep. 1967.
  * [19] S. Tesoro, I. Ali, A. N. Morozov, N. Sulaiman, and D. Marenduzzo, “A one-dimensional statistical mechanics model for nucleosome positioning on genomic DNA,” _Physical Biology_ , vol. 13, no. 1, p. 016004, feb 2016\.
  * [20] N. C. Pesheva and D. P. Daneva and J. G. Brankov, “Self-organized criticality in 1D stochastic traffic flow model” _Reports on Mathematical Physics_ , vol. 40, no. 3, 1997\.
  * [21] D. Krioukov, “Clustering implies geometry in networks,” _Phys. Rev. Lett._ , vol. 116, p. 208302, May 2016.
  * [22] R. Meester and R. Roy, _Continuum Percolation_. Cambridge University Press, 1996.
  * [23] D. Shalitin, “Continuous percolation in one dimension,” _Journal of Physics A: Mathematical and General_ , vol. 14, no. 8, pp. 1983–1992, aug 1981\.
  * [24] G. Gori, M. Michelangeli, N. Defenu, and A. Trombettoni, “One-dimensional long-range percolation: A numerical study,” _Physical Review E_ , vol. 96, no. 1, Jul. 2017.
  * [25] C. H. Foh and B. S. Lee, “A closed form network connectivity formula one-dimensional MANETs,” in _2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577)_. IEEE, 2004.
  * [26] C. H. Foh, G. Liu, B. S. Lee, B.-C. Seet, K.-J. Wong, and C. P. Fu, “Network connectivity of one-dimensional MANETs with random waypoint movement,” _IEEE Communications Letters_ , vol. 9, no. 1, pp. 31–33, 2005.
  * [27] G. Han and A. Makowski, “A very strong zero-one law for connectivity in one-dimensional geometric random graphs,” _IEEE Communications Letters_ , vol. 11, no. 1, pp. 55–57, Jan. 2007.
  * [28] Y. Shang, “Connectivity in a random interval graph with access points,” _Information Processing Letters_ , vol. 109, no. 9, pp. 446–449, Apr. 2009\.
  * [29] S. C. Ng, W. Zhang, Y. Zhang, Y. Yang, and Guoqiang, “Analysis of access and connectivity probabilities in vehicular relay networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 29, no. 1, pp. 140–150, Jan. 2011.
  * [30] W. Zhang, Y. Chen, Y. Yang, X. Wang, Y. Zhang, X. Hong, and G. Mao, “Multi-hop connectivity probability in infrastructure-based vehicular networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 30, no. 4, pp. 740–747, 2012.
  * [31] Z. Zhang, G. Mao, and B. D. O. Anderson, “Stochastic characterization of information propagation process in vehicular ad hoc networks,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 15, no. 1, pp. 122–135, Feb. 2014.
  * [32] G. Mao, _Connectivity of Communication Networks_. Springer International Publishing, 2017.
  * [33] V. M. Ajeer, P. Neelakantan, and A. Babu, “Network connectivity of one-dimensional vehicular ad hoc network,” in _2011 International Conference on Communications and Signal Processing_. IEEE, Feb. 2011.
  * [34] P. Gupta and P. R. Kumar, “Critical power for asymptotic connectivity in wireless networks,” in _Stochastic Analysis, Control, Optimization and Applications_. Birkhäuser Boston, 1999, pp. 547–566.
  * [35] K. Koufos and C. P. Dettmann, “Temporal correlation of interference in bounded mobile ad hoc networks with blockage,” _IEEE Communications Letters_ , vol. 20, no. 12, pp. 2494–2497, Dec 2016.
  * [36] ——, “Temporal correlation of interference and outage in mobile networks over one-dimensional finite regions,” _IEEE Transactions on Mobile Computing_ , vol. 17, no. 2, pp. 475–487, Feb 2018.
  * [37] K. Koufos and C. P. Dettmann, “The meta distribution of the SIR in linear motorway vanets,” _IEEE Trans. Comms._ , vol. 67, no. 12, pp. 8696-8706, Sep 2019.
  * [38] A. Kartun-Giles, S. Jayaprakasam, and S. Kim, “Euclidean matchings in ultra-dense networks,” _IEEE Communications Letters_ , vol. 22, no. 6, pp. 1216–1219, June 2018.
  * [39] A. P. Kartun-Giles, K. Koufos, and S. Kim, “Meta distribution of SIR in ultra-dense networks with bipartite euclidean matchings,” arXiv:1910.13216, 2020.
  * [40] B. Gupta, S. K. Iyer, and D. Manjunath, “Topological properties of the one dimensional exponential random geometric graph,” _Random Structures and Algorithms_ , vol. 32, no. 2, pp. 181–204, 2008.
  * [41] E. Godehardt and J. Jaworski, “On the connectivity of a random interval graph,” _Random Structures and Algorithms_ , vol. 9, no. 1-2, pp. 137–161, Aug. 1996.
  * [42] C. Domb, “Covering by random intervals and one-dimensional continuum percolation,” _Journal of Statistical Physics_ , vol. 55, no. 1-2, pp. 441–460, Apr. 1989.
  * [43] M. Krivelevich, K. Panagiotou, M. Penrose, and C. McDiarmid, _Random Graphs, Geometry and Asymptotic Structure_ , N. Fountoulakis and D. Hefetz, Eds. Cambridge University Press, 2016.
  * [44] A. P. Giles, O. Georgiou, and C. P. Dettmann, “Betweenness centrality in dense random geometric networks,” in _2015 IEEE International Conference on Communications (ICC)_. IEEE, Jun. 2015\.
  * [45] A. P. Kartun-Giles and S. Kim, “Counting k-hop paths in the random connection model,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 5, pp. 3201–3210, May 2018.
  * [46] A. Kartun-Giles, D. Krioukov, J. Gleeson, Y. Moreno, and G. Bianconi, “Sparse power-law network model for reliable statistical predictions based on sampled data,” _Entropy_ , vol. 20, no. 4, p. 257, 2018.
  * [47] A. P. Kartun-Giles, “Connectivity and centrality in dense random geometric graphs,” 2016.
  * [48] N. Privault, “Moments of k-hop counts in the random-connection model,” _Journal of Applied Probability_ , vol. 56, no. 4, pp. 1106–1121, Dec. 2019\.
  * [49] S. Janson, “Generalized Galois Numbers, Inversions, Lattice Paths, Ferrers Diagrams and Limit Theorems,” _The Electronic Journal of Combinatorics_ , vol. 19, no. 3, Sep. 2012.
  * [50] S. Horvát, IGraph/M—the igraph interface for Mathematica, http://szhorvat.net/mathematica/IGraphM, doi:10.5281/zenodo.1134932

##  Appendix A Appendix A: Code for Monte Carlo corroboration

Here we contain the code used to corroborate Eq. (2.6), for the case $k=3$ and
$k=4$. The output of this code is the two graphs in Figs. 4.6 and 4.7

Listing 1: Example code

⬇

1makeedges =

2 Function[{subsets, r0},

3 Select[subsets,

4 Abs[#[[1]] - #[[2]]] < r0 &]];(*Make the edges of the graph*)

5graph[vert_, r0_] :=

6 Graph[vert,

7 UndirectedEdge @@@

8 makeedges[Subsets[vert, {2}],

9 r0]];(*Make the 1d random geometric graph*)

10makegraph[nv_, coord_, width_, height_, r0_] :=

11 Module[{pts, newvertices, newedges, edges, alledges, allpts, e1, e2,

12 ew}, allpts = Table[RandomReal[{-width/2, width/2}], {i, 1, nv}];

13 allpts = Join[allpts, coord];

14 pdg1 = graph[allpts, r0]];

15Clear[r0];

16domainwidth = 1;

17mk3hops[n_, r0_, k_] := Module[{gr, pthcount, m1, m2},

18 m1 = 7;

19 m2 = 7;

20 pt1 = RandomReal[{0.5 - 2 r0, r0 - 0.5}, m1];

21 pt2 = RandomReal[{0.5 - r0, 2 r0 - 0.5}, m2];

22 ptall = Join[pt1, pt2, {-0.5, 0.5}];

23 gr = makegraph[0, ptall, domainwidth, 0.002, r0];

24 pthcount = Length[FindPath[gr, -0.5, 0.5, {k}, All]];

25 pthcount];

26mk4hops[n_, r0_, k_] := Module[{gr, pthcount, m1, m2, m3},

27 m1 = 5;

28 m2 = 5;

29 m3 = 5;

30 pt1 = RandomReal[{0.5 - 3 r0, r0 - 0.5}, m1];

31 pt2 = RandomReal[{0.5 - 2 r0, 2 r0 - 0.5}, m2];

32 pt3 = RandomReal[{0.5 - r0, 3 r0 - 0.5}, m3];

33 ptall = Join[pt1, pt2, pt3, {-0.5, 0.5}];

34 gr = makegraph[0, ptall, domainwidth, 0.002, r0];

35 pthcount = Length[FindPath[gr, -0.5, 0.5, {k}, All]];

36 pthcount];

37data1 = Table[mk3hops[0, 0.35, 3], {i, 1, 50000}];

38d3 = HistogramList[data1, {1}, ”Probability”][[2, All]];

39d4 = Transpose[{Range[0, Length@d3 - 1], d3}];

40ser1 = Series[QBinomial[14, 7, q], {q, 0, 49}];

41cf1 = CoefficientList[ser1, q];

42d1 = Transpose[{Range[0, Length@cf1 - 1],

43 N@(1/Binomial[14, 7]) cf1}];

44ListPlot[{d1, d4},

45 Joined -> {True,

46 False}](**Plot a graph of the coefficients against the Monte Carlo \

47simulation for k=3**)

48

49data2 = Table[mk4hops[0, 0.27, 4], {i, 1, 50000}];

50bincnts = (Join[{0}, PositionIndex[#][0], {Length[#] + 1}] //

51 Rest[#] - 1 -

52 Most[#] &) &;(*Count balls in bins,to get the part counts of \

53the complementary partition*)

54nt[x_] := Module[{a}, If[x == 1, a = 0;]; If[x == 0, a = 1;]; a]

55tf[x_] := Module[{a, li}, a = bincnts@x;

56 li = {};

57 For[i = 1, i <= Length@a, i++,

58 For[j = 1, j <= a[[i]], j++, li = Append[li, i - 1];];];

59 {Prepend[Accumulate@li, 0], bincnts[nt[#] & /@ x]}]

60g[x_] := Product[

61 1/(1 - u q^tf[x][[1, t + 1]])^(1 + tf[x][[2, t + 1]]), {t, 0, 5}]

62d7 = Transpose[{Table[i, {i, 0, 125}],

63 1/Multinomial[5, 5, 5] CoefficientList[

64 CoefficientList[

65 Series[Total[

66 g[#] & /@ Permutations[{0, 0, 0, 0, 0, 1, 1, 1, 1, 1}]], {u,

67 0, 5}], u][[6]], q]}];

68d5 = HistogramList[data2, {1}, ”Probability”][[2, All]];

69d6 = Transpose[{Range[0, Length@d5 - 1], d5}];

70ListPlot[{d7, d6},

71 Joined -> {True,

72 False}](**Plot a graph of the coefficients against the Monte Carlo \

73simulation for k=4**)