Top

Published in:

2017 | OriginalPaper | Chapter

Descriptive Community Detection

Author : Martin Atzmueller

Published in: Formal Concept Analysis of Social Networks

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Subgroup discovery and community detection are standard approaches for identifying (cohesive) subgroups. This paper presents an organized picture of recent research in descriptive community (and subgroup) detection. Here, it summarizes approaches for the identification of descriptive patterns targeting both static and dynamic (sequential) relations. We specifically focus on attributed graphs, i.e.,complex relational graphs that are annotated with additional information. This relates to attribute information, for example, assigned to the nodes and/or edges of the graph. Combining subgroup discovery and community detection, we also summarize an efficient and effective approach for descriptive community detection.

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!

inform now

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!

inform now

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!

inform now

previous chapter Individuality in Social Networks

next chapter Multimodal Clustering for Community Detection

http://www.everyaware.eu.

Adnan, M., Alhajj, R., Rokne, J.: Identifying social communities by frequent pattern mining. In: Proc. 13th Intl. Conf. Information Visualisation, pp. 413–418. IEEE Computer Society, Washington, DC (2009)

Agrawal, R., Srikant, R.: Fast algorithms for mining association rules. In: Bocca, J.B., Jarke, M., Zaniolo, C. (eds.) Proc. 20th Int. Conf. Very Large Data Bases (VLDB), pp. 487–499. Morgan Kaufmann, San Francisco (1994)

Agresti, A.: An Introduction to Categorical Data Analysis. Wiley, Hoboken (2007)CrossRef

Atzmueller, M.: Data mining on social interaction networks. J. Data Min. Digit. Humanit. 1, pp. 1–34 (2014)

Atzmueller, M.: Subgroup and community analytics on attributed graphs. In: Kuznetsov, S.O., Missaoui, R., Obiedkov, S. (eds.) Proceedings of the International Workshop on Social Network Analysis Using Formal Concept Analysis (SNAFCA-2015), CEUR-WS, vol. 1534 (2015)

Atzmueller, M.: Subgroup discovery – advanced review. WIREs Data Min. Knowl. Discov. 5(1), 35–49 (2015)CrossRef

Atzmueller, M.: Detecting community patterns capturing exceptional link trails. In: Proceedings of the IEEE/ACM ASONAM. IEEE Press, Boston, MA (2016)CrossRef

Atzmueller, M.: Local exceptionality detection on social interaction networks. In: Proceedings of the ECML-PKDD 2016: European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Springer, Berlin (2016)CrossRef

Atzmueller, M., Lemmerich, F.: Fast subgroup discovery for continuous target concepts. In: Proceedings of the International Symposium on Methodologies for Intelligent Systems. LNCS, vol. 5722, pp. 1–15. Springer, Heidelberg (2009)

10.

Atzmueller, M., Lemmerich, F.: VIKAMINE - open-source subgroup discovery, pattern mining, and analytics. In: Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Springer, Heidelberg (2012)CrossRef

11.

Atzmueller, M., Lemmerich, F.: Exploratory pattern mining on social media using geo-references and social tagging information. Int. J. Web Sci. 2(1/2), 80–112 (2013)CrossRef

12.

Atzmueller, M., Mitzlaff, F.: Efficient descriptive community mining. In: Proceedings of the 24th International FLAIRS Conference, pp. 459–464. AAAI Press, Palo Alto, CA (2011)

13.

Atzmueller, M., Puppe, F.: Semi-automatic visual subgroup mining using VIKAMINE. J. Univers. Comput. Sci. 11(11), 1752–1765 (2005)

14.

Atzmueller, M., Puppe, F.: SD-Map - a fast algorithm for exhaustive subgroup discovery. In: Proceedings of the European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD), pp. 6–17. Springer, Heidelberg (2006)

15.

Atzmueller, M., Puppe, F.: A case-based approach for characterization and analysis of subgroup patterns. J. Appl. Intell. 28(3), 210–221 (2008)CrossRef

16.

