# Tag Info

8

It is very easy to say something about the expected length before you get stuck in a loop: if there are $n$ videos, it will (starting from a random video) take in expectation $\Theta(\sqrt{n})$ videos before you loop around (the actual value is around $1.25\sqrt{n}$). This is effectively the birthday problem, since each time you draw a video at random. ...

5

You're (basically) computing the square of the graph, in which two vertices are adjacent if there is a path of length 2 (or at most 2, depending on the definition) connecting them. The square will contain at least two connected components, corresponding to the two bipartitions.

4

This is NP-hard by reduction from Set Cover. The problem remains NP-hard even if edge weights are restricted to $\{1, 3\}$. In the Set Cover problem, we are given a ground set $U$ containing $m$ elements $x_1, \dots, x_m$, a collection $\mathbf S$ of $n$ subsets $S_1, \dots, S_n$ of $U$, and an integer $k$, and our task is to determine whether there exists ...

4

I never heard of any algorithm with the constraint of having an overlap between communities larger than a given threshold (4 here). But I suggest the following: turn your graph into its line graph, use a classical node partitioning method that gives a hierarchy of communities, and then choose a partition that fits your requirements. More details: the line ...

4

this may be a bit unexpected but yes, this has been studied in at least one particular context: PRNGs. a PRNG can be visualized as a directed graph, specifically a functional graph (all vertices, single outdegree) of "current value, next value". however most PRNGs are designed to have a single very long cycle. there is some analysis of PRNGs with multiple ...

3

Suppose we want to quantify the extent to which $v$ is between $s$ and $t$. There could be a few ways. One way to describe that extent is the probability of passing through $v$ if we want to reach from $s$ to $t$ by a randomly-selected shortest path. Assuming each shortest path is selected with equal probability, we will get $\frac{\sigma_{st}(v)}{\sigma_{... 3 However it doesn't seem to me that the formula calculates what is defined. The formula is right. The betweenness centrality is a value in an interval$[0, \ldots, 1]$. Thus, if the betweenness centrality of node$v$is equal to$1$, then all shortest paths between two nodes of this graph pass through$v$. I will explain the correctness of this summation ... 2 Your analysis so far is correct. Let's consider the probability that it will take$k$attempts to transmit a package. This means that there must be$k-1$failures followed by a final success. There are two ways a transmission can fail: Transmit succeeds, ACK fails. Call this a type-1 failure. Its probability will be$(1-p)q$. Transmission fails (so ACK is ... 2 There's an efficient streaming algorithm for computing the average degree. Note that if you have the sum of the degrees and the number of vertices, you can compute the average -- so we'll try to keep track of those two values. Also note that if you delete or insert an edge, it is easy to update the sum of the degrees. If you delete or insert a vertex, it ... 2 Sure, of course. You can define a matrix to contain whatever numbers you want it to contain. There's nothing that prevents you. The real question is whether the result has the properties you want it to have, but since you haven't listed any properties, there's nothing to answer here. 2 There are many papers dealing with the algorithmic aspects of these measures, with formal proofs, complexity analysis, and so on. However, I understand that this is not really what you are looking for. There are only few formal works on their actual relevance for describing features of interest in practice. Pagerank is a notable exception, though. Its ... 2 Another heuristic idea: Find a long shortest path, and pick the vertex halfway along it. Pick a vertex and run BFS from it. For some small$k$, take the$k$furthest vertices from the original vertex that the BFS determines, and repeat the process on each of them, keeping the$k$overall furthest vertices each time. Repeat a few times. If the graph is a ... 2 Depends what you want to do with the "partition with overlapping nodes". There is this survey about overlapping community detection: https://dl.acm.org/doi/10.1145/2501654.2501657 The Clique_percolation_method is one such method. 1 If you consider the format of the TCP-IP datagram. Source Address: The 32-bit IP address of the originator of the datagram. Note that even though intermediate devices such as routers may handle the datagram, they do not normally put their address into this field—it is always the device that originally sent the datagram. Destination Address: The 32-bit IP ... 1 After a bit of reading through literature I've come upon "closeness centrality" which is the reciprocal of what I'm calculating (mean distance, which they call "farness" in the article). But I still haven't found any algorithms for finding the "closeness center" (node with maximum closeness centrality) that is faster than$O(N^2)\$. As a heuristic, I have ...

1

You're asking how to compute the shortest path between two vertices in a graph. Solution: use an algorithm for computing shortest paths. In your case, BFS would be a good choice. There's no need for A*.

1

I don't know if there is a standard method to identify which activity matches which arrow, but I was able to complete your PERT chart by examining a few possible cases, while filling the chart from left to right. Each case was accepted or rejected after a while. I found that the higher arrow matches B and the lower C. Note that if you try to match C with the ...

1

Certainly it is possible. For example, in the following study the Indian railway network was analyzed. Small-world properties of the Indian railway network. Parongama Sen, Subinay Dasgupta, Arnab Chatterjee, P. A. Sreeram, G. Mukherjee, and S. S. Manna. Phys. Rev. E 67, 036106 – 2003 In another study, the Chinese railway network was considered. W. Li, ...

1

Assuming for the moment that the two types of person are distinct, your graph is (directed) bipartite, so it makes more sense to store it as a matrix whose rows correspond to people with fishing rights, and whose columns correspond to fishermen. If a person can function in both roles, you can think of their two personas as distinct, i.e., have a row and a ...

1

In order to do this, you need high degree nodes in your initial network: since you do not add anything, degree may only decrease, and you want high degree nodes in the end. Now, assume your initial random network indeed has high degree nodes. Since it is random, choosing random links in it will often lead to high-degree extremities. Indeed, the probability ...

1

Sure. Yes, you can capture the packets and view them. That'll work. It's a useful, informative exercise. You can use Wireshark (or some other packet capture tool) to capture the packets involved in the TLS handshake and view the captured packets. It'll show you the raw bytes, and also decode the handshake messages for you. Wireshark has a nice GUI ...

Only top voted, non community-wiki answers of a minimum length are eligible