📝 Estimating the Size of a Large Network and its Communities from a Random Sample
Lin Chen, Amin Karbasi, Forrest W. Crawford
https://arxiv.org/pdf/1610.08473v1
📌 ABSTRACT:
Most real-world networks are too large to be measured or studied directly and there is substantial interest in estimating global network properties from smaller sub-samples. One of the most important global properties is the number of vertices/nodes in the network. Estimating the number of vertices in a large network is a major challenge in computer science, epidemiology, demography, and intelligence analysis. In this paper we consider a population random graph G = (V;E) from the stochastic block model (SBM) with K communities/blocks. A sample is obtained by randomly choosing a subset W and letting G(W) be the induced subgraph in G of the vertices in W. In addition to G(W), we observe the total degree of each sampled vertex and its block membership. Given this partial information, we propose an efficient PopULation Size Estimation algorithm, called PULSE, that correctly estimates the size of the whole population as well as the size of each community. To support our theoretical analysis, we perform an exhaustive set of experiments to study the effects of sample size, K, and SBM model parameters on the accuracy of the estimates. The experimental results also demonstrate that PULSE significantly outperforms a widely-used method called the network scale-up estimator in a wide variety of scenarios. We conclude with extensions and directions for future work.
Lin Chen, Amin Karbasi, Forrest W. Crawford
https://arxiv.org/pdf/1610.08473v1
📌 ABSTRACT:
Most real-world networks are too large to be measured or studied directly and there is substantial interest in estimating global network properties from smaller sub-samples. One of the most important global properties is the number of vertices/nodes in the network. Estimating the number of vertices in a large network is a major challenge in computer science, epidemiology, demography, and intelligence analysis. In this paper we consider a population random graph G = (V;E) from the stochastic block model (SBM) with K communities/blocks. A sample is obtained by randomly choosing a subset W and letting G(W) be the induced subgraph in G of the vertices in W. In addition to G(W), we observe the total degree of each sampled vertex and its block membership. Given this partial information, we propose an efficient PopULation Size Estimation algorithm, called PULSE, that correctly estimates the size of the whole population as well as the size of each community. To support our theoretical analysis, we perform an exhaustive set of experiments to study the effects of sample size, K, and SBM model parameters on the accuracy of the estimates. The experimental results also demonstrate that PULSE significantly outperforms a widely-used method called the network scale-up estimator in a wide variety of scenarios. We conclude with extensions and directions for future work.
🔴 علم بارپرستگونه:
ملاحظاتی در علم، شبهعلم و یادگیری اینکه چگونه خود را فریب ندهیم.
سخنرانی ریچارد #فاینمن به مناسبت جشن فارغالتحصیلی - #کلتک ۱۹۷۴
http://www.sitpor.org/2016/04/cargo-cult-science/
#Cargo_Cult_Science , #sitpor
ملاحظاتی در علم، شبهعلم و یادگیری اینکه چگونه خود را فریب ندهیم.
سخنرانی ریچارد #فاینمن به مناسبت جشن فارغالتحصیلی - #کلتک ۱۹۷۴
http://www.sitpor.org/2016/04/cargo-cult-science/
#Cargo_Cult_Science , #sitpor
📝 Percolation in real multiplex networks
Ginestra Bianconi, Filippo Radicchi
https://arxiv.org/pdf/1610.08708v1
(Submitted on 27 Oct 2016)
📌 ABSTRACT
We present an exact mathematical framework able to describe site-percolation transitions in real multiplex networks. Specifically, we consider the average percolation diagram valid over an infinite number of random configurations where nodes are present in the system with given probability. The approach relies on the locally treelike ansatz, so that it is expected to accurately reproduce the true percolation diagram of sparse multiplex networks with negligible number of short loops. The performance of our theory is tested in social, biological, and transportation multiplex graphs. When compared against previously introduced methods, we observe improvements in the prediction of the percolation diagrams in all networks analyzed. Results from our method confirm previous claims about the robustness of real multiplex networks, in the sense that the average connectedness of the system does not exhibit any significant abrupt change as its individual components are randomly destroyed.
Ginestra Bianconi, Filippo Radicchi
https://arxiv.org/pdf/1610.08708v1
(Submitted on 27 Oct 2016)
📌 ABSTRACT
We present an exact mathematical framework able to describe site-percolation transitions in real multiplex networks. Specifically, we consider the average percolation diagram valid over an infinite number of random configurations where nodes are present in the system with given probability. The approach relies on the locally treelike ansatz, so that it is expected to accurately reproduce the true percolation diagram of sparse multiplex networks with negligible number of short loops. The performance of our theory is tested in social, biological, and transportation multiplex graphs. When compared against previously introduced methods, we observe improvements in the prediction of the percolation diagrams in all networks analyzed. Results from our method confirm previous claims about the robustness of real multiplex networks, in the sense that the average connectedness of the system does not exhibit any significant abrupt change as its individual components are randomly destroyed.
#سلسله_سمینارهای_هفتگی گروه سیستم های پیچیده شهید بهشتی
علاقه مندان می توانند برای ارائه موضوعات خود به ادمین پیام داده یا به صورت حضوری در جلسه مطرح نمایند.
@onmjnl
علاقه مندان می توانند برای ارائه موضوعات خود به ادمین پیام داده یا به صورت حضوری در جلسه مطرح نمایند.
@onmjnl
📝 Network science on belief system dynamics under logic constraints
http://science.sciencemag.org/content/354/6310/321
📌 ABSTRACT
Breakthroughs have been made in algorithmic approaches to understanding how individuals in a group influence each other to reach a consensus. However, what happens to the group consensus if it depends on several statements, one of which is proven false? Here, we show how the existence of logical constraints on beliefs affect the collective convergence to a shared belief system and, in contrast, how an idiosyncratic set of arbitrarily linked beliefs held by a few may become held by many.
http://science.sciencemag.org/content/354/6310/321
📌 ABSTRACT
Breakthroughs have been made in algorithmic approaches to understanding how individuals in a group influence each other to reach a consensus. However, what happens to the group consensus if it depends on several statements, one of which is proven false? Here, we show how the existence of logical constraints on beliefs affect the collective convergence to a shared belief system and, in contrast, how an idiosyncratic set of arbitrarily linked beliefs held by a few may become held by many.
Science
Network science on belief system dynamics under logic constraints
An algorithmic approach shows how our belief systems change when facts and beliefs are in conflict.
🔵 Are you a student eager to work on Complex Networks and Systems? Apply to our PhD program at Indiana University!
http://cnets.indiana.edu/phd/
http://cnets.indiana.edu/phd/
Forwarded from انجمن علمی فیزیک بهشتی (SBU)
سمینار عمومی هفتگی، سه شنبه 11آبان، تالار ابن هیثم، دانشکده فیزیک، کانال انجمن علمی دانشجویی فیزیک را به دوستان خود معرفی کنید @sbu_physics
📝 Community detection in networks: A user guide
Santo FortunatoDarko
http://www.sciencedirect.com/science/article/pii/S0370157316302964
📌 Abstract
Community detection in networks is one of the most popular topics of modern network science. Communities, or clusters, are usually groups of vertices having higher probability of being connected to each other than to members of other groups, though other patterns are possible. Identifying communities is an ill-defined problem. There are no universal protocols on the fundamental ingredients, like the definition of community itself, nor on other crucial issues, like the validation of algorithms and the comparison of their performances. This has generated a number of confusions and misconceptions, which undermine the progress in the field. We offer a guided tour through the main aspects of the problem. We also point out strengths and weaknesses of popular methods, and give directions to their use.
Keywords
#Networks #Communities #Clustering
Santo FortunatoDarko
http://www.sciencedirect.com/science/article/pii/S0370157316302964
📌 Abstract
Community detection in networks is one of the most popular topics of modern network science. Communities, or clusters, are usually groups of vertices having higher probability of being connected to each other than to members of other groups, though other patterns are possible. Identifying communities is an ill-defined problem. There are no universal protocols on the fundamental ingredients, like the definition of community itself, nor on other crucial issues, like the validation of algorithms and the comparison of their performances. This has generated a number of confusions and misconceptions, which undermine the progress in the field. We offer a guided tour through the main aspects of the problem. We also point out strengths and weaknesses of popular methods, and give directions to their use.
Keywords
#Networks #Communities #Clustering
📝 Cellular Automata and Complexity: Collected Papers
https://www.complexityexplorer.org/explore/resources/461-cellular-automata-and-complexity-collected-papers
📌 Book Description:
"Are mathematical equations the best way to model nature? For many years it had been assumed that they were. But in the early 1980s, Stephen Wolfram made the radical proposal that one should instead build models that are based directly on simple computer programs. Wolfram made a detailed study of a class of such models known as cellular automata, and discovered a remarkable fact: that even when the underlying rules are very simple, the behavior they produce can be highly complex, and can mimic many features of what we see in nature. And based on this result, Wolfram began a program to develop what has become A New Kind of Science." "The results of Wolfram's work found many applications, from the so-called Wolfram Classification central to fields such as artificial life, to new ideas about cryptography and fluid dynamics. This book is a collection of Wolfram's original papers on cellular automata and complexity. Some of these papers are widely known in the scientific community; others have never been published before. Together, the papers provide a highly readable account of what has become a major new field of science, with important implications for physics, biology, economics, computer science and many other areas."
https://www.complexityexplorer.org/explore/resources/461-cellular-automata-and-complexity-collected-papers
📌 Book Description:
"Are mathematical equations the best way to model nature? For many years it had been assumed that they were. But in the early 1980s, Stephen Wolfram made the radical proposal that one should instead build models that are based directly on simple computer programs. Wolfram made a detailed study of a class of such models known as cellular automata, and discovered a remarkable fact: that even when the underlying rules are very simple, the behavior they produce can be highly complex, and can mimic many features of what we see in nature. And based on this result, Wolfram began a program to develop what has become A New Kind of Science." "The results of Wolfram's work found many applications, from the so-called Wolfram Classification central to fields such as artificial life, to new ideas about cryptography and fluid dynamics. This book is a collection of Wolfram's original papers on cellular automata and complexity. Some of these papers are widely known in the scientific community; others have never been published before. Together, the papers provide a highly readable account of what has become a major new field of science, with important implications for physics, biology, economics, computer science and many other areas."
🔵 From Navigation on the High Seas to Magnets at High Temperatures
How Conformal Maps Enter Our Lives
https://sinews.siam.org/DetailsPage/TabId/900/ArtMID/2243/ArticleID/1738/From-Navigation-on-the-High-Seas-to-Magnets-at-High-Temperatures.aspx
#CFT
How Conformal Maps Enter Our Lives
https://sinews.siam.org/DetailsPage/TabId/900/ArtMID/2243/ArticleID/1738/From-Navigation-on-the-High-Seas-to-Magnets-at-High-Temperatures.aspx
#CFT
SIAM News
From Navigation on the High Seas to Magnets at High Temperatures
Just imagine that you have attended the SIAM Conference on Industrial and Applied Geometry (GD29) in San Francisco and you are aboard a plane that is taking you back home to your research institute in Berlin. You see on the monitor in front of you that the…
📝 The physics of multilayer networks
Manlio De Domenico, Clara Granell, Mason A. Porter, Alex Arenas
https://arxiv.org/pdf/1604.02021v1
📌 ABSTRACT
The study of networks plays a crucial role in investigating the structure, dynamics, and function of a wide variety of complex systems in myriad disciplines. Despite the success of traditional network analysis, standard networks provide a limited representation of these systems, which often includes different types of relationships (i.e., "multiplexity") among their constituent components and/or multiple interacting subsystems. Such structural complexity has a significant effect on both dynamics and function. Throwing away or aggregating available structural information can generate misleading results and provide a major obstacle towards attempts to understand the system under analysis. The recent "multilayer' approach for modeling networked systems explicitly allows the incorporation of multiplexity and other features of realistic networked systems. On one hand, it allows one to couple different structural relationships by encoding them in a convenient mathematical object. On the other hand, it also allows one to couple different dynamical processes on top of such interconnected structures. The resulting framework plays a crucial role in helping to achieve a thorough, accurate understanding of complex systems. The study of multilayer networks has also revealed new physical phenomena that remained hidden when using the traditional network representation of graphs. Here we survey progress towards a deeper understanding of dynamical processes on multilayer networks, and we highlight some of the physical phenomena that emerge from multilayer structure and dynamics.
Manlio De Domenico, Clara Granell, Mason A. Porter, Alex Arenas
https://arxiv.org/pdf/1604.02021v1
📌 ABSTRACT
The study of networks plays a crucial role in investigating the structure, dynamics, and function of a wide variety of complex systems in myriad disciplines. Despite the success of traditional network analysis, standard networks provide a limited representation of these systems, which often includes different types of relationships (i.e., "multiplexity") among their constituent components and/or multiple interacting subsystems. Such structural complexity has a significant effect on both dynamics and function. Throwing away or aggregating available structural information can generate misleading results and provide a major obstacle towards attempts to understand the system under analysis. The recent "multilayer' approach for modeling networked systems explicitly allows the incorporation of multiplexity and other features of realistic networked systems. On one hand, it allows one to couple different structural relationships by encoding them in a convenient mathematical object. On the other hand, it also allows one to couple different dynamical processes on top of such interconnected structures. The resulting framework plays a crucial role in helping to achieve a thorough, accurate understanding of complex systems. The study of multilayer networks has also revealed new physical phenomena that remained hidden when using the traditional network representation of graphs. Here we survey progress towards a deeper understanding of dynamical processes on multilayer networks, and we highlight some of the physical phenomena that emerge from multilayer structure and dynamics.
🔴 The Paper Shredder
Great, curated collection of recent papers about complex systems and networks
http://www.uvm.edu/~cmplxsys/teaching-learning/papershredder/
Great, curated collection of recent papers about complex systems and networks
http://www.uvm.edu/~cmplxsys/teaching-learning/papershredder/
Vermont Complex Systems Center
The Paper Shredder
Every two weeks, and in the grand tradition of courageous academics everywhere, we review the painstaking, meticulous work of others not present to defend themselves. Pure of motivation, we endeavo…