"Euler's proof that in Königsberg there is no path crossing all seven bridges only once was based on a simple observation. Nodes with an odd number of links must be either the starting or the end point of the journey. A continuous path that goes through all the bridges can have only one starting and one end point. Thus, such a path cannot exist on a graph that has more than two nodes with an odd number of links. As the Königsberg graph had four such nodes, one could not find the desired path." (Albert-László Barabási, "Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life", 2002)
"Average path length reflects the global structure; it depends on the way the entire network is connected, and cannot be inferred from any local measurement. Clustering reflects the local structure; it depends only on the interconnectedness of a typical neighborhood, the inbreeding among nodes tied to a common center. Roughly speaking, path length measures how big the network is. Clustering measures how incestuous it is." (Steven Strogatz, "Sync: The Emerging Science of Spontaneous Order", 2003)
"The concept of path-connectedness, in which it is required that it be possible to reach any point in the space from any other point along a continuous path is necessary for the notion of fundamental group. This approach is especially useful in studying connectivity properties from an algebraic point of view, e.g., via homotopy theory." (D Chatterjee, "Topology: General & Algebraic", 2003)
"If a network is solely composed of neighborhood connections, information must traverse a large number of connections to get from place to place. In a small-world network, however, information can be transmitted between any two nodes using, typically, only a small number of connections. In fact, just a small percentage of random, long-distance connections is required to induce such connectivity. This type of network behavior allows the generation of 'six degrees of separation' type results, whereby any agent can connect to any other agent in the system via a path consisting of only a few intermediate nodes." (John H Miller & Scott E Page, "Complex Adaptive Systems", 2007)
"A graph enables us to visualize a relation over a set, which makes the characteristics of relations such as transitivity and symmetry easier to understand. […] Notions such as paths and cycles are key to understanding the more complex and powerful concepts of graph theory. There are many degrees of connectedness that apply to a graph; understanding these types of connectedness enables the engineer to understand the basic properties that can be defined for the graph representing some aspect of his or her system. The concepts of adjacency and reachability are the first steps to understanding the ability of an allocated architecture of a system to execute properly." (Dennis M Buede, "The Engineering Design of Systems: Models and methods", 2009)
"A random walk, in general, is sometimes described as being similar to how a drunk person traverses a city. They know what direction or end point they want to reach but may take a very circuitous route to get there. The algorithm starts at one node and somewhat randomly follows one of the relationships forward or backward to a neighbor node. It then does the same from that node and so on, until it reaches the set path length. ('We say somewhat randomly because the number of relationships a node has, and its neighbors have, influences the probability a node will be walked through.)'" (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)
"Betweenness Centrality makes the assumption that all communication between nodes happens along the shortest path and with the same frequency, which isn’t always the case in real life. Therefore, it doesn’t give us a perfect view of the most influential nodes in a graph, but rather a good representation." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)
"A widely adopted technique for solving the data sparsity issue and the cold-start problem is based on graph representation, navigation, and processing. Graph navigation methods (like the pathfinding example [...]) and graph algorithms (such as PageRank) are applied to fill some gaps and create a denser representation of [a] dataset." (Alessandro Negro, "Graph-Powered Machine Learning", 2021)
No comments:
Post a Comment