Atzmueller, M., Roth-Berghofer, T.: The mining and analysis continuum of explaining uncovered. In: Proceedings of the 30th SGAI International Conference on Artificial Intelligence (AI-2010) (2010)

17.

Atzmueller, M., Baumeister, J., Hemsing, A., Richter, E.J., Puppe, F.: Subgroup mining for interactive knowledge refinement. In: Proceedings of the 10th Conference on Artificial Intelligence in Medicine (AIME 05). LNAI, vol. 3581, pp. 453–462. Springer, Heidelberg (2005)CrossRef

18.

Atzmueller, M., Baumeister, J., Puppe, F.: Introspective subgroup analysis for interactive knowledge refinement. In: Proceedings of the 19th International Florida Artificial Intelligence Research Society Conference 2006 (FLAIRS-2006), pp. 402–407. AAAI Press, Palo Alto, CA (2006)

19.

Atzmueller, M., Becker, M., Kibanov, M., Scholz, C., Doerfel, S., Hotho, A., Macek, B.E., Mitzlaff, F., Mueller, J., Stumme, G.: Ubicon and its applications for ubiquitous social computing. New Rev. Hypermedia Multimed. 20(1), 53–77 (2014)CrossRef

20.

Atzmueller, M., Mueller, J., Becker, M.: Exploratory subgroup analytics on ubiquitous data. In: Mining, Modeling and Recommending ‘Things’ in Social Media. LNAI, vol. 8940. Springer, Heidelberg (2015)

21.

Atzmueller, M., Doerfel, S., Mitzlaff, F.: Description-oriented community detection using exhaustive subgroup discovery. Inf. Sci. 329, 965–984 (2016)CrossRef

22.

Atzmueller, M., Mollenhauer, D., Schmidt, A.: Big data analytics using local exceptionality detection. In: Enterprise Big Data Engineering, Analytics, and Management. IGI Global, Hershey, PA (2016)CrossRef

23.

Atzmueller, M., Schmidt, A., Kibanov, M.: DASHTrails: an approach for modeling and analysis of distribution-adapted sequential hypotheses and trails. In: Proceedings of the WWW 2016 (Companion), IW3C2/ACM (2016)CrossRef

24.

Atzmueller, M., Schmidt, A., Kloepper, B., Arnu, D.: HypGraphs: an approach for modeling and comparing graph-based and sequential hypotheses. In: Proceedings of the ECML-PKDD Workshop on New Frontiers in Mining Complex Patterns (NFMCP), Riva del Garda (2016)

25.

Clancey, W.J.: The epistemology of a rule-based expert system: a framework for explanation. Artif. Intell. 20, 215–251 (1983)CrossRef

26.

Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010)MathSciNetCrossRef

27.

Freeman, L.: Segregation in social networks. Sociol. Methods Res. 6(4), 411 (1978)CrossRef

28.

Galbrun, E., Gionis, A., Tatti, N.: Overlapping community detection in labeled graphs. Data Min. Knowl. Discov. 28(5–6), 1586–1610 (2014)MathSciNetCrossRef

29.

Geng, L., Hamilton, H.J.: Interestingness measures for data mining: a survey. ACM Comput. Surv. 38(3), Article No. 9 (2006)CrossRef

30.

Gregory, S.: Finding overlapping communities in networks by label propagation. New J. Phys. 12, 103018 (2010)CrossRef

31.

Grosskreutz, H., Rüping, S., Wrobel, S.: Tight optimistic estimates for fast subgroup discovery. In: Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. LNCS, vol. 5211, pp. 440–456. Springer, Heidelberg (2008)

32.

Günnemann, S., Färber, I., Boden, B., Seidl, T.: GAMer: a synthesis of subspace clustering and dense subgraph mining. In: Knowledge and Information Systems. Springer, London (2013)

33.

Kibanov, M., Atzmueller, M., Scholz, C., Stumme, G.: Temporal evolution of contacts and communities in networks of face-to-face human interactions. Sci. China 57, 1–17 (2014)

34.

Kibanov, M., Atzmueller, M., Illig, J., Scholz, C., Barrat, A., Cattuto, C., Stumme, G.: Is web content a good proxy for real-life interaction? A case study considering online and offline interactions of computer scientists. In: Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). IEEE Press, Boston, MA (2015)

35.

Klösgen, W.: Explora: a multipattern and multistrategy discovery assistant. In: Fayyad, U.M., Piatetsky-Shapiro, G., Smyth, P., Uthurusamy, R. (eds.) Advances in Knowledge Discovery and Data Mining, pp. 249–271. AAAI Press, Menlo Park (1996)

36.

Klösgen, W.: 16.3: subgroup discovery. In: Handbook of Data Mining and Knowledge Discovery. Oxford University Press, New York (2002)

37.

Klösgen, W.: 5.2: subgroup patterns. In: Handbook of Data Mining and Knowledge Discovery. Oxford University Press, New York (2002)

38.

Koyuturk, M., Szpankowski, W., Grama, A.: Assessing significance of connectivity and conservation in protein interaction networks. J. Comput. Biol. 14(6), 747–764 (2007)MathSciNetCrossRef

39.

Krackhardt, D.: QAP partialling as a test of spuriousness. Soc. Netw. 9, 171–186 (1987)MathSciNetCrossRef

40.

Lancichinetti, A., Fortunato, S., Kertsz, J.: Detecting the overlapping and hierarchical community structure in complex networks. New J. Phys. 11(3), 033015 (2009)CrossRef

41.

Leman, D., Feelders, A., Knobbe, A.: Exceptional model mining. In: Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Lecture Notes in Computer Science, vol. 5212, pp. 1–16. Springer, Heidelberg (2008)

42.

Lemmerich, F., Becker, M., Atzmueller, M.: Generic pattern trees for exhaustive exceptional model mining. In: Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Springer, Heidelberg (2012)CrossRef

43.

Lemmerich, F., Atzmueller, M., Puppe, F.: Fast exhaustive subgroup discovery with numerical target concepts. Data Min. Knowl. Discov. 30, 711–762 (2016)MathSciNetCrossRef

44.

Lempel, R., Moran, S.: The stochastic approach for link-structure analysis (SALSA) and the TKC effect. Comput. Netw. 33(1), 387–401 (2000)CrossRef

45.

Lin, Y.R., Chi, Y., Zhu, S., Sundaram, H., Tseng, B.L.: Analyzing communities and their evolutions in dynamic social networks. ACM Trans. Knowl. Discov. Data 3, 8:1–8:31 (2009)CrossRef

46.

McDaid, A., Hurley, N.: Detecting highly overlapping communities with model-based overlapping seed expansion. In: Proceedings of the International Conference on Advances in Social Networks Analysis and Mining, ASONAM, pp. 112–119. IEEE Computer Society, Washington, DC (2010)

47.

Mitzlaff, F., Atzmueller, M., Stumme, G., Hotho, A.: Semantics of user interaction in social media. In: Ghoshal, G., Poncela-Casasnovas, J., Tolksdorf, R. (eds.) Complex Networks IV. Studies in Computational Intelligence, vol. 476. Springer, Heidelberg (2013)

48.

Mitzlaff, F., Atzmueller, M., Hotho, A., Stumme, G.: The social distributional hypothesis. J. Soc. Netw. Anal. Min. 4, 216 (2014)CrossRef

49.

Moser, F., Colak, R., Rafiey, A., Ester, M.: Mining cohesive patterns from graphs with feature vectors. In: SDM, SIAM, vol. 9, pp. 593–604 (2009)

50.

Muff, S., Rao, F., Caflisch, A.: Local modularity measure for network clusterizations. Phys. Rev. E Stat. Nonlinear Matter Phys. 72(5), 056107 (2005)CrossRef

51.

Newman, M.E.J.: Detecting community structure in networks. Eur. Phys. J. 38, 321–330 (2004)CrossRef

52.

