An official website of the United States government
Measuring importance of nodes in a graph is one of the key aspects in graph analysis. Betweenness centrality (BC) measures the amount of influence that a node has over the flow of information in a graph. However, the computation complexity of calculating BC is extremely high with large-scale graphs. This is especially true when analyzing the road networks with millions of nodes and edges. In this study, we propose a deep learning architecture RoadCaps to estimate BC with sub-second latencies. RoadCaps aggregates features from neighbor nodes using Graph Convolutional Networks and estimates the node level BC by mapping low-level concept to high-level information using Capsule Networks. Our empirical benchmarks demonstrates that RoadCaps outperforms base models such as GCN and GCNFCL in both accuracy and robustness. On average, RoadCaps generates a node’s BC value in 7.5 milliseconds.
more »
« less
This content will become publicly available on December 1, 2025
Three applications of semantic network analysis to individual student think-aloud data
Student during-learning data such as think-alouds or writing are often coded for use of strategies or moves, but less often for what knowledge the student is using. However, analyzing the content of such products could yield much valuable information. A promising technique for analyzing the content of student products is semantic network analysis, more widely used in political science, communication, information science, and some other social science disciplines. We reviewed the small literature on semantic network analysis (SemNA) of individuals with relevant outcomes to identify which network analysis metrics might be suitable. The Knowledge Integration (KI) framework from science education is discussed as focusing on amount and structure of student knowledge, and therefore especially relevant for testing with SemNA metrics. We then re-analyze three published think-aloud data sets from undergraduate students learning introductory biology with the metrics found in the literature review. Significant relations with posttest comprehension score are found for number of nodes and edges; degree and betweenness centrality; diameter, and mean distance. Inconsistent results possibly due to text-specific features were found for number of clusters, LCC, and density, and null results were found for PageRank centrality and centralization degree. Basic principles from the KI framework are supported—amount of information (nodes), connections (edges, average degree), key ideas (degree and betweenness centrality) and length of causal chains (mean distance and diameter) are related to posttest comprehension, but not density or LCC. Possible explanations for slight variations across data sets are discussed, and alternative theories and metrics are offered.
more »
« less
- Award ID(s):
- 2225298
- PAR ID:
- 10550272
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Contemporary Educational Psychology
- Volume:
- 79
- Issue:
- C
- ISSN:
- 0361-476X
- Page Range / eLocation ID:
- 102318
- Subject(s) / Keyword(s):
- causal chains during-learning data educationally-relevant outcomes propositional analysis
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Measuring the importance of a node in a network is a major goal in the analysis of social networks, biological systems, transportation networks, and so forth. Differentcentralitymeasures have been proposed to capture the notion of node importance. For example, thecenterof a graph is a node that minimizes the maximum distance to any other node (the latter distance is theradiusof the graph). Themedianof a graph is a node that minimizes the sum of the distances to all other nodes. Informally, thebetweenness centralityof a nodewmeasures the fraction of shortest paths that havewas an intermediate node. Finally, thereach centralityof a nodewis the smallest distancersuch that anys-tshortest path passing throughwhas eithersortin the ball of radiusraroundw. The fastest known algorithms to compute the center and the median of a graph and to compute the betweenness or reach centrality even of a single node take roughly cubic time in the numbernof nodes in the input graph. It is open whether these problems admit truly subcubic algorithms, i.e., algorithms with running time Õ(n3-δ) for some constant δ > 0.1 We relate the complexity of the mentioned centrality problems to two classical problems for which no truly subcubic algorithm is known, namely All Pairs Shortest Paths (APSP) and Diameter. We show that Radius, Median, and Betweenness Centrality areequivalent under subcubic reductionsto APSP, i.e., that a truly subcubic algorithm for any of these problems implies a truly subcubic algorithm for all of them. We then show that Reach Centrality is equivalent to Diameter under subcubic reductions. The same holds for the problem of approximating Betweenness Centrality within any finite factor. Thus, the latter two centrality problems could potentially be solved in truly subcubic time, even if APSP required essentially cubic time. On the positive side, our reductions for Reach Centrality imply an improved Õ(Mnω)-time algorithm for this problem in case of non-negative integer weights upper bounded byM, where ω is a fast matrix multiplication exponent.more » « less
-
Abstract Identification of influential nodes is an important step in understanding and controlling the dynamics of information, traffic, and spreading processes in networks. As a result, a number of centrality measures have been proposed and used across different application domains. At the heart of many of these measures lies an assumption describing the manner in which traffic (of information, social actors, particles, etc.) flows through the network. For example, some measures only count shortest paths while others consider random walks. This paper considers a spreading process in which a resource necessary for transit is partially consumed along the way while being refilled at special nodes on the network. Examples include fuel consumption of vehicles together with refueling stations, information loss during dissemination with error-correcting nodes, and consumption of ammunition of military troops while moving. We propose generalizations of the well-known measures of betweenness, random-walk betweenness, and Katz centralities to take such a spreading process with consumable resources into account. In order to validate the results, experiments on real-world networks are carried out by developing simulations based on well-known models such as Susceptible-Infected-Recovered and congestion with respect to particle hopping from vehicular flow theory. The simulation-based models are shown to be highly correlated with the proposed centrality measures. Reproducibility: Our code and experiments are available at https://github.com/hmwesigwa/soc_centralitymore » « less
-
null (Ed.)Smart city projects aim to enhance the management of city infrastructure by enabling government entities to monitor, control and maintain infrastructure efficiently through the deployment of Internet-of-things (IoT) devices. However, the financial burden associated with smart city projects is a detriment to prospective smart cities. A noteworthy factor that impacts the cost and sustainability of smart city projects is providing cellular Internet connectivity to IoT devices. In response to this problem, this paper explores the use of public transportation network nodes and mules, such as bus-stops as buses, to facilitate connectivity via device-to-device communication in order to reduce cellular connectivity costs within a smart city. The data mules convey non-urgent data from IoT devices to edge computing hardware, where data can be processed or sent to the cloud. Consequently, this paper focuses on edge node placement in smart cities that opportunistically leverage public transit networks for reducing reliance on and thus costs of cellular connectivity. We introduce an algorithm that selects a set of edge nodes that provides maximal sensor coverage and explore another that selects a set of edge nodes that provide minimal delivery delay within a budget. The algorithms are evaluated for two public transit network data-sets: Chapel Hill, North Carolina and Louisville, Kentucky. Results show that our algorithms consistently outperform edge node placement strategies that rely on traditional centrality metrics (betweenness and in-degree centrality) by over 77% reduction in coverage budget and over 20 minutes reduction in latency.more » « less
-
null (Ed.)Abstract Understanding the mechanisms by which neurons create or suppress connections to enable communication in brain-derived neuronal cultures can inform how learning, cognition and creative behavior emerge. While prior studies have shown that neuronal cultures possess self-organizing criticality properties, we further demonstrate that in vitro brain-derived neuronal cultures exhibit a self-optimization phenomenon. More precisely, we analyze the multiscale neural growth data obtained from label-free quantitative microscopic imaging experiments and reconstruct the in vitro neuronal culture networks (microscale) and neuronal culture cluster networks (mesoscale). We investigate the structure and evolution of neuronal culture networks and neuronal culture cluster networks by estimating the importance of each network node and their information flow. By analyzing the degree-, closeness-, and betweenness-centrality, the node-to-node degree distribution (informing on neuronal interconnection phenomena), the clustering coefficient/transitivity (assessing the “small-world” properties), and the multifractal spectrum, we demonstrate that murine neurons exhibit self-optimizing behavior over time with topological characteristics distinct from existing complex network models. The time-evolving interconnection among murine neurons optimizes the network information flow, network robustness, and self-organization degree. These findings have complex implications for modeling neuronal cultures and potentially on how to design biological inspired artificial intelligence.more » « less
