Link prediction of multimedia social network via unsupervised face recognition

ABSTRACT

We propose a new challenge for predicting links of social networks by unsupervised face recognition on photo albums. We solve the task by formulating it into Kernel Set Discovery problem. We enhance Affinity Propagation algorithm to tackle the problem with more constraints. More specifically, the face cannot appear more than once in the same photo and we impose constraints such that detected face images in the same photograph are never clustered into the same person. We construct a synthetic dataset based on AT\&T image benchmark for empirical validation. Moreover, we validate our algorithms by a real world application which contains a real friend relation on the Web 2.0 social network system. Results indicate our Constraint Affinity Propagation method is suitable to unsupervisedly predict links of social network.

REFERENCES

• 1: D. Dueck, B. J. Frey, N. Jojic, V. Jojic, G. Giaever, A. Emili, G. Musso, and R. Hegele. Constructing treatment portfolios using affinity propagation. In M. Vingron and L. Wong, editors, RECOMB, volume 4955 of Lecture Notes in Computer Science, pages 360--371. Springer, 2008.
• 2: Frey and Dueck. Clustering by passing messages between data points. SCIENCE: Science, 315, 2007.
• 3: A. C. Gallagher and T. H. Chen. Using group prior to identify people in consumer images. In Semantic Learning Applications in Multimedia, pages 1--8, 2007.
• 4: Y. Jing and S. Baluja. Pagerank for product image search. In WWW, pages 307--316. ACM, 2008.
• 5: G. Kim, C. Faloutsos, and M. Hebert. Unsupervised modeling of object categories using link analysis techniques. In CVPR, pages 1--8, 2008.
• 6: H. W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, pages 83--97, 1955.
• 7: S. P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28:128--137, 1982.
• 8: N. F. S. Yardi and A. Bruckman. Photo-based authentication using social networks. In WOSN. IEEE, 2008.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Sociology

General Terms:
Algorithms, Human Factors

Keywords:
constraint affinity propagation, link prediction, social networks