The k-Dense Method to Extract Communities from Complex Networks - Mining Complex Data - page 244

experiments using three types of real networks assembled from blog trackbacks,
word associations and Wikipedia references, we demonstrated that the k -dense
method could extract communities almost as eciently as the k -core method,
while the qualities of the extracted communities are comparable to those ob-
tained by the k -clique method. we plan to perform more extensive experiments
using a wider variety of networks in order to clarify relative strength and weak-
ness of the k -dense method.
References
1. Applegate, D., Johnson, D.S.: Clique-finding program dfmax.c, C program,
ftp://dimacs.rutgers.edu/pub/challenge/graph/solvers/
2. Batagelj, V., Zaversnik, M.: Generalized Cores, arXiv:cs.DS/0202039 (2002)
3. Brandes, U., Erlebach, T. (eds.): Network Analysis. LNCS, vol. 3418, pp. 1-6.
Springer, Heidelberg (2005)
4. Carragan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem.
Oper. Res. Lett. 9, 375-382 (1990)
5. Flake, G.W., Lawrence, S., Giles, C.L.: Ecient identification of Web commu-
nities. In: Proceedings of the Sixth ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, pp. 150-160 (2000)
6. Garey, M., Johnson, D.S.: Computers and intractability: a guide to the theory of
NP-completeness. W.H. Freeman, San Francisco (1979)
7. Girvan, M., Newman, M.E.J.: Community structure in social and biological net-
works. In: Proceedings of the National Academy of Sciences of the United States
of America, vol. 99, pp. 7821-7826 (2002)
8. Kamada, T., Kawai, S.: An algorithm for drawing general undirected graph. Infor-
mation Processing Letters 32, 7-15 (1989)
9. Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Trawling the Web for
emerging cyber-communities. In: Proceedings of the 8th International World Wide
Web Conference (1999)
10. Palla, G., Derenyi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community
structure of complex networks in nature and society. Nature 435, 814-818 (2005)
11. Nelson, D.L., McEvoy, C.L., Schreiber, T.A.: The University of South Florida word
association norms, http://w3.usf.edu/FreeAssociation
12. Newman, M.E.J.: The structure and function of complex network. SIAM Re-
view 45(2), 167-256 (2003)
13. Kimura, M., Saito, K., Kazama, K., Sato, S.: Detecting Search Engine Spam from
a Trackback Network in Blogspace. In: Proceedings of KES 2005, Vol. IV, pp.
723-729 (2005)
14. Seidman, S.B.: Network Structure and Minimum Degree. Social Networks 5, 269-
287 (1983)
15. Shi, R., Malik, J.: Normalized cuts and image segmentation. IEEE Trans.
PAMI 22(8), 888-905 (2000)
16. Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating
all the maximal independent sets. SIAM J. Comput. 6, 505-517 (1977)
17. Yamada, T., Saito, K., Kazama, K.: Network analyses to understand the structure
of Wikipedia. In: Proceedings of AISB 2006, vol. 3, pp. 195-198 (2006)