key: cord-0474240-raprhr6l
authors: Nikolopoulos, Pavlos; Guo, Tao; Fragouli, Christina; Diggavi, Suhas
title: Community aware group testing
date: 2020-07-16
journal: nan
DOI: nan
sha: e7dcfc265fa97a497f0238cf19e5fa6bbbb1d7ac
doc_id: 474240
cord_uid: raprhr6l

Group testing pools together diagnostic samples to reduce the number of tests needed to identify infected members in a population. The observation we make in this paper is that we can leverage a known community structure to make group testing more efficient. For example, if $n$ population members are partitioned into $F$ families, then in some cases we need a number of tests that increases (almost) linearly with $k_f$, the number of families that have at least one infected member, as opposed to $k$, the total number of infected members. We show that taking into account community structure allows to reduce the number of tests needed for adaptive and non-adaptive group testing, and can improve the reliability in the case where tests are noisy.

Group testing pools together diagnostic samples to reduce the number of tests needed to identify infected members in a population. In particular, if in a population of n members we have a small fraction infected (say k n members), we can identify the infected members using as low as O(k log( n k )) group tests, as opposed to n individual tests [6, 1] . Triggered by the need of widespread testing, such techniques are already being explored in the context of Covid-19 [9, 2, 7, 19, 8] . Group testing has a rich history of several decades dating back to R. Dorfman in 1943 and a number of variations and setups have been examined in the literature [5, 6, 1, 20] .

The observation we make in this paper is that we can leverage a known community structure to make group testing more efficient. The work in group testing we know of, assumes "independent" infections, and ignores that an infection is governed by community spread; we argue that taking into account the community structure can lead to significant savings. As a use case, consider an apartment building consisting of F families that have practiced social distancing; clearly there is a strong correlation on whether members of the same family are infected or not. Assume that the building management would like to test all members to enable access to common facilities. We ask, what is the most test-efficient way to do so.

Our approach enlarges the regime where group testing can offer benefits over individual testing. Indeed, a limitation of group testing is that it does not offer benefits when k grows linearly with n [14, 10, 18] . Taking into account the community structure allows to identify and remove from the population large groups of infected members, thus reducing their proportion and converting a linear to a sparse regime identification. Essentially, the community structure can guide us on when to use individual, and when group testing.

Our main results are as follows. Assume that n population members are partitioned into F families, out of which k f families have at least one infected member.

• We derive a lower bound on the number of tests, that for some regimes increases (almost) linearly with k f (the number of infected families) as opposed to k (the number of infected members).

• We propose an adaptive algorithm that achieves the lower bound in some parameter regimes.

• We find that non-adaptive testing cannot leverage the community structure to reduce the number of tests if we require zero error rate; however, it can do so, if we tolerate some false positive errors.

• We argue that community structure can improve the reliability when tests are noisy.

• We numerically explore regimes where use of community structure can offer benefits.

The paper is organized as follows. Our notation is in section 2, the lower bound in section 3, algorithms for the noiseless case are in section 4 and for the noisy in section 5, numerical results are in section 6.

The traditional group testing setup assumes a population of n members out of which some are infected. Two models are considered: (i) in the combinatorial model, there is a fixed number of infected members k , selected uniformly at random among all sets of size k ; (ii) in the probabilistic model, each item is infected independently of all others with probability p. Let N = {1, 2, · · · , n} be the set of members, and K the set of infected members.

A group test τ takes as input samples from n τ individuals, pools them together and outputs a single value: positive if any one of the samples is infected, and negative if none is infected. More precisely, let x i = 1 when individual i is infected and 0 otherwise. Then the traditional group testing output y τ takes a binary value calculated as:

where stands for the OR operator (disjunction) and δ τ is the group of people participating in the test. The performance of a group testing algorithm is measured by the number of group tests T = T (n) needed to identify the infected members (for the probabilistic model, the expected number of tests needed). Several setups have been explored in the literature, that include: • Adaptive vs. nonadaptive testing: In adaptive testing, we use the outcome of previous tests to decide what tests to perform next. An example of adaptive testing is binary splitting, which implements a form of binary search. Non-adaptive testing constructs, in advance, a test matrix G ∈ {0, 1} T ×n where each row corresponds to one test, each column to one member, and the nonzero elements determine the set δ τ . Although adaptive testing uses less tests than nonadaptive, nonadaptive testing is more practical as all tests can be executed in parallel.

• Scaling regimes of operation: assume k = Θ(n α ), we say we operate in the linear regime if α = 1; in the sparse regime if 0 ≤ α < 1; in the very sparse regime if k is constant.

Known results. The following are well established results (see [12, 6, 1] and references therein):

• It is easy to see that since T tests allow to distinguish among 2 T combinations of test outputs, we need at least that 2 T ≥ n k , which in turn implies that we cannot use less than T = O(k log n k ) tests; this is known as the counting bound [12, 6, 1] .

