Institutional Repository
| Evaluating community structure in the large network with random walks | |
| Li, Jiankou (1); Li, J. | |
| 2013 | |
| Conference Name | 2013 Science and Information Conference, SAI 2013 |
| Pages | 315-319 |
| Conference Date | October 7, 2013 - October 9, 2013 |
| Conference Place | London, United kingdom |
| Indexed Type | EI |
| Publish Place | IEEE Computer Society, 2001 L Street N.W., Suite 700, Washington, DC 20036-4928, United States |
| ISBN | 9780989319300 |
| Department | (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; (2) University of Chinese Academy of Sciences, China |
| English Abstract | Community structure is one of the most important properties of networks. Most community algorithms are not suitable for large networks because of their time consuming. In fact there are lots of networks with millions even billions of nodes. In such case, most algorithms running in time O(n2logn) or even larger are not practical. What we need are linear or approximately linear time algorithm. Rising in response to such needs, we propose a quick method to evaluate community structure in networks and then put forward a local community algorithm with nearly linear time based on random walks. Using our community evaluating measure, we could find some difference results from measures used before, i.e., the Newman Modularity. Our algorithm are effective in small benchmark networks with small less accuracy than more complex algorithms but a great of advantage in time consuming for large networks, especially super large networks. © 2013 The Science and Information Organization.; Community structure is one of the most important properties of networks. Most community algorithms are not suitable for large networks because of their time consuming. In fact there are lots of networks with millions even billions of nodes. In such case, most algorithms running in time O(n2logn) or even larger are not practical. What we need are linear or approximately linear time algorithm. Rising in response to such needs, we propose a quick method to evaluate community structure in networks and then put forward a local community algorithm with nearly linear time based on random walks. Using our community evaluating measure, we could find some difference results from measures used before, i.e., the Newman Modularity. Our algorithm are effective in small benchmark networks with small less accuracy than more complex algorithms but a great of advantage in time consuming for large networks, especially super large networks. © 2013 The Science and Information Organization. |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16650 |
| Collection | 中国科学院软件研究所 |
| Corresponding Author | Li, J. |
| Recommended Citation GB/T 7714 | Li, Jiankou ,Li, J.. Evaluating community structure in the large network with random walks[C]. IEEE Computer Society, 2001 L Street N.W., Suite 700, Washington, DC 20036-4928, United States,2013:315-319. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment