×

Compressing strongly connected subgroups in social networks: an entropy-based approach. (English) Zbl 1417.91406

Summary: To detect and study cohesive subgroups of actors is a main objective in social network analysis. What are the respective relations inside such groups and what separates them from the outside. Entropy-based analysis of network structures is an up-and-coming approach. It turns out to be a powerful instrument to detect certain forms of cohesive subgroups and to compress them to superactors without loss of information about their embeddedness in the net: Compressing strongly connected subgroups leaves the whole net’s and the (super-)actors’ information theoretical indices unchanged; i.e., such compression is information-invariant. The actual article relates on the reduction of networks with hundreds of actors. All entropy-based calculations are realized in an expert system shell.

MSC:

91D30 Social networks; opinion dynamics
05C90 Applications of graph theory
94A17 Measures of information, entropy

Software:

Scilab; SPIRIT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barnes, J. A. (1969). Networks and political process. In J. C. Mitchell (Ed.), Social networks in urban situations (pp. 51-76). Manchester, UK: Manchester University Press.
[2] Bonacich, P., & Lloyd, P. (2001). Eigenvector-like measures of centrality for asymmetric relations. Social Networks, 23(3), 191-201. doi:10.1016/S0378-8733(01)00038-7
[3] Borgatti, S. P. (2005). Centrality and network flow. Social Networks, 27(1), 55-71. doi:10.1016/j.socnet.2004.11.008
[4] Calabrese, P. G. (2005). Reflections on Logic and Probability in the Context of Conditionals. In G. Kern-Isberner, W. Rödder, & F. Kulmann (Eds.), Conditionals, Information, and Inference, volume 3301 of Lecture Notes in Computer Science (pp. 12-37). Berlin/Heidelberg, Germany: Springer. · Zbl 1111.03023
[5] Csiszár, I. (1975). I-Divergence Geometry of Probability Distributions and Minimization Problems. The Annals of Probability, 3(1), 146-158. doi:10.1214/aop/1176996454
[6] Daly, E. M., & Haahr, M. (2009). Social network analysis for information flow in disconnected delay-tolerant MANETs. IEEE Transactions on Mobile Computing, 8(5), 606-621. doi:10.1109/TMC.2008.161
[7] Darmon, D., Omodei, E., & Flores, C. O. (2013). Detection communities using information flow in social networks. Proceedings of the Complex Systems Summer School, Santa Fe Institute, 1-21.
[8] Durkheim, É. (1961 (first 1895)). Die Regeln der soziologischen Methode. Neuwied/Berlin, Germany: Luchterhand.
[9] Freeman, L. C. (1979). Centrality in social networks conceptual clarification. Social Networks, 1(3), 215-239. doi:10.1016/0378-8733(78)90021-7
[10] Hoßfeld, T., Burger, V., Hinrichsen, H., Hirth, M., & Tran-Gia, P. (2014). On the computation of entropy production in stationary social networks. Social Network Analysis and Mining, 4(1), 190. doi:10.1007/s13278-014-0190-8
[11] Jensen, F. V., & Jensen, F. (1994). Optimal junction trees. Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence (UAI1994), 360-366.
[12] Jia, P., MirTabatabaei, A., Friedkin, N. E., & Bullo, F. (2015). Opinion dynamics and the evolution of social power in influence networks. SIAM Review, 57(3), 367-397. doi:10.1137/130913250 · Zbl 1339.91098
[13] Katz, L. (1953). A new status index derived from sociometric analysis. Psychometrika, 18(1), 39-43. doi:10.1007/BF02289026 · Zbl 0053.27606
[14] Kern-Isberner, G. (1998). Characterizing the principle of minimum cross-entropy within a conditional-logical framework. Artificial Intelligence, 98(1-2), 169-208. doi:10.1016/S0004-3702(97)00068-4 · Zbl 0903.68181
[15] Kern-Isberner, G. (2001). Conditionals in Nonmonotonic Reasoning and Belief Revision: Considering Conditionals as Agents, volume 2087 of Lecture Notes in Artificial Intelligence. Berlin/Heidelberg, Germany: Springer-Verlag. · Zbl 0978.03014
[16] Lauritzen, S. L., & Spiegelhalter, D. J. (1988). Local computations with probabilities on graphical structures and their applications to expert systems. Journal of the Royal Statistical Society B, 50(2), 154-224. · Zbl 0684.68106
[17] Meyer, C.-H. (1998). Korrektes Schließen bei unvollständiger Information. Frankfurt a.M., Germany: Peter Lang.
[18] Moreno, J. L. (1934). Who shall survive: A new approach to the problem of human interrelations. Washington, DC: Nervous and Mental Disease Publishing Co.
[19] Newcomb, T. M. (1961). The acquaintance process. New York, NY: Holt, Rinehart and Winston.
[20] Newman, M. E. J. (2010). Networks: An introduction. Oxford, UK: Oxford University Press. · Zbl 1195.94003
[21] Ortiz-Arroyo, D. (2010). Discovering sets of key players in social networks. In A. Abraham, A.-E. Hassanien, & V. Sná (Eds.), Computational social network analysis: Trends, Tools and research advances (pp. 27-47). London, UK: Springer.
[22] Rödder, W. (2001). Knowledge processing under information fidelity. Proceedings of the 17th International Joint Conference on Artificial Intelligence, Volume 1 of IJCAI’01, 749-754.
[23] Rödder, W., Brenner, D., & Kulmann, F. (2014). Entropy based evaluation of net structures - deployed in Social Network Analysis. Expert Systems with Applications, 41(17), 7968-7979. doi:10.1016/j.eswa.2014.06.049
[24] Rödder, W., & Kern-Isberner, G. (2003). From information to probability: An Axiomatic approach. Internation Journal of Intelligent Systems, 18(4), 383-403. doi:10.1002/int.10094 · Zbl 1016.68164
[25] Rödder, W., & Kulmann, F. (2006). Recall and Reasoning: An information theoretical model of cognitive processes. Information Sciences, 176(17), 2439-2466. doi:10.1016/j.ins.2005.10.010 · Zbl 1101.68092
[26] Rödder, W., Reucher, E., & Kulmann, F. (2006). Features of the Expert-System-Shell SPIRIT. Logic Journal of the IGPL, 14(3), 483-500. doi:10.1093/jigpal/jzl020 · Zbl 1109.68653
[27] Rosvall, M., & Bergstrom, C. T. (2007). An information-theoretic framework for resolving community structure in complex networks. Proceedings of the National Academy of Sciences of the United States of America, 104(18), 7327-7331. doi:10.1073/pnas.0611034104
[28] Scilab. Release 5.5.2. (2015). Retrieved May08, 2016, from http://www.scilab.org/download/5.5.2
[29] Scott, J. (2013). Social network analysis (3rd ed.). London, UK: Sage Publications.
[30] Shetty, J., & Adibi, J. (2005). Discovering important nodes through graph entropy - the case of Enron email database. Proceedings of the 3rd International Workshop on Link Discovery, 74-81.
[31] Shore, J., & Johnson, R. (1980). Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy. IEEE Transactions on Information Theory, 26(1), 26-37. doi:10.1109/TIT.1980.1056144 · Zbl 0429.94011
[32] SPIRIT. (2011). Retrieved May08, 2016, from http://www.xspirit.de
[33] Trappmann, M., Hummell, H. J., & Sodeur, W. (2005). Strukturanalyse sozialer Netzwerke. Konzepte, Modelle, Methoden. Wiesbaden, Germany: Studienskripten zur Soziologie. VS Verlag für Sozialwissenschaften.
[34] Tutzauer, F. (2007). Entropy as a measure of centrality in networks characterized by path-transfer flow. Social Networks, 29, 249-265. doi:10.1016/j.socnet.2006.10.001 · Zbl 1160.91308
[35] Ver Steeg, G., & Galstyan, A. (2012). Information transfer in social media. Proceedings of the 21st International Conference on World Wide Web, 509-518.
[36] Wasserman, S., & Faust, K. (1994). Social network analysis: Methods and applications, volume 8 of structural analysis in the social sciences. Cambridge, UK: Cambridge University Press.
[37] Zhou, D., Manavoglu, E., Li, J., Lee Giles, C., & Zha, H. (2006). Probabilistic models for discovering e-communities. Proceedings of the 15th International Conference on World Wide Web, 173-182.
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.