# network science

Published articles for network science.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Zero-One Laws for Random Graphs

DevFeed: [Zero-One Laws for Random Graphs](<https://devfeed.tech/articles/zero-one-laws-for-random-graphs-40376.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/02/09/zero-one-laws-for-random-graphs/>)

Published: 2015-02-09T09:00:00Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [big-o-notation](<https://devfeed.tech/tags/big-o-notation.md>), [connectivity](<https://devfeed.tech/tags/connectivity.md>), [countability](<https://devfeed.tech/tags/countability.md>), [distribution](<https://devfeed.tech/tags/distribution.md>), [erdos-renyi](<https://devfeed.tech/tags/erdos-renyi.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [logic](<https://devfeed.tech/tags/logic.md>), [logical](<https://devfeed.tech/tags/logical.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [model-theory](<https://devfeed.tech/tags/model-theory.md>), [network-science](<https://devfeed.tech/tags/network-science.md>), [parameter](<https://devfeed.tech/tags/parameter.md>), [random-graph](<https://devfeed.tech/tags/random-graph.md>), [random-graphs](<https://devfeed.tech/tags/random-graphs.md>), [statement](<https://devfeed.tech/tags/statement.md>), [vertex](<https://devfeed.tech/tags/vertex.md>)

### AI overview

This article introduces zero-one laws for Erdős-Rényi random graphs. It explains that many graph properties, including properties expressible in first-order logic, have probabilities that tend toward zero or one as the graph grows, with behavior determined by relevant thresholds or constant edge probabilities.

### Source excerpt

Last time we saw a number of properties of graphs, such as connectivity, where the probability that an Erdős-Rényi random graph $ G(n,p)$ satisfies the property is asymptotically either zero or one. And this zero or one depends on whether the parameter $ p$ is above or below a universal threshold (that depends only on $ n$ and the property in question). To remind the reader, the Erdős-Rényi random "graph" $ G(n,p)$ is a distribution over graphs that you draw from by including each edge independently with probability $ p$.

## The Giant Component and Explosive Percolation

DevFeed: [The Giant Component and Explosive Percolation](<https://devfeed.tech/articles/the-giant-component-and-explosive-percolation-40375.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/02/02/the-giant-component-and-explosive-percolation/>)

Published: 2015-02-02T09:00:00Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [Data analysis](<https://devfeed.tech/topics/data-analysis.md>)

Tags: [big-o-notation](<https://devfeed.tech/tags/big-o-notation.md>), [erdos-renyi](<https://devfeed.tech/tags/erdos-renyi.md>), [first-moment-method](<https://devfeed.tech/tags/first-moment-method.md>), [giant-component](<https://devfeed.tech/tags/giant-component.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [inequality](<https://devfeed.tech/tags/inequality.md>), [markov](<https://devfeed.tech/tags/markov.md>), [method-of-moments](<https://devfeed.tech/tags/method-of-moments.md>), [network-science](<https://devfeed.tech/tags/network-science.md>), [percolation](<https://devfeed.tech/tags/percolation.md>), [probability-theory](<https://devfeed.tech/tags/probability-theory.md>), [random-graph](<https://devfeed.tech/tags/random-graph.md>), [random-graphs](<https://devfeed.tech/tags/random-graphs.md>), [random-variables](<https://devfeed.tech/tags/random-variables.md>)

### AI overview

This article develops rigorous results about Erdős-Rényi random graphs, following a conjecture about connectivity at edge probability p = 5/n. It introduces threshold theorems and begins explaining the first moment method, Markov's inequality, and isolated vertices.

### Source excerpt

Last time we left off with a tantalizing conjecture: a random graph with edge probability $ p = 5/n$ is almost surely a connected graph. We arrived at that conjecture from some ad-hoc data analysis, so let's go back and treat it with some more rigorous mathematical techniques. As we do, we'll discover some very interesting "threshold theorems" that essentially say a random graph will either certainly have a property, or it will certainly not have it.

## Stable Marriages and Designing Markets

DevFeed: [Stable Marriages and Designing Markets](<https://devfeed.tech/articles/stable-marriages-and-designing-markets-40354.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/04/02/stable-marriages-and-designing-markets/>)

Published: 2014-04-02T18:21:55Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Computing](<https://devfeed.tech/topics/computing.md>), [GitHub](<https://devfeed.tech/topics/github.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [bipartite-graphs](<https://devfeed.tech/tags/bipartite-graphs.md>), [code](<https://devfeed.tech/tags/code.md>), [computing](<https://devfeed.tech/tags/computing.md>), [course](<https://devfeed.tech/tags/course.md>), [download](<https://devfeed.tech/tags/download.md>), [economics](<https://devfeed.tech/tags/economics.md>), [github](<https://devfeed.tech/tags/github.md>), [internships](<https://devfeed.tech/tags/internships.md>), [matchings](<https://devfeed.tech/tags/matchings.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [network-science](<https://devfeed.tech/tags/network-science.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [stable-marriage](<https://devfeed.tech/tags/stable-marriage.md>)

### AI overview

This tutorial explains the stable marriage problem, presents the classical algorithm for constructing stable marriages, and proves its correctness. It also discusses a polygamous generalization and applies it to assigning students to internships.

### Source excerpt

Here is a fun puzzle. Suppose we have a group of 10 men and 10 women, and each of the men has sorted the women in order of their preference for marriage (that is, a man prefers to marry a woman earlier in his list over a woman later in the list). Likewise, each of the women has sorted the men in order of marriageability. We might ask if there is any way that we, the omniscient cupids of love, can decide who should marry to make everyone happy.