Evaluating community structure in the large network with random walks

ISCAS OpenIR

	Evaluating community structure in the large network with random walks
	Li, Jiankou (1); Li, J.
	2013
会议名称	2013 Science and Information Conference, SAI 2013
页码	315-319
会议日期	October 7, 2013 - October 9, 2013
会议地点	London, United kingdom
收录类别	EI
出版地	IEEE Computer Society, 2001 L Street N.W., Suite 700, Washington, DC 20036-4928, United States
ISBN	9780989319300
部门归属	(1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; (2) University of Chinese Academy of Sciences, China
摘要	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(n²logn) 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(n²logn) 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.
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16650
专题	中国科学院软件研究所
通讯作者	Li, J.
推荐引用方式 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.