Source-linked AI summary
The clustering coefficient and community structure of bipartite networks
Peng Zhang, Jinliang Wang, Xiaojia Li, Zengru Di, Ying Fan
TL;DR
Many real-world networks are bipartite, yet projection into one-mode networks can lose information and affect community structure. The paper modifies square-based clustering, compares the definitions, and defines an edge-clustering algorithm for original bipartite networks. The modified coefficient is judged better for representing distinct node connections, while the community algorithm works well when structure is clearly defined by topological linkage.
Problem
Projection of bipartite networks can lose information, inflate edge counts, and affect analysis of community structure, motivating direct study of the original graphs.
Method
The paper modifies a square-based bipartite clustering coefficient and defines an edge-clustering-coefficient algorithm for detecting communities without projection.
Results
The modified coefficient is considered better for accounting for distinct node connections, and the community algorithm reproduces the graph-defined communities in an example network.
Takeaways & Limitations
Direct bipartite analysis avoids projection-related drawbacks for community-structure analysis within the demonstrated scope.
Abstract
from arXiv · showhide
Many real-world networks display a natural bipartite structure. It is necessary and important to study the bipartite networks by using the bipartite structure of the data. Here we propose a modification of the clustering coefficient given by the fraction of cycles with size four in bipartite networks. Then we compare the two definitions in a special graph, and the results show that the modification one is better to character the network. Next we define a edge-clustering coefficient of bipartite networks to detect the community structure in original bipartite networks.
1 Introduction
Many real-world networks are naturally bipartite, but projecting them into one-mode networks can lose information and distort structural properties. The paper therefore studies clustering and community structure directly in original bipartite networks.
- Bipartite networks contain two node sets, with edges connecting only nodes from different sets.
- Projecting bipartite networks into one-mode networks can lose information, inflate edge counts, and affect community structure.
- Prior work has introduced bipartite-network measures including clustering, overlap, and betweenness.
- The paper proposes a bipartite clustering coefficient and applies it to two real-world networks.
- It also uses a link-based clustering coefficient to detect communities in original generated bipartite networks.
2 The clustering coefficient of bipartite networks
Because triangles cannot form in bipartite networks, the paper measures clustering through four-node squares and modifies an existing denominator. It compares both definitions on a special graph and real bipartite databases, finding the modification better reflects node connections.
- Motivation: Bipartite clustering measures square density because triangles cannot form; a square is the basic clique in these networks.
- Existing definition: The prior definition uses observed squares over possible squares, with possible-square counts based on neighbor degrees and common-neighbor corrections.
- Modified definition: The modified denominator is (km − ηimn) + (kn − ηimn) + qimn.
- Comparison: For the example with qimm = 1, km = 4, kn = 3, and θmn = 0, equation 1 gives denominator 3, whereas four possible squares are visible.
- Comparison: The authors judge equation 2 better because it accounts for distinct connections at each node when computing C4.
- Real-network comparison: The definitions are also compared on an Econophysicists network of 818 authors and 777 papers and a books-readers database of 17,593 readers and 91,750 books.
3 The community structure of bipartite graphs
The paper defines bipartite community structure through dense within-group links across the two node sets and sparse between-group links, then applies an edge-clustering-based divisive algorithm to detect it without projection.
- Motivation: Projection into one-mode networks can alter the original community structure, motivating analysis directly in bipartite graphs.The paper identifies information loss and edge inflation as projection drawbacks.
- Community structure: Bipartite communities contain dense internal links between top and bottom nodes, while links between groups are sparse.Figure 2 illustrates three such communities.
- Algorithm: The edge-clustering coefficient is the number of squares containing an edge divided by the number of squares that could potentially include it.For an edge joining top node i to bottom node j, the algorithm removes the edge with the smallest Cij at each step.
- Evaluation: The evaluation uses computer-generated bipartite networks with 64 top nodes, 64 bottom nodes, and four communities of 16 nodes from each set.Accuracy is computed from 20 realizations by comparing detected groups with the presumed community structure.
- Illustrative example: On the six-top-node, five-bottom-node example, projection produces two groups, whereas the bipartite algorithm recovers the three communities visible in the original graph.The projected grouping is {{A,B,C},{D,E,F}}, while the original grouping is {{A},{B,C,a,b},{D,E,F,d,e}}.
4 Conclusions
The paper proposes a four-cycle-based clustering coefficient and an edge-clustering algorithm for community detection in original bipartite graphs. It reports better characterization than the compared definition and good performance when communities are topologically well defined, while noting a degree-related limitation.
- Conclusions: The proposed clustering coefficient uses the fraction of size-four cycles in bipartite networks.It is presented as a modification based on earlier work and compared with another definition on a special graph.
- Conclusions: The authors report that their clustering-coefficient definition gives a better answer for the distinct connections of each graph node.The comparison is based on differing results for the special graph.
- Conclusions: The edge-clustering algorithm avoids projection-related drawbacks when analyzing bipartite community structure.The paper supports this claim with the example presented at the end of Section 3.
- Conclusions: The algorithm works well when community structure is well defined by topological linkage in computer-generated bipartite networks.Its accuracy was tested on computer-generated networks.
- Conclusions: The algorithm only considers nodes connected more than twice, which the authors identify as requiring future modification.This is the paper’s stated limitation.