Title |
Online Community Detection for Large Complex Networks
|
---|---|
Published in |
PLOS ONE, July 2014
|
DOI | 10.1371/journal.pone.0102799 |
Pubmed ID | |
Authors |
Gang Pan, Wangsheng Zhang, Zhaohui Wu, Shijian Li |
Abstract |
Complex networks describe a wide range of systems in nature and society. To understand complex networks, it is crucial to investigate their community structure. In this paper, we develop an online community detection algorithm with linear time complexity for large complex networks. Our algorithm processes a network edge by edge in the order that the network is fed to the algorithm. If a new edge is added, it just updates the existing community structure in constant time, and does not need to re-compute the whole network. Therefore, it can efficiently process large networks in real time. Our algorithm optimizes expected modularity instead of modularity at each step to avoid poor performance. The experiments are carried out using 11 public data sets, and are measured by two criteria, modularity and NMI (Normalized Mutual Information). The results show that our algorithm's running time is less than the commonly used Louvain algorithm while it gives competitive performance. |
X Demographics
Geographical breakdown
Country | Count | As % |
---|---|---|
Spain | 2 | 25% |
United Kingdom | 2 | 25% |
Portugal | 1 | 13% |
Ecuador | 1 | 13% |
Japan | 1 | 13% |
United States | 1 | 13% |
Demographic breakdown
Type | Count | As % |
---|---|---|
Members of the public | 5 | 63% |
Scientists | 3 | 38% |
Mendeley readers
Geographical breakdown
Country | Count | As % |
---|---|---|
Germany | 1 | 1% |
France | 1 | 1% |
Australia | 1 | 1% |
South Africa | 1 | 1% |
Czechia | 1 | 1% |
Iran, Islamic Republic of | 1 | 1% |
United States | 1 | 1% |
Unknown | 63 | 90% |
Demographic breakdown
Readers by professional status | Count | As % |
---|---|---|
Student > Ph. D. Student | 20 | 29% |
Student > Master | 12 | 17% |
Researcher | 5 | 7% |
Professor > Associate Professor | 4 | 6% |
Student > Doctoral Student | 3 | 4% |
Other | 7 | 10% |
Unknown | 19 | 27% |
Readers by discipline | Count | As % |
---|---|---|
Computer Science | 29 | 41% |
Business, Management and Accounting | 3 | 4% |
Social Sciences | 3 | 4% |
Mathematics | 2 | 3% |
Physics and Astronomy | 2 | 3% |
Other | 9 | 13% |
Unknown | 22 | 31% |