Subgraph centrality and walk-regularity
| Autor: | Kyle Kloster, Eric Horton, Blair D. Sullivan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Social and Information Networks (cs.SI) FOS: Computer and information sciences Numerical Analysis Physics - Physics and Society Algebra and Number Theory Principle of maximum entropy 010102 general mathematics Parameterized complexity FOS: Physical sciences Computer Science - Social and Information Networks 010103 numerical & computational mathematics Physics and Society (physics.soc-ph) 05C50 05C75 15A16 01 natural sciences Graph Limit point Discrete Mathematics and Combinatorics Entropy (information theory) Geometry and Topology Matrix exponential 0101 mathematics Centrality Mathematics Network analysis |
| Popis: | Matrix-based centrality measures have enjoyed significant popularity in network analysis, in no small part due to our ability to rigorously analyze their behavior as parameters vary. Recent work has considered the relationship between subgraph centrality, which is defined using the matrix exponential $f(x) = \exp(x)$, and the walk structure of a network. In a walk-regular graph, the number of closed walks of each length must be the same for all nodes, implying uniform $f$-subgraph centralities for any $f$ (or maximum $f$-$\textit{walk entropy}$). We consider when non--walk-regular graphs can achieve maximum entropy, calling such graphs $\textit{entropic}$. For parameterized measures, we are also interested in which values of the parameter witness this uniformity. To date, only one entropic graph has been identified, with only two witnessing parameter values, raising the question of how many such graphs and parameters exist. We resolve these questions by constructing infinite families of entropic graphs, as well as a family of witnessing parameters with a limit point at zero. 23 pages, 2 figures, links to software repository |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|