×

Detecting the fuzzy clusters of complex networks. (English) Zbl 1192.68589

Summary: To find the best partition of a large and complex network into a small number of clusters has been addressed in many different ways. However, the probabilistic setting in which each node has a certain probability of belonging to a certain cluster has been scarcely discussed. In this paper, a fuzzy partitioning formulation, which is extended from a deterministic framework for network partition based on the optimal prediction of a random walker Markovian dynamics, is derived to solve this problem. The algorithms are constructed to minimize the objective function under this framework. It is demonstrated by the simulation experiments that our algorithms can efficiently determine the probabilities with which a node belongs to different clusters during the learning process. Moreover, they are successfully applied to two real-world networks, including the social interactions between members of a karate club and the relationships of some books on American politics bought from Amazon.com.

MSC:

68T10 Pattern recognition, speech recognition

Software:

ElemStatLearn
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Rev. Mod. Phys., 74, 1, 47-97 (2002) · Zbl 1205.82086
[2] Newman, M.; Barabási, A.-L.; Watts, D. J., The Structure and Dynamics of Networks (2005), Princeton University Press: Princeton University Press Princeton, NJ
[3] National Research Council, Network Science, National Academy of Sciences, Washington DC, 2005.; National Research Council, Network Science, National Academy of Sciences, Washington DC, 2005.
[4] Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intel, 22, 888-905 (2000)
[5] M. Meilaˇ, J. Shi, A random walks view of spectral segmentation, in: Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, 2001, pp. 92-97.; M. Meilaˇ, J. Shi, A random walks view of spectral segmentation, in: Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, 2001, pp. 92-97.
[6] Girvan, M.; Newman, M., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, 99, 12, 7821-7826 (2002) · Zbl 1032.91716
[7] Newman, M., Fast algorithm for detecting community structure in networks, Phys. Rev. E, 69, 066133 (2004)
[8] Newman, M.; Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. E, 69, 2, 26113 (2004)
[9] Newman, M., Detecting community structure in networks, Eur. Phys. J. B, 38, 2, 321-330 (2004)
[10] Newman, M., Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA, 103, 23, 8577-8582 (2006)
[11] Lafon, S.; Lee, A. B., Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization, IEEE Trans. Pattern Anal. Mach. Intel, 1393-1403 (2006)
[12] Li, W. E.T.; Vanden-Eijnden, E., Optimal partition and effective dynamics of complex networks, Proc. Natl. Acad. Sci. USA, 105, 7907-7912 (2008) · Zbl 1205.68031
[13] Li, T.; Liu, J.; E, W., Probabilistic framework for network partition, Phys. Rev. E, 80, 026106 (2009)
[14] Hofman, J. M.; Wiggins, C. H., A Bayesian approach to network modularity, Phys. Rev. Lett., 100, 258701 (2008)
[15] Schilders, W.; van der Vorst, H.; Rommes, J., Model Order Reduction: Theory, Research Aspects and Applications (2008), Springer: Springer Berlin, Heidelberg · Zbl 1143.65004
[16] Danon, L.; Diaz-Guilera, A.; Duch, J.; Arenas, A., Comparing community structure identification, J. Stat. Mech., 9, P09008 (2005) · Zbl 07077983
[17] Chorin, A.; Kast, A.; Kupferman, R., Unresolved computation and optimal predictions, Commun. Pure Appl. Math., 52, 10, 1231-1254 (1999) · Zbl 0933.65123
[18] Chorin, A., Conditional expectations and renormalization, Multi. Model. Simul., 1, 105-118 (2003) · Zbl 1064.65004
[19] L. Lovasz, Random walks on graphs: a survey, Combinatorics, Paul Erdos is Eighty, vol. 2, 1993, pp. 1-46.; L. Lovasz, Random walks on graphs: a survey, Combinatorics, Paul Erdos is Eighty, vol. 2, 1993, pp. 1-46.
[20] Devijver, P. A.; Kittter, J., Pattern Recognition: A Statistical Approach (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[21] Hastie, T.; Tibshirani, R.; Friedman, J., The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2001), Springer: Springer New York · Zbl 0973.62007
[22] Dunn, J., A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters, Cybern. Syst., 3, 3, 32-57 (1973) · Zbl 0291.68033
[23] Bezdek, J., Pattern Recognition with Fuzzy Objective Function Algorithms (1981), Plenum Press: Plenum Press New York · Zbl 0503.68069
[24] Chung, F., Spectral Graph Theory (1997), American Mathematical Society: American Mathematical Society Rhode Island
[25] Ma, J.; Wang, L., BYY harmony learning on finite mixture: adaptive gradient implementation and a floating RPCL mechanism, Neural Process. Lett., 24, 19-40 (2006)
[26] Ma, J.; Wang, T.; Xu, L., A gradient BYY Harmony learning rule on Gaussian mixture with automated model selection, Neurocomputing, 56, 481-487 (2004)
[27] Ma, J.; Gao, B.; Wang, Y.; Cheng, Q., Conjugate and natural gradient rules for BYY harmony learning on Gaussian mixture with automated model selection, Int. J. Pattern Recognition Artif. Intell., 19, 701-713 (2005)
[28] Qian, N., On the momentum term in gradient descent learning algorithms, Neural Networks, 12, 1, 145-151 (1999)
[29] Penrose, M., Random Geometric Graphs (2003), Oxford University Press: Oxford University Press Oxford · Zbl 1029.60007
[30] Zachary, W., An information flow model for conflict and fission in small groups, J. Anthrop. Res., 33, 4, 452-473 (1977)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.