Arboricity Matters in Triangle Counting with Random Edges
Abstract
Given a simple, unweighted, undirected graph with and , and parameters , along with Degree, Neighbour, Pair and RandomEdge query access to , we provide a query-based randomized algorithm to generate an estimate of the number of triangles in , such that with probability at least . The query complexity of our algorithm is , where is the arboricity of . Our work can be seen as a natural progression to the line of recent works [Eden et al., SIAM J Comp., 2017; Assadi et al., ITCS 2019; Eden et al., SODA 2020] that considered subgraph or triangle counting with or without the use of RandomEdge query. Of these works, Eden et al. [SODA 2020] considers the role of arboricity. Our work is the first to consider how RandomEdge query can leverage the structural property of arboricity. Furthermore, continuing in the line of work of Assadi et al. [APPROX/RANDOM 2022], we also provide a lower bound of that matches the upper bound exactly on arboricity, , and almost on .
Keywords and phrases:
Triangle counting, Sublinear algorithms, Subgraph countingCategory:
RANDOMCopyright and License:
2012 ACM Subject Classification:
Theory of computation Streaming, sublinear and near linear time algorithmsEditors:
Mohit Singh and Tom GurSeries and Publisher:
Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
1 Introduction
Counting the number of triangles present in graphs is a classical problem [20, 5, 53, 4, 10]. Researchers in the streaming (sub-linear space) community have studied this problem for the last two decades; see [10, 11, 35, 2, 17, 6, 36, 18, 22, 55, 41] for a sample of such works. The problem has also been studied by researchers in the property testing (sub-linear time) community in the last decade [26, 48, 39, 11, 13, 28, 35]. Here, graphs can be accessed only through certain queries. On the other hand, starting with the work of [20], the graph parameter called arboricity has also found its use in triangle counting [28]. Our work shows the use of arboricity in triangle counting where the graph can be accessed through random edge queries along with other standard queries like Degree, Neighbour and Pair.
Counting triangles has been a well-motivated problem with applications across various domains like optimizing query size in database join problems [10, 9, 7], computing clustering coefficients, transitivity ratio [1, 46, 60, 44], studying structures in web graphs [25, 23] etc. For a more thorough overview, see the surveys [3, 57]. The parametrization based on arboricity is also of practical interest due to the occurrence of low-arboricity graphs in various real-world scenarios [24, 42, 50, 31, 12, 23, 54].
Formally, we are given a simple, unweighted, undirected graph with , and . The neighbours of is denoted and the degree of the vertex is denoted . We are given the following queries to access the graph:
-
: Given a vertex , return .
-
: Given a vertex and , return the -th vertex if it exists; otherwise, we get .
-
: Given two vertices , return if , and , otherwise.
-
RandomEdge: Return an edge uniformly at random.
We will call the Degree, Neighbour and Pair queries taken together to be local queries [7]. Now, we formally state our problem:
Triangle Estimation:
Given with , obtain an estimate of the number of triangles in
the graph , such that with probability at least .
From now on, we refer to be an estimate of . One of the graph parameters that has been relevant to quantify the complexity of triangle counting algorithms within the context of RAM model [20], streaming model [13], distributed model [34, 56, 30, 45] and query model [29], is the arboricity of the graph , denoted . The arboricity of a graph can be seen as a measure of the density of the graph.
Definition 1 (Arboricity).
The arboricity of a graph , denoted , is the minimum number of spanning forests that can be partitioned into.
Recent works have established various ways to construct lower bounds incorporating the impact of and both in graph property testing [8] and other problems [58]. Our lower bounds will also involve and . To illustrate the dependence of , , and polylog terms on the query complexity of our algorithm, we will use two notations at times in place of – hides polylog factors only but shows dependence on and , whereas hides both , and polylog terms.
1.1 Our results
In this section, we present the main results of this work.
Upper bound
We show that using random edge queries in addition to local queries, we can obtain an estimate of where the query complexity is parametrized by arboricity apart from the usual parameters of edge, vertex, the number of triangles, , and . The work of [20] established the role of arboricity in the problem of triangle counting giving an time algorithm to exactly count the number of triangles in the RAM model. In recent works in the property testing model, [26] gave an algorithm that uses local queries and requires queries to obtain an estimate of . Using RandomEdge in addition to the local queries, [7] proposed an algorithm that uses queries. Following this, [28] was introduces the parameter of arboricity to triangle counting in the query based setup. They proposed an algorithm that uses local queries to obtain an estimate of . Our work follows in the line of the works of [26, 7, 28], where we use RandomEdge in addition to local queries to obtain an algorithm that uses queries (see the last row in Table 1). Formally,
Theorem 2 (Upper bound).
Given a simple, unweighted and undirected graph with , and arboricity , and access to the graph via Degree, Neighbour, Pair and RandomEdge queries, an estimate of can be obtained using queries.
A constant-pass space streaming algorithm was proposed in [13] for obtaining an -estimate of the number of triangles in a graph, where is the degeneracy of the graph. Our algorithm can be directly extended to a constant pass streaming algorithm using space. By the fact that , our algorithm’s space complexity is as good as the algorithm of [13] in terms of the graph parameters, and asymptotically better in terms of the approximation factor .
Lower bound
We also establish a lower bound involving the arboricity and the parameters and . Reductions from communication complexity is a well studied method to establish lower bound results in terms of query complexity [15, 29, 32]. Using only Degree and Neighbour queries, triangle counting requires queries [33]. Including Pair with the previous two queries, [26] established a lower bound of queries which matches their upper bound up to factors. Later, a simpler proof was proposed for the same bound through reduction from communication complexity problems [29]. This was subsequently extended to incorporate arboricity with a bound of queries [28] which again matched their proposed upper bound up to factors. If RandomEdge query is allowed along with all three local queries, the above lower bounds of and become [29] and [28], respectively. 111Though [28] does not mention about explicitly, it is not difficult to see it from their construction. Also, this lower bound of matches with our upper bound (stated in Theorem 2) in terms of dependence on , and . As we have mentioned, for general graphs, there is an algorithm that makes queries, where each query is either a local query or a RandomEdge query [7]. Recently, in [8], it has been shown that the algorithm of [7] is optimal (up to factors) in terms of all parameters including and through a lower bound of queries for obtaining an estimate of using local and RandomEdge queries. However, this does not consider the dependency of the query complexity on arboricity of the graph. Like our upper bound, the lower bound of our work also captures the role of arboricity and the parameters , and when the queries allowed are the local and the RandomEdge queries. Moreover, our lower bound combines the parametrization of [8] and [28] in terms of , , and , respectively, to establish an improved lower bound.
Theorem 3 (Lower bound).
Given a simple, unweighted and undirected graph with , and arboricity , and access to the graph via Degree, Neighbour, Pair and RandomEdge queries, obtaining an estimate of requires queries.
| Without RandomEdge | With RandomEdge | |
|---|---|---|
| Without Arboricity | UB: [26] | UB: [7] |
| LB: [8] | LB: [8] | |
| With Arboricity | UB: [28] | () UB: |
| () LB: | () LB: |
Table 1 describes the upper and lower bounds across different query accesses and parametrization for the triangle counting problem, with our contributions in this work highlighted with an asterisk () mark. Table 1 shows that it is only natural to study the problem of triangle estimation with the use of RandomEdge and arboricity as a parameter after the works of [26, 28, 7, 8]. We believe our work also raises some new questions: (a) it opens up the question of quantifying the impact of to count other subgraphs (e.g., k-cliques) using RandomEdge and other local queries; (b) there remains a small gap of between our upper and lower bounds that remain to be resolved.
1.2 Related work in other models
The problem of triangle counting is a problem that has been extensively studied across various models of computation. Here, we discuss the works in RAM and streaming models.
RAM model.
Streaming model.
In the data streaming model, a long line of work [51, 52] has culminated in an -space one-pass streaming algorithm for insertion only model [39] that has been shown to be optimal through the combined lower bounds proposed in [16, 39]. Here, () denote the maximum number of triangles incident on an edge (a vertex ) in the graph . There have been works on triangle counting in multi-pass setup as well as in other streaming models (e.g., turnstile, cash-register etc.) [48, 11, 39, 37, 38, 40, 13].
1.3 Paper organization
Section 2 discusses a broad overview of the techniques we use, and contextualizes it with respect to the relevant prior works. Section 3 sets up the preliminaries for our proofs, including the structural results involving arboricity of a graph. Section 4 discusses the query-based algorithm by breaking the discussion into several parts: a weight function (Section 4.1), an oracle based algorithm (Sections 4.2) and its implementation (Section 4.3) and the final algorithm (Section 4.4). The lower bounds are discussed in Section 5. Some of the proofs are deferred to the Appendix. We have also included the full version of the paper in the Appendix.
2 Technical overview
In this section, we give a broad overview of the techniques used in this work. We denote by the number of triangles incident on the edge , and the degree of an edge by .
2.1 Upper bound
Our starting point is to use RandomEdge queries to obtain , a random sample of edges of size and try to estimate the number of triangles incident on the edges of . As the RandomEdge query samples edges uniformly at random, the expected number of triangles each sampled edge participates in is . Hence, an obvious approach to estimate would be to count the number of triangles each edge participates in, and take their average for the sampled edges and scale it appropriately. However, there are two issues with this approach.
Firstly, counting the number of triangles an edge participates in exactly would require local queries. Therefore, we have to sample sufficiently many neighbour vertices for each edge and check if it forms a triangle or not to obtain a good estimate of .
Secondly, even though the expected number of triangles incident on each edge is , individual edges can participate in a large number of triangles, i.e., can be . This makes the variance of the estimate too high, and requires to be large to obtain a good estimate. To work around this issue, we fix a threshold based on the arboricity of the graph, that has a connection to the number of triangles in the graph. We call edges that participates in more than triangles -heavy edges. Correspondingly, any edge that participates in less than triangles is called -light edges. For now, assume we are given access to an oracle Heavy to decide whether an edge is light or heavy. We call the triangles consisting exclusively of heavy edges as heavy triangles, and the remaining triangles as light triangles. The threshold is set at an appropriate multiple of so that heavy triangles constitute only fraction of the triangles. Thus, we can forget about the -heavy edges and focus only on counting the light triangles. This brings us to the issue of sampling light triangles uniformly at random. We define a weight function on the edges that assigns each light triangle to one of its constituent light edges. The weight function is defined to be the number of light triangles assigned to the edge, with each heavy edge being assigned a value of .
Now the algorithm’s objective is to estimate this weight function, which cannot be accessed or sampled directly. Observe that there can be multiple assignments of the light triangles to the edges, and consequently multiple weight functions. It suffices for the algorithm to estimate any one of them. In that regard, for all the light edges in our sample , we maintain a partial non-conflicting assignment. Such an assignment can be extended to a valid assignment, and consequently, a valid weight function. Based on this assignment, we obtain an estimate of the corresponding weight function, which, given an appropriately fixed threshold , and setting to will give an estimate of .
To design the oracle Heavy for a given edge , we estimate the number of triangles each edge participates in. We can estimate it by sampling each triangle independently through the corresponding neighbouring vertex of . The probability of obtaining a triangle for an edge through a random neighbour is . Hence, for the heavy edges where , can be estimated using sufficiently small number of queries. For the light edges where , the probability of obtaining a triangle through a random neighbour can be arbitrarily low. However, note that the lower probability of obtaining triangles allows for high approximation error. We then design a bucketing trick to exploit this trade-off to implement an efficient algorithm to decide whether an edge is heavy or light. For full details, see Section 4.
2.2 Lower bound
Several lower bounds for triangle counting problems based on reductions from the disjointness problem in communication complexity [29, 7, 28] are often close to the best possible upper bounds. It is not clear whether this approach can give tight bounds involving and . Recently, Assadi and Nguyen [8] showed that any algorithm to find an -estimate of the number of triangles must make at least queries, where each query is either a local query or a RandomEdge query.222Note that this lower bound matches exactly with the corresponding upper bound in [7]. To prove the lower bound, they introduced a new query problem called the Popcount Thresholding Problem (PTP), and gave reductions from this problem to triangle estimation, instead of using disjointness. We also show a reduction from PTP. In particular, we show that for any value of arboricity , we can design a graph with arboricity such that finding an -estimate in it using queries would violate the lower bound of PTP.
In the problem, we are given query access to a binary string and must decide whether it was generated from one of two similar distributions. In the first distribution, denoted , each bit of the string is independently set to 1 with probability ; in the second distribution, denoted , each bit is independently set to 1 with probability . The objective is to distinguish between these two cases by adaptively querying bits of . For suitable choice of ,, and , with probability at least , a string from will have fewer than s and a string from will have more than s. Hence, to distinguish whether is generated from or , it suffices to estimate the number of s present in , i.e. upto multiplicative approximation factor . Assadi et al. [8] showed that (under suitable choice of parameters) queries to are needed to distinguish between the case whether and with probability .
We now describe the hard graph instance used in the reduction. The core structure of consists of three vertex sets: , , and , where and . Every vertex in is connected to all vertices in , forming a bipartite clique between and . The subgraph induced by contains edges, with each vertex having degree at most . We associate each index from the instance with a potential edge between and , and include the edge if and only if . Thus, the number of edges between and equals , and the total number of triangles in the graph is . By choosing parameters such that , , and , distinguishing whether is drawn from or becomes equivalent to distinguishing whether the number of triangles in the graph is at most or at least . To complete the reduction, we show that each local query and RandomEdge query to can be simulated using only a constant number of queries to . To enable this, we extend the construction by introducing two additional disjoint vertex sets and , resulting in five disjoint sets: , , , , and . All triangles in the graph are confined to the sets , , and , while the sets and are added to ensure that the degree of each vertex in remains identical regardless of whether is drawn from or . With this construction, every allowable query to the graph can be simulated with queries to . For full details, see Section 5.
2.3 Contextualizing with relevant prior work
Our work follows as a natural progression to the works of [26, 7, 28] in the property testing framework. So, let us review the algorithmic techniques at play in them.
We start by describing a simple randomized algorithm due to Assadi et al. [7] for estimating the number of triangles in a graph when we have access to queries like Degree, Neighbour, Pair, and RandomEdge. First, pick a random edge and let . If , pick a random neighbour of and check if forms a triangle in the correct order, i.e., in the increasing degree sequence. The probability of sampling a triangle in this case is . If , pick a vertex at random with probability proportional to its degree. This is possible because RandomEdge allows sampling vertices proportional to their degrees. The probability of sampling a triangle in this case is . By setting , we can ensure that the algorithm works effectively. This process finds a triangle with probability . Finally, by repeating this process times, we can estimate the total number of triangles.
The setting seems to be the optimal choice for the general case. We do not see a way to generalize the above idea when parametrized by arboricity. In bounded arboricity graphs, the structure and degree distribution of the graph may not align with this approach. So, a different strategy would be required for graphs with bounded arboricity to achieve the desired bound of .
Our approach is more closely aligned with the framework of triangle counting developed by Eden et al. [26] with access to local queries only. The algorithm by Eden et al. [26] starts by picking a small set of vertices at random and for each sampled vertex, the algorithm tries to estimate the number of triangles it participates in. Some vertices appear in many triangles and are called heavy, while others are called light. To keep the estimate as desired, the algorithm limits the contribution of heavy vertices and focuses mainly on light ones. It gives more weight to triangles that have more light vertices. Since the number of triangles a vertex participates in cannot be obtained directly, the algorithm estimates this by sampling edges incident on the sampled vertices and checking if they close triangles with neighbouring vertices of those edges. The above framework has also been subsequently extended for clique counting in general graphs [28] and that in bounded arboricity graphs [28].
In summary, the idea of dividing the triangles in terms of their constituent edges or vertices into heavy and light, and dealing with them separately has been a long-standing technique for subgraph counting in sublinear models [48, 26, 11, 27, 38, 28, 13]. The algorithmic techniques vary on how to set and leverage this thresholding behaviour for the specific problems and models. Furthermore, allowing RandomEdge queries has yielded simpler algorithms for subgraph counting problems [7]. The usage of RandomEdge enables us to design a simple algorithm that uses the structural parameter of arboricity.
The lower bounds for the triangle counting problem in the query model have come from indistinguishability arguments [26] or reduction from communication problems, particularly set-disjointness [29, 7, 28] with [28] establishing arboricity-sensitive lower bounds. On the other hand, several recent works [14, 8] have established lower bounds for property testing problems through reductions to query problems that are sensitive to and . In this work, we extend the -sensitive lower bound of [8] to the triangle counting problem for any value of arboricity .
3 Preliminaries
3.1 Notations
The set of positive integers is denoted . The set of triangles in is denoted , and individual triangles are denoted . denotes a triangle formed by the vertices and the endpoints of the edge . denotes an element of is chosen uniformly at random.
3.2 Arboricity and its properties
As arboricity plays a crucial role in our work, we put together all the structural results that involve arboricity here. Let us restate the definition once more.
Definition 4 (Arboricity).
The arboricity of a graph , denoted by , is the minimum number of spanning forests that can be partitioned into.
The arboricity of a graph can be seen as a measure of the density of the graph. can be at least . Also, where is any subgraph of . We will write instead of when the underlying graph is understood. We introduce the following result due to [20] on the sum of edge degrees over all edges in the graph.
Lemma 5 (Sum of [20]).
Given a graph with arboricity and , .
The following result due to [28] builds on the work of [20] to bound the number of triangles based on the number of edges and arboricity .
Lemma 6 (Triangle upper bound [28]).
Given a graph with arboricity and , the graph has at most triangles.
Note that this upper bound is also tight, i.e., there exists graphs that contain edges and triangles. Additionally, arboricity can be at most [28]. Thus, all our results can be reformulated by plugging in this upper bound.
3.3 Chernoff bounds
We will be using the following variation of the Chernoff bound that bounds the deviation of the sum of independent Poisson trials [49].
Lemma 7 (Multiplicative Chernoff bound).
Given i.i.d. random variables where and , define . Then, we have:
4 Algorithm
This section describes the algorithm and its related concepts. Section 4.1 formally defines the weight function for edges and associated structural results. Section 4.2 describes the algorithm assuming access to an idealized oracle that can decide if an edge is heavy or light (based on whether the edge has many or few incident triangles). Section 4.3 describes how to actually implement this oracle within the problem setup. Section 4.4 puts everything together to develop the final algorithm.
4.1 Weight function
In this section, we formalize the ideas of heavy and light edges and weight function for the edges.
Heavy and light edges and triangles
First, we define heavy and light edges and correspondingly, heavy and light triangles.
Definition 8 (-heavy and -light edges).
An edge is defined to be a -heavy (resp. -light) edge if it participates in more than (resp. ) triangles.
Definition 9 (-heavy and -light triangles).
A triangle is called a -heavy triangle if all its three edges are -heavy edges. A triangle that is not -heavy is a -light triangle.
We denote by and the number of -light and -heavy triangles in the graph , respectively. The following lemma bounds the number of -heavy triangles in a graph using the parameter of arboricity.
Lemma 10 (Upper bound on ).
Given a graph with triangles, the number of -heavy triangles is at most .
Proof.
Note that the graph has triangles containing at most edges. By Definition 9, -heavy triangles have all three of their edges to be -heavy edges, or more triangles incident on each of them. Hence, the number of -heavy edges in is at most .
Now consider the subgraph of induced by the -heavy edges in . We know, . Also, (see Section 3.2). Hence, by Lemma 6, we know that contains at most triangles.
The following corollary follows from Lemma 10 and the fact that .
Corollary 11 (Lower bound on ).
Given a graph , there are at least -light triangles.
Weight function for the edges
Now, we define a weight function for the edges. As a triangle is incident to multiple edges, the objective of a weight function is to charge each of the light triangles to exactly one of its participating light edges. To ensure this, we do not charge any light triangle to any heavy edge that it may be incident on. Each light edge can be charged by at most triangles, i.e., all the triangles the edge participates in. To avoid over-counting, we ensure that the sum of the weight function over all edges is equal to the number of light triangles, . denotes that the triangle is charged to the edge .
Definition 12 (Triangle weight function ).
We define a function to be a triangle weight function if it satisfies the following two conditions:
Observe that there are multiple such weight functions (e.g., a triangle with 3 light edges can be assigned to any one of these 3 edges). Henceforth, we denote the set consisting of valid triangle weight functions by . We now state a property of valid weight functions. Note that this property is true for any .
Lemma 13 (Expectation of ).
Consider any triangle weight function . If we select an edge uniformly at random, then the expected value of is , i.e., .
Proof.
Given that the edges have been chosen uniformly at random and the condition of the triangle weight function (Definition 12), we have:
4.2 Oracle based algorithm
Our algorithm, due to its usage of the triangle weight function, requires knowledge of whether an edge is heavy or light. The problem of deciding whether an edge is heavy is non-trivial as it directly relates to number of triangles the edge participates in. In this section, we assume black-box access to an oracle HeavyOracle that helps us determine if an edge is heavy.
Here and are constants to be determined later. We will discuss an efficient implementation of this oracle later.
Let us first consider the case where we are given an oracle that given an edge , returns the exact value of a weight function, . Given we can sample edges uniformly at random through the RandomEdge query, we can compute using this oracle on the sampled edges. However, no such oracle exists in our model. Hence, we try to simulate one through an empirical estimate of the weight function, . Recall the fact that there are many valid weight functions, each being characterized by every light triangle being charged to one of its constituent light edges. Our algorithm will work if the empirical weight function estimates any one of these weight functions. We achieve this by ensuring that a triangle is not sampled through more than one edge (see Line 17 of Algorithm 1). Thus, the assignments that we consider can be extended to a valid weight function , and our algorithm can be thought of as estimating this weight function through . We develop our initial algorithm (Algorithm 1) assuming , an estimate of satisfying .
In Algorithm 1, we assume that we know exactly. In fact, our algorithm and analysis work even if we have a constant factor approximation of . This can be achieved by using queries [7].
We now state and analyse the algorithm.
Proof.
Let be the event that the edge is chosen as the -th edge sample. We proceed with the proof by considering two different cases: and .
Case I: ().
When , is set to with probability and 1 with probability , and is evaluated through a single query. Thus,
| (1) |
Case II: ().
On the other hand, when , let be the contribution of each queries made for the edge to the weight function estimate. Then,
| (2) |
Correspondingly, we have by linearity of expectation and Equation (2):
| (3) |
Given that we draw each edge uniformly at random, we now have by Equations (1), (3), and Lemma 13:
By linearity of expectations, we obtain
Note that Lemma 14 holds irrespective of whether the assumption is satisfied or not. Next, we turn our attention to the variance of .
Proof.
Again, we consider two different cases as in the proof of Lemma 14.
Case I: ().
When , Algorithm 1 makes at most query as . As , we have
| (4) |
Case II: ().
Now we consider the case which is more involved as . We first estimate the variance of each individually as defined in Lemma 14. We condition on the event that edge is chosen as the -th edge sample, denoted by . If , then . Hence, we condition on the event that from now on. As ,
| (5) |
After having bounded the variance of the contribution of each query, we now obtain the variance of the weight estimate of the edge.
| ( are i.i.d. given ) | |||||
| (by Equation (5) and linearity of expectation) | |||||
| (6) | |||||
Proof.
The algorithm calls HeavyOracle for each of the edges in , resulting in a total of calls.
The algorithm makes RandomEdge queries, Degree queries, and Neighbour query for each edge . All edges in are sampled uniformly at random from . Hence, the expected number of Neighbour queries made are:
The last inequality in the above step follows from Lemma 5. Hence, the algorithm makes at most queries in expectation. Here the inequality is due to the fact that for a heavy edge in , . Furthermore, we bound the variance of the estimate as:
The last two steps follow from Lemma 15 and the fact that . We now use Chebyshev’s inequality on :
| (Chebyshev’s inequality) | ||||
| (by Lemma 15) | ||||
| (by Lemma 14) | ||||
| (as ) |
where the last inequality uses the fact due to the assumption that .
4.3 Implementing the oracle
Rather than the exact oracle (HeavyOracle) that we assumed in Algorithm 1, we would design an oracle (called Heavy) that given arboricity , and parameters and , accepts edges participating in at most triangles as light, and rejects edges participating in at least triangles as heavy, with probability at least . The algorithm works by estimating the number of triangles each edge participates in. However, in this case, each Neighbour and Pair queries generate i.i.d. random variables denoting the existence of triangle through that neighbouring vertex. Thus, our analysis uses the multiplicative Chernoff bound to obtain high probability guarantees for each individual edge.
Lemma 17 (Estimation guarantee of Heavy).
The algorithm satisfies the following properties with probability at least : (i) returns edge if it is -heavy; (ii) returns edge if it is -light.
Proof.
For (i), we only consider edges that have at least triangles. In this case, the random variables ( as in Algorithm 2; if and form a triangle; , otherwise) are i.i.d. Bernoulli random variables taking value with probability at least . Hence, we have the following using linearity of expectation:
As , we can upper bound the probability of the algorithm returning for the edge , by a multiplicative Chernoff bound (Lemma 7) as follows:
| (by multiplicative Chernoff bound) | ||||
For (ii), we do not have a lower bound on the probability of success in general and hence we cannot obtain a lower bound on . Now, observe that for the edges that participate in very few triangles, the probability of finding triangles (i.e., getting ) is low. However, such light edges can still tolerate a high approximation error to be accepted (as a light edge). To account for the trade-off between the lower bound on the probability of and the upper bound on the approximation factor, we divide the edges participating in at most triangles into buckets with each bucket being defined as the set of edges . For each of these buckets, observe that when Heavy is called for an edge belonging to the bucket, we have , and hence .
On the other hand, we have , and hence, . Using these observations, we complete the proof by considering any in these buckets:
| (by multiplicative Chernoff bound) | |||||
Lemma 17 shows that Algorithm 2 can decide whether an edge is heavy or not with probability at least using iterations; making 2 Degree, 1 Neighbour and 1 Pair queries in each iteration. For an individual edge, can be at most , and hence the subroutine might contribute to additional queries for each edge. However, as part of Algorithm 1, Heavy is called on a set of edges drawn uniformly at random. Hence, in the following lemma, we bound the expected number of queries made by Heavy when called on edges that were drawn uniformly at random.
Lemma 18 (Query complexity of Heavy).
makes queries in expectation on an edge .
Proof.
For edge , makes iterations with each iteration making queries. Hence, the expected number of queries is:
| (by Lemma 5) | |||||
4.4 Finalizing the algorithm
In this section, we combine the algorithms discussed above to obtain our final algorithm. Our goal is to call Heavy with appropriate parameters instead of HeavyOracle so that the approximation error due to the heavy triangles not being counted remains small. We also derive the query complexity of the algorithm including the queries made through Heavy.
4.4.1 Algorithm with an estimate
Theorem 19 (Performance guarantees of Algorithm 3).
Algorithm 3 makes at most queries in expectation and returns such that .
Proof.
Algorithm 3 will make the same number of calls to Heavy as did Algorithm 1 to HeavyOracle. By Theorem 16, Algorithm 3 makes queries and calls to Heavy. By Lemma 18, each call to Heavy requires queries in expectation. Combining with the fact that we have , the algorithm requires queries in expectation.
By Lemma 17, we can use as an implementation of the idealized . This ensures that a -light edge is accepted and a -heavy edge is rejected with probability at least . By union bound, the algorithm accepts all -light edges and rejects all -heavy edges in with probability at least . Hence, by Corollary 11 and Lemma 14, we have,
| (7) |
By Theorem 16, we have that:
| (8) |
4.4.2 Getting rid of the assumption on
In this section, we describe the steps to obtain Theorem 22 from Theorem 19. First, we remove the assumption on the knowledge of for Algorithm 3. To achieve that, we search for an appropriate choice of starting from and halving it each time we fail to find a satisfying the assumption that . We must also bound the probability of deviating significantly below . To ensure that, for each value of , we run Algorithm 3 using values of as .
First we bound the probability that the Algorithm 4 terminates at a choice of that does not satisfy the assumption that .
Lemma 20 (Termination bound of Algorithm 4).
When , the algorithm terminates with probability at most .
Proof.
Lemma 21 (Lower bound of for Algorithm 4).
The algorithm reaches a value of with probability at most .
Proof.
For every such value of , we have a in Line 2 of Algorithm 4 such that . By Theorem 19, the algorithm returns an estimate with probability at least . Taking a union bound over possible values of , we have Algorithm 4 returning an such that with probability at least , and the algorithm terminates.
Hence, to get to a , Algorithm 4 must have failed to terminate for all previous values of , which happens with probability at most .
Finally we combine Lemmas 20 and 21 to obtain the following theorem quantifying the estimation guarantees and query complexity of Algorithm 4. The following theorem formalizes the Theorem 2 of Section 1.1.
Theorem 22 (Upper bound - Formal).
There exists an algorithm that makes queries in expectation, and returns with probability at least .
Proof.
The algorithm runs through at most values of such that . By Lemma 20, the algorithm terminates in each such case with probability at most . For each value of , by Theorem 19, the algorithm returns a wrong value with probability at most . There are at most such values of . Taking an union bound and fixing the constant appropriately, the algorithm returns a correct output with probability at least .
5 Lower bound
In this section, we prove a lower bound that accounts for , , and the arboricity of the graph by extending the ideas proposed in [8]. Our lower bound almost matches our proposed upper bound stated in Theorem 22. We first state the problem Popcount Thresholding Problem (referred to as PTP) in the query framework:
Definition 23 ().
Given a string , the problem is to distinguish whether is generated by i.i.d. samples from or defined as follows:
-
: For all , is set to with probability , and set to , otherwise.
-
: For all , is set to with probability , and set to , otherwise.
The problem is to decide if is generated from or by querying at any of its bits.
We state the following lemma [8] quantifying the query complexity of .
Lemma 24 (PTP Query Lower Bound [8]).
For any , , and integers , , where is the randomized query complexity to decide problem with probability at least .
We also state the following lemma, establishing bounds on the -norm of , which was partially proved in [8].
Lemma 25.
In , for any , , and integers , , let denote the number of ’s in the string , then:
-
(i)
;
-
(ii)
;
-
(iii)
;
In [8], (i) and (ii) have been shown using Chernoff bound. (iii) can also be shown by using Chernoff bound. We combine two results to obtain the result. First we state the lemma due to [8]:
Lemma 26 ([8]).
In , for any , , and integers , ,
-
(i)
;
-
(ii)
where denotes the number of ’s in the string .
We introduce another lemma to lower bound the norm of for .
Lemma 27.
In , for any , , and integers , ,
Proof.
By definition of and linearity of expectations, we have:
Now, given the independence of each , we can use Chernoff bound (Lemma 7) to obtain:
| (by Chernoff bound) | |||||
The following theorem formalizes the Theorem 3 of Section 1.1.
Theorem 28 (Lower bound - Formal).
Any algorithm that solves triangle estimation problem with using Degree, Neighbour, Pair and RandomEdge for any graph with edges, triangles, and arboricity such that requires queries.
Proof.
We want to show that given a graph , it takes queries to obtain an estimate such that with probability at least . For a contradiction, let us assume that there exists an algorithm that, for some arboricity , computes an estimate such that with probability at least using queries.
To show the contradiction, we design an algorithm that solves in less than queries using . Given an instance of generated from , we consider a graph defined as:
The vertex set .
The vertex set consists of sets of disjoint and independent set of vertices , and , with , and . Vertices of , , and will be named as , , and , respectively.
The edge set .
There exists an edge between every vertex in to every vertex in . Observe that this makes sure that the arboricity of is at least the average degree of the subgraph induced by , i.e., . If a bit of is (resp. ), there will be an edge from a vertex in (resp. ) to a vertex in (resp. ), and an edge from a vertex in (resp. ) to a vertex in (resp. ).
We index the problem instance of length as , denoting as , where and . We add an edge , and an edge if . We add an edge , and an edge if . All additions here are modulo .
Consider the orientation of edges such that all edges from is oriented outwards, and other edges are oriented arbitrarily. This gives a DAG with the out-degree of each edge being bounded by . As a DAG with out-degree at most ensures that the arboricity of the graph is at most [28, 47, 21], the graph has arboricity at most . Hence, the arboricity of is , as we have already shown it to be .
From the construction, observe that the number of edges between and is . Moreover, each edge between and adds triangles. Hence, the number of triangles in is exactly . Also note that we have added edges between and , and further edges (in the subgraph induced by ) according to the entries of , 2 for each bit . Hence, we have , and we fix .
We now describe an algorithm that uses to solve using less than queries. Given a string , we generate and estimate the number of triangles by calling using queries. If , it outputs ; otherwise, it outputs . Also, observe that by Lemma 25, we have with probability at least , where the last inequality follows from the fact that . Lemma 25 is applicable due to the fact that . Hence, we have . Thus, is allowed to make queries under the given query bound.
By Lemma 25, to distinguish between whether is generated from or with probability at least , it suffices to show that we can use to distinguish between the instance where and the instance where instance with probability at least . We now show that outputs with probability at least given , and outputs with probability at least given . We consider the two cases separately:
Case I: .
Our construction ensures that the number of triangles in is . Additionally, by our assumption on , it outputs an estimate with probability . Thus, we have with probability at least .
Case II: .
Our construction ensures that the number of triangles in is . Additionally, by our assumption on , it outputs an estimate with probability . Thus, we have with probability at least .
Now we state how to simulate the required queries used by the algorithm:
-
: For a vertex , return , and for a vertex , return . Hence, for Degree queries, no queries are made to the string.
-
: For a vertex , w.l.o.g assume to be . Return if , and otherwise. For a vertex , if , return , else return . Hence, for Neighbour queries, a single query is made to the string.
-
Pair: Given a vertex pair , there can be 3 cases: (a) If the vertex , w.l.o.g assume to be , if , return , else if and , return , else if and , return , else return . (b) If a vertex , w.l.o.g assume the to be , if , return if , else if , return if , else return . If , return if , else return . (c) If a vertex , return if , return otherwise. Hence, for Pair queries, a single query is made to the string.
-
RandomEdge: Sample a vertex with probability . Choose uniformly at random, query and return . Hence, for RandomEdge queries, a single query is made to the string for the Neighbour query.
The following corollary is a direct implication from Theorem 28 due to the fact that we consider a weaker model (without access to RandomEdge queries) compared to Theorem 28.
Corollary 29 (Lower Bound for Local Queries).
Any algorithm that solves triangle estimation problem with using Degree, Neighbour, and Pair requires queries.
6 Conclusion
In this paper, we present an almost optimal algorithm for triangle counting in graphs of bounded arboricity, assuming access to both local queries and RandomEdge queries. In particular, the query complexity of our algorithm is .333In this section, we suppress the dependence on polylogarithmic factors, for simplicity of presentation. Extending our result to clique counting remains an interesting open question. Eden et al. [28] showed that the number of -cliques can be estimated using local queries, where denotes the number of -cliques in the graph. When RandomEdge queries are also available, Assadi et al. [7] established a bound of . For graphs with arboricity bounded by , Eden et al. [28] showed that local queries suffice. We believe that, when RandomEdge queries are available in addition to local queries, the bound can be improved to . However, establishing the complexity of clique counting (when RandomEdge is available along with local queries) remains an open question. A similar open question was posed in the streaming model by Bera and Seshadri [13].
References
- [1] Charu Aggarwal and Karthik Subbian. Evolutionary network analysis: A survey. ACM Comput. Surv., 47(1), May 2014. doi:10.1145/2601412.
- [2] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’12, pages 5–14, New York, NY, USA, 2012. Association for Computing Machinery. doi:10.1145/2213556.2213560.
- [3] Mohammad Al Hasan and Vachik S. Dave. Triangle counting in large networks: a review. WIREs Data Mining and Knowledge Discovery, 8(2):e1226, 2018. doi:10.1002/widm.1226.
- [4] N. Alon. Testing Subgraphs in Large Graphs. In IEEE 54th Annual Symposium on Foundations of Computer Science, page 434, Los Alamitos, CA, USA, October 2013. IEEE Computer Society. doi:10.1109/SFCS.2001.959918.
- [5] Noga Alon, Tali Kaufman, Michael Krivelevich, and Dana Ron. Testing triangle-freeness in general graphs. SIAM J. Discret. Math., 22(2):786–819, 2008. doi:10.1137/07067917X.
- [6] Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209–223, 1997. doi:10.1007/BF02523189.
- [7] Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:20, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2019.6.
- [8] Sepehr Assadi and Hoai-An Nguyen. Asymptotically optimal bounds for estimating h-index in sublinear time with applications to subgraph counting. In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference), volume 245 of LIPIcs, pages 48:1–48:20, Illinois, Urbana-Champaign, USA (Virtual Conference), 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.48.
- [9] Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. SIAM Journal on Computing, 42(4):1737–1767, 2013. doi:10.1137/110859440.
- [10] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’02, pages 623–632, USA, 2002. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=545381.545464.
- [11] Suman K. Bera and Amit Chakrabarti. Towards tighter space bounds for counting triangles and other substructures in graph streams. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 11:1–11:14, Hannover, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2017.11.
- [12] Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:21, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2020.11.
- [13] Suman K. Bera and C. Seshadhri. How the degeneracy helps for triangle counting in graph streams. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS’20, pages 457–467, New York, NY, USA, 2020. Association for Computing Machinery. doi:10.1145/3375395.3387665.
- [14] Lorenzo Beretta and Jakub Tětek. Better sum estimation via weighted sampling. ACM Trans. Algorithms, 20(3), June 2024. doi:10.1145/3650030.
- [15] Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. computational complexity, 21(2):311–358, May 2012. doi:10.1007/s00037-012-0040-x.
- [16] Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. How hard is counting triangles in the streaming model? In 40th International Colloquium on Automata, Languages, and Programming (ICALP 2013), ICALP’13, pages 244–254, Berlin, Heidelberg, 2013. Springer-Verlag. doi:10.1007/978-3-642-39206-1_21.
- [17] Laurent Bulteau, Vincent Froese, Konstantin Kutzkov, and Rasmus Pagh. Triangle counting in dynamic graph streams. Algorithmica, 76(1):259–278, September 2016. doi:10.1007/s00453-015-0036-4.
- [18] Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’06, pages 253–262, New York, NY, USA, 2006. Association for Computing Machinery. doi:10.1145/1142351.1142388.
- [19] Amit Chakrabarti. Data stream algorithms. Computer Science, 49:149, 2015.
- [20] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1):210–223, 1985. doi:10.1137/0214017.
- [21] Marek Chrobak and David Eppstein. Planar orientations with low out-degree and compaction of adjacency matrices. Theoretical Computer Science, 86(2):243–266, 1991. doi:10.1016/0304-3975(91)90020-3.
- [22] Graham Cormode and Hossein Jowhari. A second look at counting triangles in graph streams (corrected). Theoretical Computer Science, 683:22–30, 2017. doi:10.1016/j.tcs.2016.06.020.
- [23] Maximilien Danisch, Oana Balalau, and Mauro Sozio. Listing k-cliques in sparse real-world graphs*. In Proceedings of the 2018 World Wide Web Conference, WWW ’18, pages 589–598, Republic and Canton of Geneva, CHE, 2018. International World Wide Web Conferences Steering Committee. doi:10.1145/3178876.3186125.
- [24] Michal Dory, Mohsen Ghaffari, and Saeed Ilchi. Near-optimal distributed dominating set in bounded arboricity graphs. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, pages 292–300, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519270.3538437.
- [25] Jean-Pierre Eckmann and Elisha Moses. Curvature of co-links uncovers hidden thematic layers in the world wide web. Proceedings of the National Academy of Sciences of the United States of America, 99:5825–5829, 2001. URL: https://api.semanticscholar.org/CorpusID:2618949.
- [26] Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. Approximately counting triangles in sublinear time. SIAM Journal on Computing, 46(5):1603–1646, 2017. doi:10.1137/15M1054389.
- [27] Talya Eden, Dana Ron, and C. Seshadhri. On approximating the number of k-cliques in sublinear time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 722–734, New York, NY, USA, 2018. Association for Computing Machinery. doi:10.1145/3188745.3188810.
- [28] Talya Eden, Dana Ron, and C. Seshadhri. Faster sublinear approximation of the number of k-cliques in low-arboricity graphs. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, pages 1467–1478, USA, 2020. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611975994.89.
- [29] Talya Eden and Will Rosenbaum. Lower Bounds for Approximating Graph Parameters via Communication Complexity. In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), volume 116 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:18, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.11.
- [30] Irene Finocchi, Marco Finocchi, and Emanuele G. Fusco. Clique counting in mapreduce: Algorithms and experiments. ACM J. Exp. Algorithmics, 20, October 2015. doi:10.1145/2794080.
- [31] Gaurav Goel and Jens Gustedt. Bounded arboricity to determine the local structure of sparse graphs. In Proceedings of the 32nd International Conference on Graph-Theoretic Concepts in Computer Science, WG’06, pages 159–167, Berlin, Heidelberg, 2006. Springer-Verlag. doi:10.1007/11917496_15.
- [32] Oded Goldreich. On the communication complexity methodology for proving lower bounds on the query complexity of property testing, pages 87–118. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag, Germany, April 2020. doi:10.1007/978-3-030-43662-9_7.
- [33] Mira Gonen, Dana Ron, and Yuval Shavitt. Counting stars and other small subgraphs in sublinear-time. SIAM Journal on Discrete Mathematics, 25(3):1365–1411, 2011. doi:10.1137/100783066.
- [34] Shweta Jain and C. Seshadhri. A fast and provable method for estimating clique counts using turán’s theorem. In Proceedings of the 26th International Conference on World Wide Web, WWW ’17, pages 441–449, Republic and Canton of Geneva, CHE, 2017. International World Wide Web Conferences Steering Committee. doi:10.1145/3038912.3052636.
- [35] Rajesh Jayaram and John Kallaugher. An Optimal Algorithm for Triangle Counting in the Stream. In APPROX/RANDOM 2021, volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:11, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.11.
- [36] Madhav Jha, C. Seshadhri, and Ali Pinar. A space-efficient streaming algorithm for estimating transitivity and triangle counts using the birthday paradox. ACM Trans. Knowl. Discov. Data, 9(3), February 2015. doi:10.1145/2700395.
- [37] John Kallaugher, Michael Kapralov, and Eric Price. The sketching complexity of graph and hypergraph counting. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 556–567. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00059.
- [38] John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova. The complexity of counting cycles in the adjacency list streaming model. In Dan Suciu, Sebastian Skritek, and Christoph Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 119–133. ACM, 2019. doi:10.1145/3294052.3319706.
- [39] John Kallaugher and Eric Price. A hybrid sampling scheme for triangle counting. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pages 1778–1797, USA, 2017. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611974782.116.
- [40] John Kallaugher and Eric Price. Separations and equivalences between turnstile streaming and linear sketching. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1223–1236. ACM, 2020. doi:10.1145/3357713.3384278.
- [41] Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting arbitrary subgraphs in data streams. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part II, ICALP’12, pages 598–609, Berlin, Heidelberg, 2012. Springer-Verlag. doi:10.1007/978-3-642-31585-5_53.
- [42] Christian Konrad, Andrew McGregor, Rik Sengupta, and Cuong Than. Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model. In Siddharth Barman and Sławomir Lasota, editors, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024), volume 323 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:15, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.FSTTCS.2024.29.
- [43] Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’16, pages 1272–1287, USA, 2016. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611974331.CH89.
- [44] Jure Leskovec, Lars Backstrom, Ravi Kumar, and Andrew Tomkins. Microscopic evolution of social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08, pages 462–470, New York, NY, USA, 2008. Association for Computing Machinery. doi:10.1145/1401890.1401948.
- [45] Quanquan C. Liu and C. Seshadhri. Brief announcement: Improved massively parallel triangle counting in o(1) rounds. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC ’24, pages 519–522, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3662158.3662819.
- [46] Duncan Luce and Albert D. Perry. A method of matrix analysis of group structure. Psychometrika, 14:95–116, 1949. URL: https://api.semanticscholar.org/CorpusID:16186758.
- [47] David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM, 30(3):417–427, July 1983. doi:10.1145/2402.322385.
- [48] Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. Better algorithms for counting triangles in data streams. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’16, pages 401–411, New York, NY, USA, 2016. Association for Computing Machinery. doi:10.1145/2902251.2902283.
- [49] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge, 2005. doi:10.1017/CBO9780511813603.
- [50] Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully dynamic mis in uniformly sparse graphs. ACM Trans. Algorithms, 16(2), March 2020. doi:10.1145/3378025.
- [51] Rasmus Pagh and Charalampos E. Tsourakakis. Colorful triangle counting and a mapreduce implementation. Inf. Process. Lett., 112(7):277–281, 2012. doi:10.1016/J.IPL.2011.12.007.
- [52] A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Counting and sampling triangles from a graph stream. Proc. VLDB Endow., 6(14):1870–1881, 2013. doi:10.14778/2556549.2556569.
- [53] Thomas Schank and Dorothea Wagner. Finding, counting and listing all triangles in large graphs, an experimental study. In Sotiris E. Nikoletseas, editor, Experimental and Efficient Algorithms, pages 606–609, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007/11427186_54.
- [54] Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos. Patterns and anomalies in k-cores of real-world graphs with applications. Knowl. Inf. Syst., 54(3):677–710, March 2018. doi:10.1007/s10115-017-1077-6.
- [55] Kijung Shin, Sejoon Oh, Jisu Kim, Bryan Hooi, and Christos Faloutsos. Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Trans. Knowl. Discov. Data, 14(2), February 2020. doi:10.1145/3375392.
- [56] Siddharth Suri and Sergei Vassilvitskii. Counting triangles and the curse of the last reducer. In Proceedings of the 20th International Conference on World Wide Web, WWW ’11, pages 607–614, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/1963405.1963491.
- [57] Charalampos Tsourakakis, Mihail Kolountzakis, and Gary Miller. Triangle sparsifiers. Journal of Graph Algorithms and Applications, 15(6):703–726, October 2011. doi:10.7155/jgaa.00245.
- [58] Jakub Tětek. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 107:1–107:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2022.107.
- [59] Virginia Vassilevska Williams and Yinzhan Xu. Monochromatic triangles, triangle listing and APSP. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 786–797, Durham,NC,USA, 2020. IEEE. doi:10.1109/FOCS46700.2020.00078.
- [60] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442, 1998. doi:10.1038/30918.
