Robustness of community structure in networks
Brian Karrer1, Elizaveta Levina, M E J Newman
1Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA.
Summary
Assessing community structure significance in network analysis is challenging. This study introduces a robustness-based method to quantify community structure significance, distinguishing real patterns from random chance in network data.
Area of Science:
- Network analysis
- Graph theory
- Data science
Background:
- Community structure discovery is crucial in network analysis.
- Assessing the statistical significance of discovered communities is often overlooked.
- Existing methods lack robust significance testing for community structures.
Purpose of the Study:
- To develop a method for quantifying the statistical significance of community structure.
- To differentiate genuine community structures from those arising by chance.
- To provide a robust measure of community significance in network data.
Main Methods:
- Proposing a novel method to perturb network structures.
- Measuring the impact of perturbations on community structure.
- Assessing community significance through robustness analysis.
Main Results:
- Demonstrated that community structure significance can be quantified by robustness to perturbations.
- Successfully applied the method to assess significance in diverse real and synthetic networks.
- The proposed method effectively distinguishes significant community structures.
Conclusions:
- Robustness to network perturbations is a reliable indicator of community structure significance.
- This approach offers a statistically sound way to validate community findings.
- The method enhances the reliability of community detection in network analysis.
Related Concept Videos
01:14Stability of structures
In mechanical engineering, the stability of systems under various forces is critical for designing durable and efficient structures. One fundamental way to explore these concepts is by analyzing systems like two rods connected at a pivot point, O, with a torsional spring of spring constant k at the pivot point. This system is similar in appearance to a scissor jack used to change tires on a car. In this case, the arms of the linkage (equivalent to the rods in this system) are entirely vertical,...
02:26Protein Networks
An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
02:26Protein Networks
An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
02:12Relationship Formation
What do you think is the single most influential factor in determining with whom you become friends and whom you form romantic relationships? You might be surprised to learn that the answer is simple: the people with whom you have the most contact. This most important factor is proximity. You are more likely to be friends with people you have regular contact with. For example, there are decades of research that shows that you are more likely to become friends with people who live in your dorm,...
01:25Network Function of a Circuit
Frequency response analysis in electrical circuits provides vital insights into a circuit's behavior as the frequency of the input signal changes. The transfer function, a mathematical tool, is instrumental in understanding this behavior. It defines the relationship between phasor output and input and comes in four types: voltage gain, current gain, transfer impedance, and transfer admittance. The critical components of the transfer function are the poles and zeros.
02:18Network Covalent Solids
Network covalent solids contain a three-dimensional network of covalently bonded atoms as found in the crystal structures of nonmetals like diamond, graphite, silicon, and some covalent compounds, such as silicon dioxide (sand) and silicon carbide (carborundum, the abrasive on sandpaper). Many minerals have networks of covalent bonds.
To break or to melt a covalent network solid, covalent bonds must be broken. Because covalent bonds are relatively strong, covalent network solids are typically...
To break or to melt a covalent network solid, covalent bonds must be broken. Because covalent bonds are relatively strong, covalent network solids are typically...