• Noiseless adaptive testing allows to achieve the counting bound for k = Θ(n α ) and 0 ≤ α < 1; for non-adaptive testing, this is also true of 0 ≤ α < 0.5 if we allow a vanishing (with n) error. • In the linear regime (α = 1), group testing offers little (if any) benefits over individual testing [14, 10, 18] . In particular, if p j = p ≥ 0.38, group testing does not use less tests than one-to-one (individual) testing [14, 10, 18] (see also [16] for phase transitions for noiseless and noisy testing).

In this paper, we additionally assume a known community structure: the population can be decomposed in F disjoint sets of families, where family j has M j members and n = F j=1 M j . In the symmetric case, M j = M for all j and n = F M . We consider the following infection models, that parallel the ones in the traditional setup 1 .

• Combinatorial Model (I). k f of the families have at least one infected member (we will call these infected families). The rest of the families have no infected members. In each infected family j, there exist k j m infected members, with 0 ≤ k j m ≤ M . In the symmetric case, k j m = k m for all j. • Probabilistic Model (II). A family is infected with probability q i.i.d. across the families. A member of an infected family is infected, independently from the other members (and other families), with probability p j . The rest of the families have no infected members. For k j m = p j M j the two models behave similarly.

In this work we assume that there is no dilution noise. That is, the performance of a test does not depend on the number of samples pooled together. This is a reasonable assumption with genetic RT-PCR tests used in virus detection where the genetic material is "amplified" and thus even small amounts of viral nucleotides can be amplified to be detectable [15] .

In this paper, we additionally assume a known community structure: the pop composed in F disjoint sets of families, where family j has M j members and n = symmetric case, M j = M for all j and n = F M. We consider the following infe parallel the ones in the traditional setup.

• Combinatorial Model (I).

There are k f families that have at least one inf will call these infected families). The rest of the families have no infected member family j, there exist k j m infected members, with 0  k j m  M . In the symmetric all infected families j.

• Probabilistic Model (II). A family is infected with probability q i.i.d. a A member of an infected family is infected, independently from the other me families), with probability p j . The rest of the families have no infected member For k j m = p j M j the two models behave similarly.

Observation 1. Although in this paper we focus on the two above models, sev be treated in very similar fashion. For instance, we could have F 1 families that (with probability p 1 ! 1), F 2 families mildly infected (with probability say p remaining families having no infected members.

In this work we assume that there is no dilution noise. That is, the performance depend on the number of samples pooled together. This is a reasonable assumpt ... Suhas could you add here?

In section 4 we assume access to noiseless tests that have perfect accuracy consider noisy testing according to the Z-channel model, illustrated in Figur output that should be positive, flips and appears as negative with probability z Y ⌧Ŷ ⌧ In section 4 we assume access to noiseless tests that have perfect accuracy. In section 5 we consider noisy testing according to the Z-channel model in Figure 1 , where a test output that should be positive, flips and appears as negative with probability z . Though our focus is on this noise model, the ideas could be extended to other noise models.

Letx i denote the estimate of the state of x i after group testing. Zero error captures the requirement thatx i = x i for all i ∈ N . Vanishing error refers to that all error probabilities go to zero with n. Sometimes we distinguish between False Negatives (FN) and False Positives (FP) errors, where Pr(FN) = Pr(x i = 0|x i = 1), Pr(FP) = Pr(x i = 1|x i = 0).

(2.2)

We compute the minimum number of tests needed to identify all infected members under the zeroerror criterion in both community models I and II, starting from model I. All proofs of this section are in Appendix A. Any algorithm that identifies all infected members k with T and without error requires

In the symmetric case, the above lower bound becomes:

1 Although in this paper we focus on these two models, several variations can be treated in very similar fashion. For instance, we could have F1 families that are highly infected (with probability p1 − → 1), F2 families mildly infected (with probability say p2 p1) and the remaining families having no infected members.

Observations: We make two observations regarding the bound of Theorem 3.1: (a) When the number of infected families k f follows a sparse regime (i.e., when k f = Θ(F α f ) for α f ∈ [0, 1)), the bound increases almost linearly with k f (the number of infected families), as opposed to k (the overall number of infected members). This is because, in such a sparse regime, the following asymptotic equivalences hold:

When the number(s) of infected family members k j m follows a "strongly" linear regime (i.e. k j m = p j M j for p j → 1), the community bound may be significantly lower than the counting bound, k log 2 n k , that does not take into account the community structure (see known results in section 2.1). This is because k m ≈ M j and the asymptotic behavior of the counting bound can be obtained through the fundamental lower bound of the binomial coefficient:

As a result, the ratio of the counting bound to the combinatorial symmetric bound scales as follows:

Similar results hold for the probabilistic community model:

. Consider the probabilistic model (of §2.2). Any algorithm that identifies all infected members k without error requires a number of tests T satisfying:

where h 2 is the binary entropy function. In the symmetric case, we have: T ≥ F (h 2 (q) + qM h 2 (p)) .

Observation: The combinatorial and probabilistic bounds are asymptotically equivalent. For example, using standard estimates of the binomial coefficient, one may see that the combinatorial bound 3.1 is asymptotically equivalent to

wherek f andk j m are the expected values. A respective equivalence holds for the symmetric case: the combinatorial bound is asymptotically equivalent to

In this section, we provide group-testing algorithms for the noiseless case that leverage the community structure. We start from adaptive algorithms and then proceed to two-stage and non-adaptive.

Alg. 1 describes our algorithm for the fully adaptive case, that consists of two parts. In both parts, we make use of a classic adaptive-group-testing algorithm AdaptiveTest(), which is an abstraction Algorithm 1 Adaptive Community Testinĝ U i is the estimated infection status of member i ("positive" or "negative"). U z is the estimated infection status of a mixed sample z ("positive" or "negative"). SelectRepresentatives() is a function that selects a representative subset from a set of members. AdaptiveTest() is an adaptive algorithm that tests a set of items (mixed samples or members). r j = SelectRepresentatives ({i : i ∈ j }) 3: end for 4: Û z (r 1 ) , . . . ,Û z (r F ) = AdaptiveTest (z (r 1 ), . . . , z (r F )) 5: Set A := ∅ 6: for j = 1, . . . , F do 7: ifÛ z (r j ) = "positive" then 8:

Use a noiseless, individual test for each family member:Û i = U i , ∀i ∈ j . 14: return Û 1 , . . . ,Û n for any existing (or future) adaptive group-testing algorithm. We distinguish between 2 different kinds of input for AdaptiveTest(): (a) any set of selected members, which is the typical input of group-testing algorithms; (b) any set of selected mixed samples. A mixed sample is created by pooling together samples from multiple members that usually have some common characteristic. For example, mixed sample z (r j ) denotes an aggregate sample of a set of representative members r j from family j . We call a mixed sample "infected," if at least one of the members that compose it is infected, and "non-infected" otherwise. Because in some cases we only care whether a mixed sample is infected or not, we can treat it in the same way as an individual sample-hence use group testing to identify the state of mixed samples as we do for individuals.

Part 1 (lines 1-4): First, a representative subset r j of family-j members is selected using a sampling function SelectRepresentatives() (lines 1-3). Then, a mixed sample z (r j ) is produced for each representative subset r j , and an adaptive group-testing algorithm is performed on top of all representative mixed samples (line 4). If our choice of AdaptiveTest() offers exact reconstruction (which is usually the case), then:Û z (r j ) = U z (r j ) .

Part 2 (lines 5-13): We treatÛ z (r j ) as an estimate of the infection regime inside family j : if U z (r j ) is positive, then we consider the infection rate of the family to be high (i.e k j m/M j or p j ≥ 0.38), otherwise low (i.e. k j m/M j or p j < 0.38). Since group testing performs better than individual testing only in the latter case (section 2.1), we use individual testing for each heavily-infected family (lines 7-8), and an adaptive group test for all lightly-infected ones (line 13).

We discuss the rationale behind Alg. 1 in detail in Appendix B.

Analysis for the number of tests. We now compute the maximum expected number of tests needed by our algorithm to detect the infection status of all members without error. To this end, we consider a uniform (random) sampling function for the SelectRepresentatives() and 2 choices for the AdaptiveTest() algorithm: (i) binary-splitting [17] (which is the classic case and performs well when little is known about the actual numbers of infected families/members), and (ii) Hwang's binary-splitting [11] (which is optimal if the numbers of infected families/members are known in advance, but cannot be considered in the probabilistic case where these numbers are unknown). For simplicity of notation, we present our results through the symmetric case, where M j = M , k j m = k m (combinatorial case) or p j = p (probabilistic case), and |r j | = R for all families 2 :

Lemma 4.1 (Expected number of tests -Symmetric combinatorial model). Consider the choices (i) and (ii) about AdaptiveTest() defined above. Alg. 1 needs a number of tests given by: 

is the expected fraction of infected families that are detected as heavily infected in Part 1 and the inequality is because of the randomness of binary splitting.

Two observations: (a) Given that the infection regime of each family is detected without error in Part 1, our algorithm can asymptotically achieve the lower combinatorial bound of Theorem 3.1 in particular community structures. For example, in a sparse regime across families (where k f = Θ(F α f ) for α f ∈ [0, 1)) and a moderately linear regime within families (where km /M is close to 0.5), the lower bound becomes

, which is equivalent to Ineq. 4.2 for φ c = 1. Another example is the opposite case, where the regime across families is heavily linear and the regime within families is sparse (i.e. k = k f k m ≈ k f ): the lower bound in that case is T ≈ k f log 2 ( F /kf ) + k f k m log 2 ( M /km) ≈ k log 2 ( n /k), which is equivalent to Ineq. 4.2 for φ c = 0 (zero-error detection of the light infection regime of each family). However, we should notice that the above is possible only if the numbers of infected families/members are known in advance, hence Hwang's binary splitting can be used in place of the AdaptiveTest() algorithm (which is also what is required by classic adaptive group testing to achieve the counting bound [1]-we claim no improvement on this front). (b) Ineq. 4.1 shows that our algorithm achieves significant benefits compared to classic binary splitting when the families are heavily-infected and all of them are correctly detected (in which case

and it is never worse, when families are lightlyinfected and none of them is detected otherwise (in which case φ c = 0 and E T (i) ≤ k log 2 n). Since the former case (heavy infection) is more realistic, our algorithm is expected to perform a lot better than classic group testing in practice.

The adaptive algorithm can be easily implemented as a two-stage algorithm, where we first perform one round of tests, see the outcomes, and then design and perform a second round of tests. The first round of tests implement part 1, checking whether a family is highly infected or not; the second round of tests implement part 2, performing individual tests for the members of the highly infected families, and in parallel, group testing for the members of the remaining families.

As we did before for the adaptive case, we here make use of a classic non-adaptive-grouptesting algorithm, which we call NonAdaptiveTest(). This may be regarded as an abstraction for any existing (or future) non-adaptive algorithm in the group-testing literature. Note also that we can implement individual one-to-one testing using an identity test matrix in a non-adaptive manner.

Thus to translate Algorithm 1 to a two-stage algorithm lines 4 and 14 simply become:

Number of tests: In some regimes, the two-stage algorithm can operate with the (same order) number of tests as the adaptive algorithm, at a cost of a vanishing error probability: for example, for the tests in line 4, if 

Test Matrix Structure. We divide the test matrix G into two sub-matrices:

The sub-matrix G 1 of size T 1 × n identifies the infected families using one mixed sample from each family -namely implements (4.4) . In the worst case, T 1 = F , where we use one row for each family test; in sparse k f regimes, T 1 can be closer to O(k f log F k f ). The sub-matrix G 2 of size T 2 × n has a block matrix structure and contains F identity matrices I M , one for each family 3 . Assume that F = ab and that b i (i ∈ {1, 2, · · · , a}) are positive integers such that a i=1 b i = F . G 2 contains b i matrices I M in the i-th block matrix row and one I M in each block matrix column. An example with F = 6, a = 3, b 1 = 2, b 2 = 1, b 3 = 3 is Note that T 2 = aM . In Appendix C.2 we provide a rationale on this choice of structure for G 2 .

Decoding. From the outcome of the tests in G 1 we identify the F −k f not-infected families, and proceed to remove the corresponding columns (not-infected members) from G 2 . We use the remaining columns of G 2 to identify infected members according to the rules:

(ii) All other members, that are only included in positive tests in G 2 , are identified as infected. These rules follow the logic of combinatorial orthogonal matching pursuit (COMP) decoding [4, 3] .

Error Probability. We observe that:

• Requiring zero-error decoding is too rigid: the optimal solution is the trivial solution that tests each member individually. Lemma C.1 in Appendix C.1 proves that for zero-error we need T 2 ≥ n.

• The symmetric choice b i = b minimizes the error probability. Note that our decoding strategy leads to zero FN errors. Thus we want to design G 2 to minimize FP errors. A FP may happen if identity matrices I M corresponding to two infected families appear in the same block row of G 2 . In this case, some not-infected members may be covered by infected members from other families and identified as infected by error. The probability that two infected families are tested in the same set of M tests is obtained for the combinatorial (I) and probabilistic (II) model as follows: Pr(all-FP) = Pr(∃i :

For the symmetric probabilistic model (II):

The system Pr(all-FP) can be pessimistic; a better metric may be the average fraction of noninfected members that are identified as infected (FP rate) calculated for models I and II as:

where

We plot the Pr(all-FP) and rate in Figure 2 , for parameters F = 64, k f = 4, k m = 4, M = 5, q = 1/16, and p = 0.8.

Leveraging community structure can improve the reliability when the test outputs are noisy. We make this point through simple error calculations for a particular case in this section, and through numerical evaluation in section 6. An extended version and all proofs are in Appendix D.

Reliability of Testing. Assume that positive test outputs can flip with probability z , as illustrated by the Z-channel in Figure 1 , and consider for now individual tests. To improve reliability we need to add redundancy (extra tests). We explore the following ways to do so:

(1) Repetition testing, where each individual test is repeated times, and thus we use T = n tests. Assuming the decoding rule in eq. (D.1) that uses a parameter δ, we get that

Just as in coding theory, repetition is not very efficient as a coding mechanism.

(2) Group testing, where now each group test can be viewed as a form of coding, aiming to introduce redundancy to correct errors due to noise. We consider two classes of testing matrices G: Bernoulli designs (akin to binary random coding) and constant weight designs (akin to constant weight random coding).

Bernoulli design: each item is included in each test iid at random with probability θ. Constant weight design: each item is included in L tests, chosen uniformly at random. For the decision rule in (D.7) that uses a parameter δ, we get that

Using the Community Structure. We adapt the two-stage algorithm developed in Section 4.2 by introducing redundancy using the constant weight testing design 4 where we set L = T k . We want to compare this against group testing that again uses the same mechanism for redundancy but does not take into account the community structure. We use the following notation. 7)). In such a case Q 3 = 0, at the cost of a slight increase in false positive probability (see Appendix D for FP analyses). Note that

where we use T 1 tests for the first and T 2 tests for the second stage. Therefore

which suggests that for T 1 = cT with c a constant, the upper bound for Pr(FN|community structure) can be exponentially smaller than the upper bound for Q = Pr(FN|no community).

Our adaptive algorithm (Alg. 1) achieves the lower bound, if particular conditions about the community structure hold. But, being an adaptive algorithm, it needs time to identify all infected member as a round of tests may start only if the results of a previous round of tests are available.

On the other hand, our nonadaptive algorithms (of sections 4.2, 4.3 and 5) can be parallelized to save time, but this comes at the cost of an increased number of tests and/or a positive error rate.

In this section, we evaluate the performance of our adaptive algorithm in practical scenarios. We are also interested in the additional cost of using our nonadaptive algorithms instead. There are two types of the cost that we care for: (i) the number of tests and (ii) the error rate. For each scenario, we allocate the infected items to members/students according to the probabilistic model II (of Section 2.2): in each of them, a family/class is first selected at random w.p. q to be infected and then each of its members/students become randomly infected w.p. p ∈ [0.3, 0.95]. When varying p, we pay particular attention to also vary q accordingly (q =k Mp ), so that the overall infection regime is the one defined in (a) and (b), above. To obtain results that are statistically significant, for each choice of p, we average over up to 250 randomly generated such allocations. All these allocations constitute the various randomized "runs" of the following 2 experiments:

(i) Performance comparison in terms of the actual number of tests. In each run, we reconstruct the infection status of all members/students using: Alg. 1 with R = 1 (i.e. we select one representative per family/class), Alg. 1 with R = M (the entire family/class is pooled together in the mixed sample), classic binary splitting and a version of our nonadaptive algorithm ( §4.3), which has no false negatives and a FP error rate that is similar across all runs (around 0.03). In the end, we compute the actual number of tests required by each of these algorithms to identify the entire set of members/students. To validly compare their performance none of these algorithms assumes prior knowledge about the number of infected families/classes or members/students. So, Alg. 1 uses classic binary splitting as for the AdaptiveTest() algorithm.

(ii) Performance comparison in terms of the actual error rate. In each run, we first reconstruct the infection status of all members/students using Alg. 1 with R = M . Then we do the same with all our nonadaptive algorithms ( §4.2, §4.3), and two different versions of nonadaptive noisy testing that use a Z-channel model for noise (with z = 0.15) and LP decoding (as described in Appendix D.1.3): one version ("noisy-C") that takes the community structure into account (as in §5), and another one ("noisy-NC") that does not. We force all algorithms to use the same number of tests needed by Alg. 1. In the end, we compute the actual error rate achieved by all algorithms as the fraction of members for which the infection status estimated by the algorithm is different than the actual one.

Results: We obtained similar results for all community structures we examined; for brevity, we show here only the most interesting ones. of our adaptive algorithm offer significant benefits compared to classic binary splitting (in both the linear and the sparse regime), while staying below the counting bound. For example, for p = 0.7, our adaptive algorithm that uses R = M needs only 307 tests on average in the linear regime (resp. 65 tests in the sparse regime) instead of 860 (resp. 285) tests that are required by the binary splitting algorithm; even the counting bound is much higher: 464 and 200 respectively. This is a quantified example of the potential benefits from the community structure, even when the exact number of infected members cannot be known in advance. More interestingly, Alg. 1 with R = M j performs close to the lower bound ( §3) in most realistic cases (where p ∈ [0.5, 0.8]). Additionally, as expected in the linear regime, binary splitting is not close to the counting bound; for a similar reason, Alg. 1 (which uses binary splitting as for AdaptiveTest()) performs closer to the lower bound in the sparse regime than in the linear. Last, we observe that the non-adaptive version comes at the cost of an increased number of tests: in the linear regime (Fig. 3a) , the non-adaptive does not perform very well as our results show that individual testing would be preferable in cases where p ≤ 0.8, but our results are more promising for the more realistic sparse-regime case (Fig. 3b) , where our non-adaptive algorithm seems to offer significant benefits when p > 0.6 (of course at the cost of a positive FP rate, yet being free from false negatives by construction). we plot the average error rate achieved over all 50 runs. As expected, Alg. 1 has a zero error rate in all runs. But, the performance of the 2-stage is not far away from optimal (in fact it is very close to exact reconstruction). On the other hand, our nonadaptive algorithm seems to perform worse; however, its error consists only of false positives and zero false negatives (which is important in the context of disease testing). Last, when noiseless group-testing is not available (green and blue curves), the error rate becomes higher in general, but as we observe, the knowledge of the community structure (in noisy-C) reduces the error rate by more than 20% in most cases, compared to classic community-unaware noisy testing (noisy-NC). Through the results of experiment (ii), we may therefore visualize the significant benefits that the knowledge of the community structure may offer in terms of reliability. 

possible sets of infected members that each must give a different set of results. Thus,

which reveals the result. The RHS of the latter inequality is because there are F k f combinations of infected families, and for each infected family j , there are Given the community model II, the joint entropy becomes:

The symmetric bound is obtained as a corollary by taking M j = M and p j = p for each infected family j . The goal of Part 1 is to detect the infection regime inside each family j : i.e., to accurately estimate which of the F families have a high infection rate ("heavily" infected) and which are have a low or zero infection rate ("lightly" infected). Our interest in detecting the infection regime is motivated by prior work [14, 10] , which has shown that group testing offers benefits over individual testing, only if the infection rate is low (p j ≤ 0.38). This allows us to define the two regimes as follows: In the combinatorial model I (resp. probabilistic model II), a is considered heavily infected when k j m/M j ≥ 0.38 (resp. p j ≥ 0.38); conversely, it is considered lightly infected family when k j m/M j < 0.38 (resp. p j < 0.38). For each family j , we regardÛ z (r j ) as an estimate of the family's infection regime. IfÛ z (r j ) is positive, we consider the family to be highly infected and therefore perform individual testing for all of its members. Otherwise, ifÛ z (r j ) is negative, we consider the family to be lightly infected and group test its members with all other lightly infected families. The challenge is therefore to produce accurate enough regime estimates, such that the overall number of tests that are needed from Alg. 1 to achieve exact infection-status reconstruction for all members i = 1, . . . , n is minimal. We discuss this challenge further below.

Given all estimatesÛ z (r j ) from Part 1, the goal of the Part 2 is then to identify all infected members, by using the appropriate testing method (group or individual testing) according to the infection regime of each family (light or heavy). In this way, at the end of Part 2, the algorithm returns an estimateÛ i of the true infection status U i of each individual member i .

Selection of family representatives: Function SelectRepresentatives() at line 2 refers to any sampling function on a set of family members, as long as it returns a fixed number of members from family j . A configurable cardinality of the representative subset |r j | is essential in our context; it affects the accuracy of regime estimate-hence the performance of our algorithm in terms of the expected number of tests that it uses. Differentially said, one may use their own sampling function, as long as the accuracy of Part 1 is well defined.

In this paper, we consider only random-sampling functions without replacement (i.e. |r j | members are randomly chosen from the family members and each subset of that size has the same probability of being selected as the representative subset). But perhaps, more elaborate sampling functions may be considered in other contexts, where the community models provide information about the internal contact structure of each family. For example, if the internal structure of family j can be represented through a contact graph, in which only specific family nodes have external contacts with other families, it may make more sense to include (some of) these nodes into the representative with certainty.

Adaptive group testing: In both parts of our algorithm, we make use of a classic adaptivegroup-testing algorithm, which we call AdaptiveTest(). This may be regarded as an abstraction for any existing (or future) adaptive algorithm in the group-testing literature. In our analysis, however, we mostly focus on the classic binary splitting algorithm because of its good performance in realistic cases, where the numbers of infected families and/or members (k f , k j m ) are unknown [17] . In this section, we consider only adaptive algorithms that offer noiseless (zero-error) reconstruction. Note, however, the fact that AdaptiveTest() offers exact reconstruction is not enough to guarantee an accurate detection of any family's infection regime in Part 1. For example, consider the following case, where the true infection rate within a family j is not very low (say p j = 0.6), yet none of the family representative in set r j happened to be infected. Intuitively, the error probability of detection in Part 1 should depend on the number of selected representatives |r j | from each family j and the infection rate among its members p j . In our analysis, we examine different scenaria w.r.t. these parameters and discuss which parametrization (i.e. value of |r j |) optimizes the expected number of the tests required by our algorithm. We also discuss noisy group testing in Section §5.

One modification of our algorithm is the following: In Part 1 we select from each family m s non overlaying representative subgroups each of size s (as opposed to one representative group) with the hope to increase the estimation accuracy ofp j and reduce the error of the related hypothesis test, at the cost of spending a few more tests. We treat each of these subgroups as a single "member": that is, we will identify whether each subgroup is positive (has at least one positive member) or not. Based on this, we will classify the family. Algorithm 1 may just be regarded as a special case of this when m s = 1 and s = |r j |.

This modification is related to Hwang's binary splitting algorithm, which does not require prior knowledge about the numbers of the infected families or the infected members. As a result, we expect it to use fewer tests on expectation than our algorithm and perform better in some cases. However, the improvement is not expected to be large. So, to keep things simple, we prefer not to analyze this algorithm in this paper and differ it to future work.

Another modification could be the following: instead of leveraging the community structure to preform individual tests where needed, we could use it to reduce the number of tests of the binary splitting algorithm in the case where the number of infected members is unknown. For example, consider a symmetric case, where we split all n = FM members into M of F people, one from each family; then, use binary splitting to each group.

This modification is also related to Hwang's binary splitting algorithm, but achieves only logarithmic benefits compared to binary splitting, as opposed to our algorithm that may perform much better in real cases (see section 4.1). In fact, the expected number of tests needed by this modified algorithm would be at most k log 2 ( n /M ) + O(k ): each group g has k g infected member and binary splitting needs k g log 2 ( n /M ) + O(k g ) tests to identify all of them. By adding together the number of tests for each group g, we deduce the result. For line 13, the expected number of items that are tested is: n−k f φ c M , and the expected number of infected members is:

. So, the expected number of tests performed by a binary splitting algorithm is:

. And, the expected number of tests performed by Hwang's binary splitting is:

We add together all the above terms that are related to the binary splitting or Hwang's algorithm, and the result follows. (1 − φ p ) . So, the expected number of tests performed by a binary splitting algorithm is:

We add together all the above terms that are related to the binary splitting or Hwang's algorithm, and the result follows.

C Appendix for section 4.3: The Noiseless Nonadaptive case C.1 Zero error requirements Lemma C.1. For G 2 to achieves zero-error we need T 2 ≥ n.

Proof. A trivial implementation for G 2 is to use an identity matrix of size n; since each member is tested individually, we can identify all the infected members correctly. We next argue that T 2 ≥ n for the zero-error case. We prove this through contradiction. Assume that T 2 < n. Then, from the pigeonhole principle, there exists one member, say m 1 that does not participate in any test alone -it always participates together with one or more members from a set S 1 . Assume that all members in S 1 are infected, while m 1 belongs in an infected family but is not infected -our decoding will result in a FP.

Observation: G 2 leads to zero error if and only if it has the following property: Zero Error Property: Any subset of {1, 2, · · · , n} of size (F − k f )m + k f (m − k m ) equals the union of some testing rows of G 2 . Namely, the members of the not-infected families together with the not-infected members of the infected families, need to be the only participants in some rows of G 2 , for all possible not-infected families and not-infected members. This requirement can lead to an alternative proof of lemma C.1.

Our goal is to design a non-trivial matrix G 2 that can identify almost all the infected members with high probability and a small number of tests. We next discuss two intuitive properties we would like our designs to have to minimize the error probability.

Desirable Property 1: Use identity matrices as building blocks. Ideally, after removing the (F − k f )M columns corresponding to the members in non-infected families, we would like the remaining columns to form an identity matrix so that we can identify all the infected members correctly. To reduce the number of tests, there should be more than one members included in each test. Thus we use overlapping identity matrices, one corresponding to each family. We assume the index for the n members is family-by-family, i.e., the indexes for the members in the same family are consecutive. Then each family corresponds to an identity sub-matrix I M in G 2 . Now the problem becomes how to arrange the identity sub-matrices.

Desirable Property 2: The identity matrices corresponding to different families either appear in the same set of M rows in G 2 or they do not appear in any shared rows. Indeed, otherwise, a family may share tests with more than two other families. This would increase the probability that two infected families share tests after removing all the non-infected family columns, which in turn would increase the FP probability.

Lemma C.2. The system FP probability Pr(all-FP) = Pr(∃i :x i = 1|x i = 0) is minimized for both combinatorial and probabilistic models when b i = b, namely, we can restrict our attention to matrices of the form:

which is simply the concatenation of b identity matrices I aM .

Proof.

For the combinatorial model, we can verify the difference of the probability for b i and b i by

where X is a positive value independent of b i and b j . This implies that the minimum of the probability P I overlap in (4.7) achieves its minimum roughly at the symmetric case where all b i 's are equal, i.e., b i = b for all i ∈ {1, 2, · · · , a}.

Similarly, for the probabilistic model, consider the probability in (4.7), we can calculate that 

For the symmetric probabilistic model, it equals

Remark 1. We have assumed that the number of families F is a multiple of a and b. If F cannot be factorized, the error probabilities in Lemma 4.4 can be viewed as an upper bound for the corresponding error probabilities. This can be seen by simply adding F auxiliary families so that F + F = ab.

Proof. The probabilities in (4.7) become

For the symmetric combinatorial model, the number of infected members in an infected family k j m = k m for all infected families j. If two families appear in the same set of M tests, the probability that all infected members in one family share the same k m tests as the other family is simply

Thus the probability that FPs happen is . Thus, the probability that there is no false positives is given as follows,

Thus the probability that a false positive happens can be obtained as

Replacing a by T 2 /M and b by FM /T 2 completes the result.

We here make two observations: (i) The system Pr(all-FP) can be too pessimistic; a better metric may be the average fraction of non-infected members that are identified as infected (FP rate). The average FP rate for the symmetric combinatorial model is

where m 0 = min(k m , M − k m ) and m 1 = max(k m , M − k m ). The average FP rate for the symmetric probabilistic model is

(ii) As we explore further in section 6 non-adaptive group testing requires more tests than adaptive.

Assume that k f = Θ(F α f ) for α f ∈ [0, 1) and choose R = M − 1 in Algorithm 1. Adaptive testing allows to achieve zero error with k f log 2 F + k f M tests; if we use the same (order) number of tests with a non-adaptive strategy, i.e.,

 which is bounded away from 0 5 .

In this section we will provide further results and some of the details used in Section 5. As mentioned earlier, we will focus on the specific Z-channel for the noise model, where positive test output can flip with probability z , illustrated in Figure 1 , reproduced below for convenience. The ideas can be generalized to other noise models, but for simplicity we analyze this to focus on the important false negative results. 

In this section we briefly analyze the performance of some testing strategies which use the traditional group testing methods, without taking into account the community structure. The goal is then to compare these with the methods that utilize the community structure, adapting algorithms considered in Section 4 for the noise-free (or noiseless) case to the case of testing with noise.

In the presence of noisy tests, the simplest way to correct for noisy tests is to test each item repeatedly, saying times. In such a strategy, the testing matrix is composed of identity matrix I n , i.e. G = [I n , · · · , I n ] T . It is well-known that a length-repetition code can correct up to −1 2 noise-related flips. For each item i ∈ N , the decision rule is given as follows,

This can be seen as follows:

is decreasing with m and can be very small when m n.

where tunable parameter δ ≥ 0 and C i = {i, i + n, · · · , i + ( − 1)n}, i ∈ N is the test set of item i.

Lemma D.1. Using the decision rule given in (D.1) the probability of false negative is bounded as,

where T is the total number of tests for a total population size n; also note that there are no false positives in this due to the Z-channel noise model.

Proof of Lemma D.1: For any item x i , the false negative probability is

where (D.5) follows from the Chernoff bound. This simple method can obtain a small false negative probability, with a large number of tests, which is times the total number of items, T = n. Next, we consider group testing which could significantly reduce the number of tests, which is analyzed for reliability.

As noted earlier, just as in coding theory, repetition is not as efficient as a coded mechanism, we analyze the performance of group testing (effectively coding), with some redundancy, for noisy tests. For the analysis we focus on two classes of testing matrix G, which are studied in literature: Bernoulli designs and constant weight designs, which were defined in Section 5 and repeated below for convenience. Let g t,i be the entries of (random) matrix G. Decoder: Ideally, one would use an optimal decoder for group testing with noise [1] , whose relaxation can be implemented using a linear program (see Section D.1.3 for details). However, such decoders are difficult to analyze (though we use it for our numerical results). For simplicity of analysis, we use a threshold-based rule to decode each item individually, described below. For each i ∈ N , we identify whether item i is an infected member through the i-th column of G. Among all the outputs corresponding to τ ∈ T such that g τ,i = 1, if the number of zeros is larger than some threshold, then we say i is an infected member. Otherwise, we say i is non-infected. Formally, for a tunable parameter δ ≥ 0, we write the decoding rule as:

x i = 0, if |{τ ∈ T :ŷ τ = 0, g τ,i = 1}| > z (1 + δ) · |{τ ∈ T : g τ,i = 1}| 1, if |{τ ∈ T :ŷ τ = 1, g τ,i = 1}| ≥ (1 − z (1 + δ)) · |{τ ∈ T : g τ,i = 1}|. (D.7)

for each i ∈ N . The Bernoulli and constant-weight testing matrices are defined in Section 5, and repeated below for convenience,

• Bernoulli design: each item is included in each test independently at random with probability θ, i.e. P (g t,i = 1) = θ, ∀ i ∈ {1, 2, · · · , n}, t ∈ T . (D.8)

• Constant weight design: each item is included in L tests, which are chosen uniformly at random, independent from the choices for all other items. In terms of the testing matrix G, we have independent columns of constant weight.

Bernoulli testing matrix: The false negative and false positive probabilities with Bernoulli design matrix are bounded as follows. Constant weight testing matrix Replacing Bernoulli testing matrix with the constant weight design in the following with the decision rule in (D.7) unchanged. Since the we test L times for each item, the decision rule can be simplified aŝ Note that the Chernoff bound requires that 1 − z (1 + δ) > a 0 which means δ < 1−z z (1 − L T ) k .

For a given testing matrix G, either constant test-per-item or Bernoulli design, we perform linear programming (LP) decoding by solving the following optimization problem: min u,ξ n i=1 u i + ζ The LP is a relaxation of the corresponding integer programming by relaxing u i ∈ {0, 1} to u i ∈ [0, 1]. The solution of u represents an estimate of the infection indicator vector, and we will round each u i to its nearest integer from {0, 1}. The slack variable ξ i has the following intuition: i) ξ i = 0 if test τ is positive or truly negative (no error); ii) ξ i = number of infected members in test τ , if the test is a false negative. The parameter ζ controls the tradeoff between declaring a small number of infected members (sparsity) and the a smaller number of Z-channel noise-related flips happen (most slack variables being zero).

Group testing: an information theory perspective

Coronavirus test shortages trigger a new strategy: Group screening

Efficient algorithms for noisy group testing

Non-adaptive group testing: Explicit bounds and novel algorithms

The detection of defective members of large population

Combinatorial Group Testing and Its Applications. Series on Applied Mathematics

Five people. one test. this is how you get there. NYtimes

Tapestry: A single-round smart pooling technique for covid-19 testing. medRxiv

Group testing against covid-19

A boundary problem for group testing

A method for detecting all defective members in a population by group testing

Strong converses for group testing from finite block-length results

Group testing with prior statistics. CoRR, abs/1401

Sharper bounds in adaptive group testing

Enzymatic amplification of beta-globin genomic sequences and restriction site analysis for diagnosis of sickle cell anemia

Phase transitions in group testing

Group testing to eliminate efficiently all defectives in a binomial sample

Cutoff points in group testing

Group testing for sars-cov-2 allows for up to 10-fold efficiency increase across realistic scenarios and testing strategies. medRxiv

Revisiting nested group testing procedures: new results, comparisons, and robustness