Regular Equivalence for Social Networks
Source abstract
Abstract
Networks and graphs are highly relevant in modeling real-life communities and their interactions. In order to gain insight in their structure, different roles are attributed to vertices, effectively clustering them in equivalence classes. A new formal definition of regular equivalence is presented in this paper, and the relation with other equivalence types is investigated and mathematically proven. An efficient algorithm is designed, able to detect all regularly equivalent roles in large-scale complex networks. We apply it to both Barabási–Albert random networks, as well as real-life social networks, which leads to interesting insights.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Complex Network Analysis Techniques · Opinion Dynamics and Social Influence · Advanced Graph Neural Networks
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Faculty of Engineering and Architecture, Department of Information Technology, Ghent-University - imec, 9052 Ghent, Belgium
References (40)
Show source-provided references
1. On random graphs10.5486/PMD.1959.6.3-4.12 ↗
2. van Steen, M. (2010). Graph Theory and Complex Networks: An Introduction, On Demand Publishing, LLC-Create Space.
3. Collective dynamics of’small-world’networks10.1038/30918 ↗
4. Csermely, P. (2006). Weak Links: The Universal Key to the Stability of Networks and Complex Systems, Springer-Verlag.
5. Deterministic scale-free networks10.1016/S0378-4371(01)00369-7 ↗
6. Statistical mechanics of complex networks10.1103/RevModPhys.74.47 ↗
7. Barabási, A.L. (2002). Linked: The New Science Of Networks, Perseus Books Group.
8. Emergence of Scaling in Random Networks10.1126/science.286.5439.509 ↗
9. Dorogovtsev, S.N., and Mendes, J.F.F. (2003). Evolution of Networks, Oxford University Press, Inc.10.1093/acprof:oso/9780198515906.001.0001 ↗
10. Vega-Redondo, F. (2007). Complex Social Networks, Cambridge University Press.10.1017/CBO9780511804052 ↗
11. Structure of Growing Networks with Preferential Linking10.1103/PhysRevLett.85.4633 ↗
12. Growing scale-free networks with tunable clustering10.1103/PhysRevE.65.026107 ↗
13. The modeling of scale-free networks10.1016/j.physa.2003.12.014 ↗
14. Wasserman, S., and Faust, K. (1995). Social Network Analysis, Cambridge University Press.10.1017/CBO9780511815478 ↗
15. Easley, D., and Kleinberg, J. (2010). Networks, Crowds, and Markets, Cambridge University Press.10.1017/CBO9780511761942 ↗
16. Structural equivalence of individuals in social networks10.1080/0022250X.1971.9989788 ↗
17. Hanneman, R., and Riddle, M. (2005). Introduction to Social Network Methods, University of California.
18. Newman, M. (2010). Networks: An Introduction, OUP Oxford.10.1093/acprof:oso/9780199206650.001.0001 ↗
19. Notions of Position in Social Network Analysis10.2307/270991 ↗
20. Scalable and Axiomatic Ranking of Network Role Similarity10.1145/2518176 ↗
21. Logical characterizations of regular equivalence10.1016/j.artint.2014.05.007 ↗
22. Regular equivalence and dynamic logic10.1016/S0378-8733(02)00036-9 ↗
23. Structural Similarity: Spectral Methods for Relaxed Blockmodeling10.1007/s00357-010-9062-8 ↗
24. Are social equivalences ever regular?: Permutation and exact tests10.1016/S0378-8733(01)00032-6 ↗
25. A new criterion function for exploratory blockmodeling for structural and regular equivalence10.1016/j.socnet.2012.12.001 ↗
26. Finding roles in sparse economic hierarchies: Going beyond regular equivalence10.1016/j.socnet.2015.10.005 ↗
27. Barrière, L., Comellas, F., Dalfó, C., and Fiol, M.A. (2016). Deterministic hierarchical networks. Physica A, 49.10.1088/1751-8113/49/22/225202 ↗
28. A theoretical investigation of regular equivalences for fuzzy graphs10.1016/j.ijar.2008.07.007 ↗
29. On the discovery of social roles in large scale social systems10.1007/s13278-015-0290-0 ↗
30. Henderson, K., Gallagher, B., Eliassi-Rad, T., Tong, H., Basu, S., Akoglu, L., Koutra, D., Faloutsos, C., and Li, L. (2012, January 12–16). RolX: Structural Role Extraction and Mining in Large Graphs. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012, Beijing, China.10.1145/2339530.2339723 ↗
31. A new approach to role and position detection in networks10.1007/s13278-016-0346-9 ↗
32. Vega, D., Meseguer, R., Freitag, F., and Magnani, M. (2015, January 25–28). Role and Position Detection in Networks: Reloaded. Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Paris, France.10.1145/2808797.2809412 ↗
33. Role Discovery in Networks10.1109/TKDE.2014.2349913 ↗
34. On the complexity of role colouring planar graphs, trees and cographs
35. Dense Subgraph Extraction with Application to Community Detection10.1109/TKDE.2010.271 ↗
36. Two algorithms for computing regular equivalence10.1016/0378-8733(93)90012-A ↗
37. Fast algorithm for detecting community structure in networks10.1103/PhysRevE.69.066133 ↗
38. Finding and testing regular equivalence10.1016/S0378-8733(02)00011-4 ↗
39. Sedgewick, R., and Wayne, K. (2011). Algorithms, Pearson Education.
40. Leskovec, J., and Krevl, A. (2018, November 30). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http://snap.stanford.edu/data.