“Two-scale” network?
$begingroup$
I've read that networks can be:
random (Erdős–Rényi model),
scale-free (Albert–Barabási model),
small-world (Watts–Strogatz model).
But can a real world network be “two-scale”, in the sense that its degree distribution only consists of two different degrees, for example $(5,5,5,5,4,4,4,...)$ where the number nodes of degree $4$ is equal to $9$?
soft-question network
edited Jan 14 at 18:20
Wrzlprmft
3,17111335
asked Aug 28 '18 at 2:54
UltradarkUltradark
3631518
$endgroup$
add a comment |
$begingroup$
I've read that networks can be:
random (Erdős–Rényi model),
scale-free (Albert–Barabási model),
small-world (Watts–Strogatz model).
But can a real world network be “two-scale”, in the sense that its degree distribution only consists of two different degrees, for example $(5,5,5,5,4,4,4,...)$ where the number nodes of degree $4$ is equal to $9$?
soft-question network
edited Jan 14 at 18:20
Wrzlprmft
3,17111335
asked Aug 28 '18 at 2:54
UltradarkUltradark
3631518
$endgroup$
$begingroup$
Real world, no. But for a random network as you wish, yes, simply adapt the usual construction starting with half-edges attached to each vertex.
$endgroup$
– Did
Aug 28 '18 at 5:57
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? Would the degree distribution for a "two scale" network just be a line segment with negative slope?
$endgroup$
– Ultradark
Aug 28 '18 at 13:17
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? – Many real networks do not have such a distribution and it is still up to debate to what extents observations of such distributions in real networks are a measurement artefact. The models you list are just that: models. Any given real network will substantially differ from the typical output of these models. (And note that I use typical here only because all of the models involve randomness and therefore can produce all sorts of things with a very low probability.)
$endgroup$
– Wrzlprmft
Jan 14 at 18:25
add a comment |
$begingroup$
I've read that networks can be:
random (Erdős–Rényi model),
scale-free (Albert–Barabási model),
small-world (Watts–Strogatz model).
But can a real world network be “two-scale”, in the sense that its degree distribution only consists of two different degrees, for example $(5,5,5,5,4,4,4,...)$ where the number nodes of degree $4$ is equal to $9$?
soft-question network
edited Jan 14 at 18:20
Wrzlprmft
3,17111335
asked Aug 28 '18 at 2:54
UltradarkUltradark
3631518
$endgroup$
I've read that networks can be:
random (Erdős–Rényi model),
scale-free (Albert–Barabási model),
small-world (Watts–Strogatz model).
But can a real world network be “two-scale”, in the sense that its degree distribution only consists of two different degrees, for example $(5,5,5,5,4,4,4,...)$ where the number nodes of degree $4$ is equal to $9$?
soft-question network
soft-question network
edited Jan 14 at 18:20
Wrzlprmft
3,17111335
asked Aug 28 '18 at 2:54
UltradarkUltradark
3631518
edited Jan 14 at 18:20
Wrzlprmft
3,17111335
asked Aug 28 '18 at 2:54
UltradarkUltradark
3631518
edited Jan 14 at 18:20
Wrzlprmft
3,17111335
edited Jan 14 at 18:20
Wrzlprmft
3,17111335
edited Jan 14 at 18:20
Wrzlprmft
3,17111335
3,17111335
asked Aug 28 '18 at 2:54
UltradarkUltradark
3631518
asked Aug 28 '18 at 2:54
UltradarkUltradark
3631518
asked Aug 28 '18 at 2:54
UltradarkUltradark
3631518
3631518
$begingroup$
Real world, no. But for a random network as you wish, yes, simply adapt the usual construction starting with half-edges attached to each vertex.
$endgroup$
– Did
Aug 28 '18 at 5:57
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? Would the degree distribution for a "two scale" network just be a line segment with negative slope?
$endgroup$
– Ultradark
Aug 28 '18 at 13:17
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? – Many real networks do not have such a distribution and it is still up to debate to what extents observations of such distributions in real networks are a measurement artefact. The models you list are just that: models. Any given real network will substantially differ from the typical output of these models. (And note that I use typical here only because all of the models involve randomness and therefore can produce all sorts of things with a very low probability.)
$endgroup$
– Wrzlprmft
Jan 14 at 18:25
add a comment |
$begingroup$
Real world, no. But for a random network as you wish, yes, simply adapt the usual construction starting with half-edges attached to each vertex.
$endgroup$
– Did
Aug 28 '18 at 5:57
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? Would the degree distribution for a "two scale" network just be a line segment with negative slope?
$endgroup$
– Ultradark
Aug 28 '18 at 13:17
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? – Many real networks do not have such a distribution and it is still up to debate to what extents observations of such distributions in real networks are a measurement artefact. The models you list are just that: models. Any given real network will substantially differ from the typical output of these models. (And note that I use typical here only because all of the models involve randomness and therefore can produce all sorts of things with a very low probability.)
$endgroup$
– Wrzlprmft
Jan 14 at 18:25
$begingroup$
Real world, no. But for a random network as you wish, yes, simply adapt the usual construction starting with half-edges attached to each vertex.
$endgroup$
– Did
Aug 28 '18 at 5:57
$begingroup$
Real world, no. But for a random network as you wish, yes, simply adapt the usual construction starting with half-edges attached to each vertex.
$endgroup$
– Did
Aug 28 '18 at 5:57
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? Would the degree distribution for a "two scale" network just be a line segment with negative slope?
$endgroup$
– Ultradark
Aug 28 '18 at 13:17
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? Would the degree distribution for a "two scale" network just be a line segment with negative slope?
$endgroup$
– Ultradark
Aug 28 '18 at 13:17
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? – Many real networks do not have such a distribution and it is still up to debate to what extents observations of such distributions in real networks are a measurement artefact. The models you list are just that: models. Any given real network will substantially differ from the typical output of these models. (And note that I use typical here only because all of the models involve randomness and therefore can produce all sorts of things with a very low probability.)
$endgroup$
– Wrzlprmft
Jan 14 at 18:25
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? – Many real networks do not have such a distribution and it is still up to debate to what extents observations of such distributions in real networks are a measurement artefact. The models you list are just that: models. Any given real network will substantially differ from the typical output of these models. (And note that I use typical here only because all of the models involve randomness and therefore can produce all sorts of things with a very low probability.)
$endgroup$
– Wrzlprmft
Jan 14 at 18:25
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The concept of “real-world networks” is not well defined. Usually, as soon as you find some kind of natural data, from which your network emerges it can be considered a real-world network. Most real-world data has certain properties that are significantly different from random networks (i.e., the Erdős–Rényi model), e.g., its degree distribution or the small-world property.
If you are asking whether there exists a graph that has that particular degree sequence, then the answer is yes, and here is an example given by its edge list:
$
[(0, 11), ;
(0, 3), ;
(0, 3), ;
(0, 10), ;
(0, 6), ;
(1, 4), ;
(1, 3), ;
(1, 11), ;
(1, 10), ;
(1, 5), ;
(2, 5), ;
(2, 7), ;
(2, 7), ;
(2, 4), ;
(2, 3), ;
(3, 5), ;
(4, 8), ;
(4, 8), ;
(5, 6), ;
(6, 9), ;
(6, 11), ;
(7, 7), ;
(8, 12), ;
(8, 10), ;
(9, 10), ;
(9, 12), ;
(9, 11), ;
(12, 12)]$
In general, this is known as the graph-realization problem and there are efficient (i.e. in polynomial time) algorithms that, given a degree sequence, can decide whether this sequence can be realized as a degree sequence of a graph or not.
Also note that networks can fall in much more than just these three categories, and the Watts–Strogatz model with $0$ randomness actually does not exhibit the small-world property.
edited Jan 14 at 18:18
Wrzlprmft
3,17111335
answered Jan 14 at 17:52
chickenNinja123chickenNinja123
14313
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2896814%2ftwo-scale-network%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The concept of “real-world networks” is not well defined. Usually, as soon as you find some kind of natural data, from which your network emerges it can be considered a real-world network. Most real-world data has certain properties that are significantly different from random networks (i.e., the Erdős–Rényi model), e.g., its degree distribution or the small-world property.
If you are asking whether there exists a graph that has that particular degree sequence, then the answer is yes, and here is an example given by its edge list:
$
[(0, 11), ;
(0, 3), ;
(0, 3), ;
(0, 10), ;
(0, 6), ;
(1, 4), ;
(1, 3), ;
(1, 11), ;
(1, 10), ;
(1, 5), ;
(2, 5), ;
(2, 7), ;
(2, 7), ;
(2, 4), ;
(2, 3), ;
(3, 5), ;
(4, 8), ;
(4, 8), ;
(5, 6), ;
(6, 9), ;
(6, 11), ;
(7, 7), ;
(8, 12), ;
(8, 10), ;
(9, 10), ;
(9, 12), ;
(9, 11), ;
(12, 12)]$
In general, this is known as the graph-realization problem and there are efficient (i.e. in polynomial time) algorithms that, given a degree sequence, can decide whether this sequence can be realized as a degree sequence of a graph or not.
Also note that networks can fall in much more than just these three categories, and the Watts–Strogatz model with $0$ randomness actually does not exhibit the small-world property.
edited Jan 14 at 18:18
Wrzlprmft
3,17111335
answered Jan 14 at 17:52
chickenNinja123chickenNinja123
14313
$endgroup$
add a comment |
$begingroup$
The concept of “real-world networks” is not well defined. Usually, as soon as you find some kind of natural data, from which your network emerges it can be considered a real-world network. Most real-world data has certain properties that are significantly different from random networks (i.e., the Erdős–Rényi model), e.g., its degree distribution or the small-world property.
If you are asking whether there exists a graph that has that particular degree sequence, then the answer is yes, and here is an example given by its edge list:
$
[(0, 11), ;
(0, 3), ;
(0, 3), ;
(0, 10), ;
(0, 6), ;
(1, 4), ;
(1, 3), ;
(1, 11), ;
(1, 10), ;
(1, 5), ;
(2, 5), ;
(2, 7), ;
(2, 7), ;
(2, 4), ;
(2, 3), ;
(3, 5), ;
(4, 8), ;
(4, 8), ;
(5, 6), ;
(6, 9), ;
(6, 11), ;
(7, 7), ;
(8, 12), ;
(8, 10), ;
(9, 10), ;
(9, 12), ;
(9, 11), ;
(12, 12)]$
In general, this is known as the graph-realization problem and there are efficient (i.e. in polynomial time) algorithms that, given a degree sequence, can decide whether this sequence can be realized as a degree sequence of a graph or not.
Also note that networks can fall in much more than just these three categories, and the Watts–Strogatz model with $0$ randomness actually does not exhibit the small-world property.
edited Jan 14 at 18:18
Wrzlprmft
3,17111335
answered Jan 14 at 17:52
chickenNinja123chickenNinja123
14313
$endgroup$
add a comment |
$begingroup$
The concept of “real-world networks” is not well defined. Usually, as soon as you find some kind of natural data, from which your network emerges it can be considered a real-world network. Most real-world data has certain properties that are significantly different from random networks (i.e., the Erdős–Rényi model), e.g., its degree distribution or the small-world property.
If you are asking whether there exists a graph that has that particular degree sequence, then the answer is yes, and here is an example given by its edge list:
$
[(0, 11), ;
(0, 3), ;
(0, 3), ;
(0, 10), ;
(0, 6), ;
(1, 4), ;
(1, 3), ;
(1, 11), ;
(1, 10), ;
(1, 5), ;
(2, 5), ;
(2, 7), ;
(2, 7), ;
(2, 4), ;
(2, 3), ;
(3, 5), ;
(4, 8), ;
(4, 8), ;
(5, 6), ;
(6, 9), ;
(6, 11), ;
(7, 7), ;
(8, 12), ;
(8, 10), ;
(9, 10), ;
(9, 12), ;
(9, 11), ;
(12, 12)]$
In general, this is known as the graph-realization problem and there are efficient (i.e. in polynomial time) algorithms that, given a degree sequence, can decide whether this sequence can be realized as a degree sequence of a graph or not.
Also note that networks can fall in much more than just these three categories, and the Watts–Strogatz model with $0$ randomness actually does not exhibit the small-world property.
edited Jan 14 at 18:18
Wrzlprmft
3,17111335
answered Jan 14 at 17:52
chickenNinja123chickenNinja123
14313
$endgroup$
The concept of “real-world networks” is not well defined. Usually, as soon as you find some kind of natural data, from which your network emerges it can be considered a real-world network. Most real-world data has certain properties that are significantly different from random networks (i.e., the Erdős–Rényi model), e.g., its degree distribution or the small-world property.
If you are asking whether there exists a graph that has that particular degree sequence, then the answer is yes, and here is an example given by its edge list:
$
[(0, 11), ;
(0, 3), ;
(0, 3), ;
(0, 10), ;
(0, 6), ;
(1, 4), ;
(1, 3), ;
(1, 11), ;
(1, 10), ;
(1, 5), ;
(2, 5), ;
(2, 7), ;
(2, 7), ;
(2, 4), ;
(2, 3), ;
(3, 5), ;
(4, 8), ;
(4, 8), ;
(5, 6), ;
(6, 9), ;
(6, 11), ;
(7, 7), ;
(8, 12), ;
(8, 10), ;
(9, 10), ;
(9, 12), ;
(9, 11), ;
(12, 12)]$
In general, this is known as the graph-realization problem and there are efficient (i.e. in polynomial time) algorithms that, given a degree sequence, can decide whether this sequence can be realized as a degree sequence of a graph or not.
Also note that networks can fall in much more than just these three categories, and the Watts–Strogatz model with $0$ randomness actually does not exhibit the small-world property.
edited Jan 14 at 18:18
Wrzlprmft
3,17111335
answered Jan 14 at 17:52
chickenNinja123chickenNinja123
14313
edited Jan 14 at 18:18
Wrzlprmft
3,17111335
edited Jan 14 at 18:18
Wrzlprmft
3,17111335
edited Jan 14 at 18:18
Wrzlprmft
3,17111335
3,17111335
answered Jan 14 at 17:52
chickenNinja123chickenNinja123
14313
answered Jan 14 at 17:52
chickenNinja123chickenNinja123
14313
answered Jan 14 at 17:52
chickenNinja123chickenNinja123
14313
14313
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2896814%2ftwo-scale-network%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Real world, no. But for a random network as you wish, yes, simply adapt the usual construction starting with half-edges attached to each vertex.
$endgroup$
– Did
Aug 28 '18 at 5:57
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? Would the degree distribution for a "two scale" network just be a line segment with negative slope?
$endgroup$
– Ultradark
Aug 28 '18 at 13:17
$begingroup$
It can't be real world because it doesn't have a power law degree distribution? – Many real networks do not have such a distribution and it is still up to debate to what extents observations of such distributions in real networks are a measurement artefact. The models you list are just that: models. Any given real network will substantially differ from the typical output of these models. (And note that I use typical here only because all of the models involve randomness and therefore can produce all sorts of things with a very low probability.)
$endgroup$
– Wrzlprmft
Jan 14 at 18:25