Newman, M.E.J.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. 103(23), 8577–8582 (2006)CrossRef

53.

Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E Stat. Nonlin Soft Matter Phys. 69(2), 1–15 (2004)CrossRef

54.

Nicosia, V., Mangioni, G., Carchiolo, V., Malgeri, M.: Extending the definition of modularity to directed graphs with overlapping communities. J. Stat. Mech. 2009, 03024 (2009)

55.

Palla, G., Dernyi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814–818 (2005)CrossRef

56.

Palla, G., Farkas, I.J., Pollner, P., Derenyi, I., Vicsek, T.: Directed network modules. New J. Phys. 9(6), 186 (2007)CrossRef

57.

Pool, S., Bonchi, F., van Leeuwen, M.: Description-driven community detection. Trans. Intell. Syst. Technol. 5(2), 1–21 (2014)CrossRef

58.

Raghavan, U., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76, 036106 (2007)CrossRef

59.

Roth-Berghofer, T.R., Cassens, J.: Mapping goals and kinds of explanations to the knowledge containers of case-based reasoning systems. In: Muñoz-Avila, H., Ricci, F. (eds.) Case-Based Reasoning Research and Development, 6th International Conference on Case-Based Reasoning, ICCBR 2005, Chicago, IL, USA, August 2005, Proceedings. Lecture Notes in Artificial Intelligence, vol. 3620, pp. 451–464. Springer, Heidelberg (2005)

60.

Scholz, C., Atzmueller, M., Stumme, G.: On the predictability of human contacts: influence factors and the strength of stronger ties. In: Proceedings of the 4th ASE/IEEE International Conference on Social Computing (SocialCom). IEEE Computer Society, Boston, MA (2012)

61.

Scholz, C., Atzmueller, M., Barrat, A., Cattuto, C., Stumme, G.: New Insights and Methods For Predicting Face-To-Face Contacts. In: Kiciman E, Ellison NB, Hogan B, Resnick P, Soboroff I (eds) Proc. International AAAI Conference on Weblogs and Social Media. AAAI Press, Palo Alto, CA (2013)

62.

Scholz, C., Atzmueller, M., Kibanov, M., Stumme, G.: How do people link? Analysis of contact structures in human face-to-face proximity networks. In: Proc. ASONAM 2013. ACM Press, New York, NY (2013)

63.

Sese, J., Seki, M., Fukuzaki, M.: Mining networks with shared items. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management, pp. 1681–1684. ACM, New York, NY (2010)

64.

Silva, A., Meira Jr., W., Zaki, M.J.: Mining attribute-structure correlated patterns in large attributed graphs. Proc VLDB Endowment 5(5), 466–477 (2012)CrossRef

65.

Singer, P., Helic, D., Taraghi, B., Strohmaier, M.: Detecting memory and structure in human navigation patterns using Markov chain models of varying order. PLoS One 9(7), e102070 (2014)CrossRef

66.

Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications. Structural Analysis in the Social Sciences, vol. 8, 1st edn. Cambridge University Press, Cambridge (1994)

67.

Wrobel, S.: An algorithm for multi-relational discovery of subgroups. In: Proceedings of the 1st European Symposium on Principles of Data Mining and Knowledge Discovery, pp. 78–87. Springer, Heidelberg (1997)CrossRef

68.

Xie, J., Szymanski, B.K.: LabelRank: a stabilized label propagation algorithm for community detection in networks. In: Proceedings of the IEEE Network Science Workshop, West Point, NY (2013)

69.

Xie, J., Kelley, S., Szymanski, B.K.: Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput. Surv. 45(4), 43:1–43:35 (2013)CrossRef

70.

Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, MDS ’12, pp. 3:1–3:8. ACM, New York, NY (2012)

Title: Descriptive Community Detection
Author: Martin Atzmueller
Publisher: Springer International Publishing
Book: Formal Concept Analysis of Social Networks
Print ISBN: 978-3-319-64166-9

Electronic ISBN: 978-3-319-64167-6

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-64167-6_3

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner