Skip to main content
Top

2014 | OriginalPaper | Chapter

Classification in Social Networks

Authors : Zehra Çataltepe, Abdullah Sönmez

Published in: Social Networks: Analysis and Case Studies

Publisher: Springer Vienna

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Production of social network data in different kinds and huge amounts brings with it classification problems which need to be solved. In this chapter, we introduce a framework for classification in a social network. Aggregation of neighbor labels and sampling are two important aspects of classification in a social network. We give details of different aggregation methods and sampling methods. Then, we discuss different graph properties, especially homophily, which may be helpful in determining which type of classification algorithm should be used. We give details of a collective classification algorithm, ICA (Iterative Classification Algorithm), which can be used for semi-supervised learning in general and transductive learning in particular on a social network. We present classification results on three different datasets, using different aggregation and sampling methods and classifiers.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Ahmed NK, Neville J, Kompella R (2012) Network sampling: from static to streaming graphs. arXiv preprint arXiv:1211.3412 Ahmed NK, Neville J, Kompella R (2012) Network sampling: from static to streaming graphs. arXiv preprint arXiv:1211.3412
2.
go back to reference Awan A, Bari H, Yan F, Moksong S, Yang S, Chowdhury S, Cui Q, Yu Z, Purisima EO, Wang E (2007) Regulatory network motifs and hotspots of cancer genes in a mammalian cellular signalling network. IET Syst Biol 1(5):292–297CrossRef Awan A, Bari H, Yan F, Moksong S, Yang S, Chowdhury S, Cui Q, Yu Z, Purisima EO, Wang E (2007) Regulatory network motifs and hotspots of cancer genes in a mammalian cellular signalling network. IET Syst Biol 1(5):292–297CrossRef
3.
go back to reference Bernstein AA, Clearwater S, Hill S, Perlich C, Provost F (2002) Discovering knowledge from relational data extracted from business news. In: Proceedings of the workshop on multi-relational data mining at KDD-2002, pp 7–22 Bernstein AA, Clearwater S, Hill S, Perlich C, Provost F (2002) Discovering knowledge from relational data extracted from business news. In: Proceedings of the workshop on multi-relational data mining at KDD-2002, pp 7–22
4.
go back to reference Bilgic M, Getoor L (2008) Effective label acquisition for collective classification. In: Li Y, Liu B, Sarawagi S (eds) Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining, Las Vegas, 24–27 August 2008. ACM, New York, pp 43–51 Bilgic M, Getoor L (2008) Effective label acquisition for collective classification. In: Li Y, Liu B, Sarawagi S (eds) Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining, Las Vegas, 24–27 August 2008. ACM, New York, pp 43–51
5.
go back to reference Blum A, Mitchell T (1998) Combining labeled and unlabeled data with co-training. In: COLT, pp 92–100 Blum A, Mitchell T (1998) Combining labeled and unlabeled data with co-training. In: COLT, pp 92–100
6.
go back to reference Chapelle O, Zien A (2005) Semi-supervised classification by low density separation. In: AISTAT 2005 Chapelle O, Zien A (2005) Semi-supervised classification by low density separation. In: AISTAT 2005
7.
go back to reference Colizza V, Flammini A, Serrano MA, Vespignani A (2006) Detecting rich-club ordering in complex networks. Nat Phys 2(2):110–115CrossRef Colizza V, Flammini A, Serrano MA, Vespignani A (2006) Detecting rich-club ordering in complex networks. Nat Phys 2(2):110–115CrossRef
8.
go back to reference Cozman FG, Cohen I (2002) Unlabeled data can degrade classification performance of generative classifiers. In: FLAIRS 2002 Cozman FG, Cohen I (2002) Unlabeled data can degrade classification performance of generative classifiers. In: FLAIRS 2002
9.
go back to reference Cravenand M, DiPasquo D, Freitag D, McCallum A, Mitchell T, Nigam K, Slattery S (1998) Learning to extract symbolic knowledge from the world wide web. In: Proceedings of the fifteenth national conference on artificial intelligence (AAAI), Madison, pp 509–516 Cravenand M, DiPasquo D, Freitag D, McCallum A, Mitchell T, Nigam K, Slattery S (1998) Learning to extract symbolic knowledge from the world wide web. In: Proceedings of the fifteenth national conference on artificial intelligence (AAAI), Madison, pp 509–516
10.
go back to reference Dasgupta K, Singh R, Viswanathan B, Chakraborty D, Mukherjea S, Nanavati AA, Joshi A (2008) Social ties and their relevance to churn in mobile telecom networks. In: EDBT08 Dasgupta K, Singh R, Viswanathan B, Chakraborty D, Mukherjea S, Nanavati AA, Joshi A (2008) Social ties and their relevance to churn in mobile telecom networks. In: EDBT08
11.
go back to reference Dorogovtsev SN, Mendes JF (2002). Evolution of networks. Adv Phys 51(4):1079–1187CrossRef Dorogovtsev SN, Mendes JF (2002). Evolution of networks. Adv Phys 51(4):1079–1187CrossRef
12.
13.
go back to reference Fronczak A, Fronczak P, Holyst JA (2004) Average path length in uncorrelated random networks with hidden variables. Phys Rev E 70(5):056110, 1–7 Fronczak A, Fronczak P, Holyst JA (2004) Average path length in uncorrelated random networks with hidden variables. Phys Rev E 70(5):056110, 1–7
14.
go back to reference Giles CL, Bollacker K, Lawrence S (1998) Citeseer: an automatic citation indexing system. In: ACM digital libraries, pp 89–98 Giles CL, Bollacker K, Lawrence S (1998) Citeseer: an automatic citation indexing system. In: ACM digital libraries, pp 89–98
15.
go back to reference Hanneman RA, Riddle M (2005) Introduction to social network methods. University of California, Riverside Hanneman RA, Riddle M (2005) Introduction to social network methods. University of California, Riverside
16.
go back to reference Hein O, Schwind M, Konig W (2006) Scale-free networks: the impact of fat tailed degree distribution on diffusion and communication processes. Wirtschaftsinformatik 48(4):267–275CrossRef Hein O, Schwind M, Konig W (2006) Scale-free networks: the impact of fat tailed degree distribution on diffusion and communication processes. Wirtschaftsinformatik 48(4):267–275CrossRef
17.
go back to reference Jensen D, Neville J (2002) Linkage and autocorrelation cause feature selection bias in relational learning. In: Proceedings of the 19th international conference on machine learning. Morgan Kaufmann, San Francisco, pp 259–266 Jensen D, Neville J (2002) Linkage and autocorrelation cause feature selection bias in relational learning. In: Proceedings of the 19th international conference on machine learning. Morgan Kaufmann, San Francisco, pp 259–266
18.
go back to reference Joachims T (2003) Transductive learning via spectral graph partitioning. In: ICML 2003, pp 200–209 Joachims T (2003) Transductive learning via spectral graph partitioning. In: ICML 2003, pp 200–209
19.
go back to reference Kahng GO, Oh E, Kahng B, Kim D (2003) Betweenness centrality correlation in social networks. Phys Rev E 67:01710–01711 Kahng GO, Oh E, Kahng B, Kim D (2003) Betweenness centrality correlation in social networks. Phys Rev E 67:01710–01711
20.
go back to reference Leskovec J, Faloutsos C (2006, August) Sampling from large graphs. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 631–636 Leskovec J, Faloutsos C (2006, August) Sampling from large graphs. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 631–636
21.
go back to reference Macskassy SA, Provost F (2007) Classification in networked data: a toolkit and a univariate case study. J Mach Learn Res 8:935–983 Macskassy SA, Provost F (2007) Classification in networked data: a toolkit and a univariate case study. J Mach Learn Res 8:935–983
22.
go back to reference McCallum A, Nigam K, Rennie J, Seymore K (2000) Automating the construction of internet portals with machine learning. Inf Retr J 3(2):127–163CrossRef McCallum A, Nigam K, Rennie J, Seymore K (2000) Automating the construction of internet portals with machine learning. Inf Retr J 3(2):127–163CrossRef
23.
go back to reference McDowell L, Gupta KM, Aha DW (2007) Cautious inference in collective classification. In: AAAI. AAAI Press, Menlo Park, pp 596–601 McDowell L, Gupta KM, Aha DW (2007) Cautious inference in collective classification. In: AAAI. AAAI Press, Menlo Park, pp 596–601
24.
go back to reference Neville J, Jensen D (2008) A bias/variance decomposition for models using collective inference. Mach Learn 73(1):87–106CrossRef Neville J, Jensen D (2008) A bias/variance decomposition for models using collective inference. Mach Learn 73(1):87–106CrossRef
25.
go back to reference Neville J, Gallagher B, Eliassi-Rad T (2009) Evaluating statistical tests for within-network classifiers of relational data. In: ICDM Neville J, Gallagher B, Eliassi-Rad T (2009) Evaluating statistical tests for within-network classifiers of relational data. In: ICDM
27.
go back to reference Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45(2):167256CrossRef Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45(2):167256CrossRef
28.
go back to reference Perlich C, Huang Z (2005) Relational learning for customer relationship management. In: Proceedings of international workshop on customer relationship management: data mining meets marketing Perlich C, Huang Z (2005) Relational learning for customer relationship management. In: Proceedings of international workshop on customer relationship management: data mining meets marketing
29.
go back to reference Perlich C, Provost FJ (2006) Distribution-based aggregation for relational learning with identifier attributes. Mach Learn 62(1–2):65–105CrossRef Perlich C, Provost FJ (2006) Distribution-based aggregation for relational learning with identifier attributes. Mach Learn 62(1–2):65–105CrossRef
30.
go back to reference Preisach C, Schmidt-Thieme L (2008) Ensembles of relational classifiers. Knowl Inf Syst 14(3):249–272CrossRefMATH Preisach C, Schmidt-Thieme L (2008) Ensembles of relational classifiers. Knowl Inf Syst 14(3):249–272CrossRefMATH
31.
go back to reference Provost F, Perlich C, Macskassy S (2003) Relational learning problems and simple models. In: Proceedings of the IJCAI-2003 workshop on learning statistical models from relational data Provost F, Perlich C, Macskassy S (2003) Relational learning problems and simple models. In: Proceedings of the IJCAI-2003 workshop on learning statistical models from relational data
32.
go back to reference Sen P, Getoor L (2006) Empirical comparison of approximate inference algorithms for networked data. In: ICML workshop on open problems in statistical relational learning (SRL2006) Sen P, Getoor L (2006) Empirical comparison of approximate inference algorithms for networked data. In: ICML workshop on open problems in statistical relational learning (SRL2006)
33.
go back to reference Sen P, Getoor L (2007) Link-based classification. UM Computer Science Department, Technical Report, CS-TR-4858. University of Maryland Sen P, Getoor L (2007) Link-based classification. UM Computer Science Department, Technical Report, CS-TR-4858. University of Maryland
34.
go back to reference Sen P, Namata G, Bilgic M, Getoor L, Gallagher B, Eliassi-Rad T (2008) Collective classification in network data. AI Mag 29(3):93–106 Sen P, Namata G, Bilgic M, Getoor L, Gallagher B, Eliassi-Rad T (2008) Collective classification in network data. AI Mag 29(3):93–106
35.
go back to reference Snijders TAB (1992) Estimation on the basis of snowball samples: How to weight? BMS: Bull Sociol Methodol (Bulletin de M thodologie Sociologique) 36(1):59–70 Snijders TAB (1992) Estimation on the basis of snowball samples: How to weight? BMS: Bull Sociol Methodol (Bulletin de M thodologie Sociologique) 36(1):59–70
36.
go back to reference Tresp V, Bundschus M, Rettinger A, Huang Y (2008) Towards machine learning on the semantic web. In: Uncertainty reasoning for the semantic web I. Lecture notes in AI. Springer, Berlin Tresp V, Bundschus M, Rettinger A, Huang Y (2008) Towards machine learning on the semantic web. In: Uncertainty reasoning for the semantic web I. Lecture notes in AI. Springer, Berlin
37.
go back to reference Wang W, Zhou ZH (2007) Analyzing co-training style algorithms. In: Machine Learning: ECML 2007 (pp. 454–465). Springer Berlin Heidelberg Wang W, Zhou ZH (2007) Analyzing co-training style algorithms. In: Machine Learning: ECML 2007 (pp. 454–465). Springer Berlin Heidelberg
38.
go back to reference Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393: 440–442CrossRef Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393: 440–442CrossRef
39.
go back to reference Xiang R, Neville J, Rogati M (2010) Modeling relationship strength in online social networks. In: Proceedings of the 19th international conference on World wide web. ACM, New York, pp 981–990 Xiang R, Neville J, Rogati M (2010) Modeling relationship strength in online social networks. In: Proceedings of the 19th international conference on World wide web. ACM, New York, pp 981–990
40.
go back to reference Yang Y, Slattery S, Ghani R (2002) A study of approaches to hypertext categorization. J Intell Inf Syst 18(2/3):219–241CrossRef Yang Y, Slattery S, Ghani R (2002) A study of approaches to hypertext categorization. J Intell Inf Syst 18(2/3):219–241CrossRef
41.
go back to reference Yaslan Y, Cataltepe Z (2010) Co-training with relevant random subspaces. Neurocomputing 73(10–12):1652–1661CrossRef Yaslan Y, Cataltepe Z (2010) Co-training with relevant random subspaces. Neurocomputing 73(10–12):1652–1661CrossRef
42.
go back to reference Yonghong T, Tiejun H, Wen G (2006) Latent linkage semantic kernels for collective classification of link data. J Intell Inf Syst 26(3):269–301CrossRef Yonghong T, Tiejun H, Wen G (2006) Latent linkage semantic kernels for collective classification of link data. J Intell Inf Syst 26(3):269–301CrossRef
43.
go back to reference Zhu X (2007) Semi-supervised learning literature survey. Computer Sciences Technical Report, TR 1530. University of Wisconsin Madison Zhu X (2007) Semi-supervised learning literature survey. Computer Sciences Technical Report, TR 1530. University of Wisconsin Madison
Metadata
Title
Classification in Social Networks
Authors
Zehra Çataltepe
Abdullah Sönmez
Copyright Year
2014
Publisher
Springer Vienna
DOI
https://doi.org/10.1007/978-3-7091-1797-2_7

Premium Partner