Search

Your search keyword '"Graph property"' showing total 3,722 results
Start Over Descriptor "Graph property"
3,722 results on '"Graph property"'

2. Edge Weights Edge weight and Network Network Properties in Multiple Sclerosis Multiple sclerosis

Author

Powell, Elizabeth, Prados, Ferran, Chard, Declan, Toosy, Ahmed, Clayden, Jonathan D., Wheeler-Kingshott, Claudia Gandini A. M., Hege, Hans-Christian, Series Editor, Hoffman, David, Series Editor, Johnson, Christopher R., Series Editor, Polthier, Konrad, Series Editor, Rumpf, Martin, Series Editor, Bonet-Carne, Elisenda, editor, Grussu, Francesco, editor, Ning, Lipeng, editor, Sepehrband, Farshid, editor, and Tax, Chantal M. W., editor

Published
2019
Full Text
View/download PDF

3. EvoGraph: On-the-Fly Efficient Mining of Evolving Graphs on GPU

Author

Sengupta, Dipanjan, Song, Shuaiwen Leon, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Kunkel, Julian M., editor, Yokota, Rio, editor, Balaji, Pavan, editor, and Keyes, David, editor

Published
2017
Full Text
View/download PDF

4. Assessing the Computational Complexity of Multi-layer Subgraph Detection

Author

Bredereck, Robert, Komusiewicz, Christian, Kratsch, Stefan, Molter, Hendrik, Niedermeier, Rolf, Sorge, Manuel, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Fotakis, Dimitris, editor, Pagourtzis, Aris, editor, and Paschos, Vangelis Th., editor

Published
2017
Full Text
View/download PDF

5. 그래프 속성을 이용한 온라인 소셜 네트워크 스팸 탐지 동향 분석.

Author

정시현 and 오하영

Subjects
ONLINE social networks, SOCIAL networks, PUBLIC opinion, INFORMATION sharing, EMERGING markets
Abstract

As online social networks are used as a critical medium for modern people's information sharing and relationship, their users are increasing rapidly every year. This not only increases usage but also surpasses the existing media in terms of information credibility. Therefore, emerging marketing strategies are deliberately attacking social networks. As a result, public opinion, which should be formed naturally, is artificially formed by online attacks, and many people trust it. Therefore, many studies have been conducted to detect agents attacking online social networks. In this paper, we analyze the trends of researches attempting to detect such online social network attackers, focusing on researches using social network graph characteristics. While the existing content-based techniques may represent classification errors due to privacy infringement and changes in attack strategies, the graph-based method proposes a more robust detection method using attacker patterns [ABSTRACT FROM AUTHOR]

Published
2020
Full Text
View/download PDF

6. Fast Distributed Algorithms for Testing Graph Properties

Author

Censor-Hillel, Keren, Fischer, Eldar, Schwartzman, Gregory, Vasudev, Yadu, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor

Published
2016
Full Text
View/download PDF

7. Decision Tree Complexity Versus Block Sensitivity and Degree

Author

Rahul Chugh and Supartha Podder and Swagato Sanyal, Chugh, Rahul, Podder, Supartha, Sanyal, Swagato, Rahul Chugh and Supartha Podder and Swagato Sanyal, Chugh, Rahul, Podder, Supartha, and Sanyal, Swagato

Abstract

Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It is known that decision tree complexity is bounded above by the cube of block sensitivity, and the cube of polynomial degree. However, the widest separation between decision tree complexity and each of block sensitivity and degree that is witnessed by known Boolean functions is quadratic. Proving quadratic relations between these measures would resolve several open questions in decision tree complexity. For example, it will imply a tight relation between decision tree complexity and square of randomized decision tree complexity and a tight relation between zero-error randomized decision tree complexity and square of fractional block sensitivity, resolving an open question raised by Aaronson [Aaronson, 2008]. In this work, we investigate the tightness of the existing cubic upper bounds. We improve the cubic upper bounds for many interesting classes of Boolean functions. We show that for graph properties and for functions with a constant number of alternations, the cubic upper bounds can be improved to quadratic. We define a class of Boolean functions, which we call the zebra functions, that comprises Boolean functions where each monotone path from 0ⁿ to 1ⁿ has an equal number of alternations. This class contains the symmetric and monotone functions as its subclasses. We show that for any zebra function, decision tree complexity is at most the square of block sensitivity, and certificate complexity is at most the square of degree. Finally, we show using a lifting theorem of communication complexity by Göös, Pitassi and Watson [Göös et al., 2017] that the task of proving an improved upper bound on the decision tree complexity for all functions

Published
2023
Full Text
View/download PDF

9. Dichotomy Theorems for Homomorphism Polynomials of Graph Classes

Author

Engels, Christian, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Rahman, M. Sohel, editor, and Tomita, Etsuji, editor

Published
2015
Full Text
View/download PDF

10. Testing Forest-Isomorphism in the Adjacency List Model

Author

Kusumoto, Mitsuru, Yoshida, Yuichi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Esparza, Javier, editor, Fraigniaud, Pierre, editor, Husfeldt, Thore, editor, and Koutsoupias, Elias, editor

Published
2014
Full Text
View/download PDF

11. Modularity of trophic network is driven by phylogeny and migration in a steppe ecosystem.

Author

Végvári, Zsolt

Subjects
STEPPES, STEPPE ecology, MIGRATORY animals, ECOSYSTEMS, ECOLOGY, PREY availability
Abstract

• Using the largest available trophic network of a large steppe ecosystem, we tested that steppe trophic networks including migratory species are associated with (i) migratory strategy and (ii) phylogenetic relatedness of interacting species. • We found that (1) a substantial number of links were established by migrant taxa; (2) the phylogenetic signal in network structure was moderate for both consumer and prey nodes; (3) both consumer and prex phylogenies affected modularity, which was modulated by migration strategy; and (4) all species-level graph properties significantly differed between networks including and excluding migratory taxa. • Our findigs provide information for conservation planning by identifying key trophic links in migratory taxa. Evidence is mounting that the structures of trophic networks are governed by migratory movements of interacting species and also by their phylogenetic relationships. Using the largest available trophic network of a large steppe ecosystem, we tested that steppe trophic networks including migratory species are associated with (i) migratory strategy and (ii) phylogenetic relatedness of interacting species: (1) whole graph-level metrics, estimated as modularity, and (2) species-level network metrics, measured as node degree (number of interacting partners), and centrality metrics. We found that (1) a substantial number of links were established by migrant taxa; (2) the phylogenetic signal in network structure was moderate for both consumer and prey nodes; (3) both consumer and prex phylogenies affected modularity, which was modulated by migration strategy; and (4) all species-level graph properties significantly differed between networks including and excluding migratory taxa. In sum, here we show that the structure of steppe trophic networks is primarily governed by migratory strategies and to a lesser extent, by phylogenetic relatedness, using the largest available food web representative for steppe ecology and migration biology. [ABSTRACT FROM AUTHOR]

Published
2019
Full Text
View/download PDF

12. Design and Analysis of Fibonacci Based TGO Compared with Real-time Mesh using Graph Invariant Technique

Author

Shanmuk Srinivas Amiripalli, P. Naga Srinivasu, and Veeramallu Bobba

Subjects
Discrete mathematics, Control and Optimization, Fibonacci number, Computer Networks and Communications, Electrical and Electronic Engineering, Graph property, Computer Science Applications, Mathematics
Abstract

Background: Graph analytics is one of the foremost established and unique strategies utilized in taking care of present-day designing issues. In this study, this procedure was applied to networks. The connectivity of gadgets is one of the intense issues distinguished in wireless systems. To deal with this issue, a unique Fibonacci-based TGO was proposed for a superior network. Methods: The proposed model attempts to construct a trimet graph based on the Fibonacci arrangement, implying that a cluster is formed with 3, 5, 8, 13, 21... hubs. To frame Fibonacci-based TGO, each of these hubs is recursively connected with a trimet diagram. For the random regular graph, the practical mesh is invariant. Edges, diameter, average degree, average clustering, density, and average shortest path are currently being compared for both meshes. Results: Fibonacci TGO has approximately 50 edges at 100 nodes and a constant diameter of 4. The average degree of Fibonacci TGO is less, which is approximately 3, having 0.7 high average clustering over random regular. As the number of nodes increases, the density decreases.TGO is having a better path than the random regular model. Finally, Fibonacci TGO mesh has better performance and connectivity over real-time meshes in wireless networks. Conclusion: We have proposed Fibonacci-based TGO mesh in the following steps. This formation is split into two stages. Fibonacci-dependent trimets based on the input nodes are created in the first stage, with 3, 5, 8, 13, and 21... nodes. These trimets will be connected in the second step to create a Fibonacci-based TGO. Both meshes are now being studied using network science parameters. In any scenario, Fibonacci-based TGO has better connectivity over the real-time random mesh. The NetworkX package in the Python language is used to produce the results automatically.

Published
2022
Full Text
View/download PDF

13. Crowd Vetting: Rejecting Adversaries via Collaboration With Application to Multirobot Flocking

Author

Matthew Cavorsi, Frederik Mallmann-Trenn, and Stephanie Gil

Subjects
Computer science, Distributed computing, media_common.quotation_subject, Computation, Computer Science Applications, Computer Science::Robotics, Adversarial system, Control and Systems Engineering, Vetting, Sybil attack, Robot, Electrical and Electronic Engineering, Function (engineering), Graph property, Flocking (texture), Computer Science::Cryptography and Security, media_common
Abstract

We characterize the advantage of using a robot's neighborhood to find and eliminate adversarial robots in the presence of a Sybil attack. We show that by leveraging the opinions of its neighbors on the trustworthiness of transmitted data, robots can detect adversaries with high probability. We characterize a number of communication rounds required to achieve this result to be a function of the communication quality and the proportion of legitimate to malicious robots. This result enables increased resiliency of many multi-robot algorithms. Because our results are finite time and not asymptotic, they are particularly well-suited for problems with a time critical nature. We develop two algorithms, \emph{FindSpoofedRobots} that determines trusted neighbors with high probability, and \emph{FindResilientAdjacencyMatrix} that enables distributed computation of graph properties in an adversarial setting. We apply our methods to a flocking problem where a team of robots must track a moving target in the presence of adversarial robots. We show that by using our algorithms, the team of robots are able to maintain tracking ability of the dynamic target.

Published
2022
Full Text
View/download PDF

14. Graph signatures: Identification and optimization

Author

Hao Pan, Balabhaskar Balasundaram, and Juan S. Borrero

Subjects
050210 logistics & transportation, Sequence, 021103 operations research, Information Systems and Management, Theoretical computer science, General Computer Science, Computer science, 05 social sciences, 0211 other engineering and technologies, Parameterized complexity, 02 engineering and technology, Management Science and Operations Research, Industrial and Manufacturing Engineering, Dynamic programming, Parameter identification problem, Identification (information), Modeling and Simulation, 0502 economics and business, Subsequence, Graph property, Biological network
Abstract

We introduce a new graph-theoretic paradigm called a graph signature that describes persistent patterns in a sequence of graphs. This framework is motivated by the need to detect subgraphs of significance in temporal networks, e.g., social and biological networks that evolve over time. Because the subgraphs of interest may not all “look alike” in the snapshots of the temporal network, the framework deems a subgraph to be persistent if it satisfies one of several preselected properties in each snapshot of a consecutive subsequence. The persistency requirement is parameterized by the length of this subsequence. This discrete mathematical framework can be viewed more broadly as a way to generalize classical graph properties and invariants associated with a single graph to a sequence of graphs. In this introductory article, we formulate the graph signature identification problem as a mixed-integer program and propose an algorithmic framework based on dynamic programming. This methodology is applicable to any collection of mixed-integer representable graph properties. We also demonstrate how this framework can be tailored to exploit property-specific decomposition and scale reduction techniques through three different computational case-studies. Our experiments show that the dynamic programming algorithm solves this problem across most instances in our test bed to optimality. Moreover, for the instances in our test bed, the optimal signature sizes are comparable to those of their static counterparts, suggesting that our new framework can identify subgraphs of significance in complex dynamic networks.

Published
2022
Full Text
View/download PDF

15. A Systematic Survey on Deep Generative Models for Graph Generation

Author

Liang Zhao and Xiaojie Guo

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Theoretical computer science, Systematic survey, Computer science, media_common.quotation_subject, Applied Mathematics, Fidelity, Machine Learning (stat.ML), Field (computer science), Graph, Domain (software engineering), Machine Learning (cs.LG), Range (mathematics), Computational Theory and Mathematics, Statistics - Machine Learning, Artificial Intelligence, Computer Vision and Pattern Recognition, Graph generation, Graph property, Generative grammar, Software, media_common
Abstract

Graphs are important data representations for describing objects and their relationships, which appear in a wide diversity of real-world scenarios. As one of a critical problem in this area, graph generation considers learning the distributions of given graphs and generating more novel graphs. Owing to their wide range of applications, generative models for graphs, which have a rich history, however, are traditionally hand-crafted and only capable of modeling a few statistical properties of graphs. Recent advances in deep generative models for graph generation is an important step towards improving the fidelity of generated graphs and paves the way for new kinds of applications. This article provides an extensive overview of the literature in the field of deep generative models for graph generation. Firstly, the formal definition of deep generative models for the graph generation and the preliminary knowledge are provided. Secondly, taxonomies of deep generative models for both unconditional and conditional graph generation are proposed respectively; the existing works of each are compared and analyzed. After that, an overview of the evaluation metrics in this specific domain is provided. Finally, the applications that deep graph generation enables are summarized and five promising future research directions are highlighted., Accepted in TPAMI

Published
2022
Full Text
View/download PDF

18. Local Reconstructors and Tolerant Testers for Connectivity and Diameter

Author

Campagna, Andrea, Guo, Alan, Rubinfeld, Ronitt, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Raghavendra, Prasad, editor, Raskhodnikova, Sofya, editor, Jansen, Klaus, editor, and Rolim, José D. P., editor

Published
2013
Full Text
View/download PDF

19. Testing Linear-Invariant Function Isomorphism

Author

Wimmer, Karl, Yoshida, Yuichi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fomin, Fedor V., editor, Freivalds, Rūsiņš, editor, Kwiatkowska, Marta, editor, and Peleg, David, editor

Published
2013
Full Text
View/download PDF

20. An Effective Branching Strategy for Some Parameterized Edge Modification Problems with Multiple Forbidden Induced Subgraphs

Author

Liu, Yunlong, Wang, Jianxin, Xu, Chao, Guo, Jiong, Chen, Jianer, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Du, Ding-Zhu, editor, and Zhang, Guochuan, editor

Published
2013
Full Text
View/download PDF

21. Iterative Approximate Byzantine Consensus under a Generalized Fault Model

Author

Tseng, Lewis, Vaidya, Nitin, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Frey, Davide, editor, Raynal, Michel, editor, Sarkar, Saswati, editor, Shyamasundar, Rudrapatna K., editor, and Sinha, Prasun, editor

Published
2013
Full Text
View/download PDF

23. Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?

Author

Fomin, Fedor V., Jansen, Bart M. P., Pilipczuk, Michał, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Thilikos, Dimitrios M., editor, and Woeginger, Gerhard J., editor

Published
2012
Full Text
View/download PDF

24. Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash

Author

Aumüller, Martin, Dietzfelbinger, Martin, Woelfel, Philipp, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Epstein, Leah, editor, and Ferragina, Paolo, editor

Published
2012
Full Text
View/download PDF

25. Deciding First Order Properties of Matroids

Author

Gavenčiak, Tomáš, Král, Daniel, Oum, Sang-il, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Czumaj, Artur, editor, Mehlhorn, Kurt, editor, Pitts, Andrew, editor, and Wattenhofer, Roger, editor

Published
2012
Full Text
View/download PDF

26. The Complexity of Minor-Ancestral Graph Properties with Forbidden Pairs

Author

Fox-Epstein, Eli, Krizanc, Danny, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Hirsch, Edward A., editor, Karhumäki, Juhani, editor, Lepistö, Arto, editor, and Prilutskii, Michail, editor

Published
2012
Full Text
View/download PDF

27. EWNI: Efficient Anonymization of Vulnerable Individuals in Social Networks

Author

Nagle, Frank, Singh, Lisa, Gkoulalas-Divanis, Aris, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Tan, Pang-Ning, editor, Chawla, Sanjay, editor, Ho, Chin Kuan, editor, and Bailey, James, editor

Published
2012
Full Text
View/download PDF

28. Principles of Network Computing

Author

Pan, Yicheng, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Agrawal, Manindra, editor, Cooper, S. Barry, editor, and Li, Angsheng, editor

Published
2012
Full Text
View/download PDF

29. Experimental Descriptive Complexity

Author

Carmosino, Marco, Immerman, Neil, Jordan, Charles, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Constable, Robert L., editor, and Silva, Alexandra, editor

Published
2012
Full Text
View/download PDF

30. Revisiting Botnet Models and Their Implications for Takedown Strategies

Author

Yen, Ting-Fang, Reiter, Michael K., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Degano, Pierpaolo, editor, and Guttman, Joshua D., editor

Published
2012
Full Text
View/download PDF

32. The Weisfeiler-Leman algorithm and recognition of graph properties

Author

Ilia Ponomarenko, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky

Subjects
FOS: Computer and information sciences, General Computer Science, Computational Complexity (cs.CC), Graph, Prime (order theory), Theoretical Computer Science, Computer Science - Computational Complexity, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Isomorphism, Graph isomorphism, Graph property, Algorithm, Mathematics
Abstract

The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of $k$-WL to recognition of graph properties. Let $G$ be an input graph with $n$ vertices. We show that, if $n$ is prime, then vertex-transitivity of $G$ can be seen in a straightforward way from the output of 2-WL on $G$ and on the vertex-individualized copies of $G$. However, if $n$ is divisible by 16, then $k$-WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with $n$ vertices as long as $k=o(\sqrt n)$. Similar results are obtained for recognition of arc-transitivity., 30 pages, 2 figures. This paper supersedes Section 5 in the first version of arXiv:2002.04590. The 3rd version is a thorough revision of the paper

Published
2021
Full Text
View/download PDF

33. Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees

Author

Jakub Przybyło

Subjects
Combinatorics, Conjecture, Open problem, Multigraph, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Multiplicity (mathematics), Combinatorics (math.CO), Geometry and Topology, Strength of a graph, Graph property, Mathematics
Abstract

The irregularity strength of a graph $G$, $s(G)$, is the least $k$ admitting a $\{1,2,\ldots,k\}$-weighting of the edges of $G$ assuring distinct weighted degrees of all vertices, or equivalently the least possible maximal edge multiplicity in an irregular multigraph obtained of $G$ via multiplying some of its edges. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists a constant $C$ such that $s(G)\leq \frac{n}{d}+C$ for each $d$-regular graph $G$ with $n$ vertices and $d\geq 2$ (while a straightforward counting argument yields $s(G)\geq \frac{n+d-1}{d}$). The best known results towards this imply that $s(G)\leq 6\lceil\frac{n}{d}\rceil$ for every $d$-regular graph $G$ with $n$ vertices and $d\geq 2$, while $s(G)\leq (4+o(1))\frac{n}{d}+4$ if $d\geq n^{0.5}\ln n$. We show that the conjecture of Faudree and Lehel holds asymptotically in the cases when $d$ is neither very small nor very close to $n$. We in particular prove that for large enough $n$ and $d\in [\ln^8n,\frac{n}{\ln^3 n}]$, $s(G)\leq \frac{n}{d}(1+\frac{8}{\ln n})$, and thereby we show that $s(G) = \frac{n}{d}(1+o(1))$ then. We moreover prove the latter to hold already when $d\in [\ln^{1+\varepsilon}n,\frac{n}{\ln^\varepsilon n}]$ where $\varepsilon$ is an arbitrary positive constant., 14 pages

Published
2021
Full Text
View/download PDF

34. Relative Coprime Probability and Graph for Some Nonabelian Groups of Small Order and Their Associated Graph Properties

Author

Nurfarah Zulkifli and Nor Muhainiah Mohd Ali

Subjects
Statistics and Probability, Economics and Econometrics, Finite group, Coprime integers, Group (mathematics), Domination analysis, Mathematics::Number Theory, Planar graph, Combinatorics, Mathematics::Group Theory, symbols.namesake, symbols, Greatest common divisor, Order (group theory), Statistics, Probability and Uncertainty, Graph property, Mathematics
Abstract

Let be a finite group. The probability that two selected elements from and from are chosen at random in a way that the greatest common divisor also known as gcd, of the order of and , which is equal to one, is called as the relative coprime probability. Meanwhile, another definition states that the vertices or nodes are the elements of a group and two distinct vertices or nodes are adjacent if and only if their orders are coprime and any of them is in the subgroup of the group and this is called as the relative coprime graph. This research focuses on determining the relative coprime probability and graph for cyclic subgroups of some nonabelian groups of small order and their associated graph properties by referring to the definitions and theorems given by previous researchers. Besides, various results of the relative coprime probability for nonabelian groups of small order are obtained. As for the relative coprime graph, the result shows that the domination number for each group is one whereas the number of edges and the independence number for each group vary. Types of graphs that can be formed are either star graph, planar graph or complete subgraph depending on the order of the subgroup of a group.

Published
2021
Full Text
View/download PDF

35. The Computational Power of Simple Protocols for Self-awareness on Graphs

Author

Chatzigiannakis, Ioannis, Michail, Othon, Nikolaou, Stavros, Spirakis, Paul G., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Défago, Xavier, editor, Petit, Franck, editor, and Villain, Vincent, editor

Published
2011
Full Text
View/download PDF

36. A Brief Introduction to Property Testing

Author

Goldreich, Oded, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Goldreich, Oded, editor

Published
2011
Full Text
View/download PDF

37. Holographic Computation of Balanced Succinct Permanent Instances : (Extended Abstract)

Author

Dolev, Shlomi, Fandina, Nova, Rosen, Joseph, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Dolev, Shlomi, editor, and Oltean, Mihai, editor

Published
2011
Full Text
View/download PDF

38. Fly-Automata, Their Properties and Applications

Author

Courcelle, Bruno, Durand, Irène A., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Bouchou-Markhoff, Béatrice, editor, Caron, Pascal, editor, Champarnaud, Jean-Marc, editor, and Maurel, Denis, editor

Published
2011
Full Text
View/download PDF

39. Generalized Fractional and Circular Total Colorings of Graphs

Author

Kemnitz Arnfried, Marangio Massimiliano, Mihók Peter, Oravcová Janka, and Soták Roman

Subjects
graph property, (p,q)-total coloring, circular coloring, fractional coloring, fractional (p,q)-total chromatic number, circular (p,q)- total chromatic number., Mathematics, QA1-939
Abstract

Let P and Q be additive and hereditary graph properties, r, s ∈ N, r ≥ s, and [ℤr]s be the set of all s-element subsets of ℤr. An (r, s)-fractional (P,Q)-total coloring of G is an assignment h : V (G) ∪ E(G) → [ℤr]s such that for each i ∈ ℤr the following holds: the vertices of G whose color sets contain color i induce a subgraph of G with property P, edges with color sets containing color i induce a subgraph of G with property Q, and the color sets of incident vertices and edges are disjoint. If each vertex and edge of G is colored with a set of s consecutive elements of ℤr we obtain an (r, s)-circular (P,Q)-total coloring of G. In this paper we present basic results on (r, s)-fractional/circular (P,Q)-total colorings. We introduce the fractional and circular (P,Q)-total chromatic number of a graph and we determine this number for complete graphs and some classes of additive and hereditary properties.

Published
2015
Full Text
View/download PDF

40. Optimization of spectral wavelets for persistence-based graph classification

Author

Ka Man Yim and Jacob Leygonie

Subjects
Signal Processing (eess.SP), FOS: Computer and information sciences, Statistics and Probability, Computer Science - Machine Learning, Computer science, Machine Learning (stat.ML), 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, QA273-280, Machine Learning (cs.LG), topological data analysis, Set (abstract data type), Wavelet, Statistics - Machine Learning, 020204 information systems, graph Laplacian, FOS: Electrical engineering, electronic engineering, information engineering, 0202 electrical engineering, electronic engineering, information engineering, Differentiable function, Electrical Engineering and Systems Science - Signal Processing, 0101 mathematics, Graph property, T57-57.97, Applied mathematics. Quantitative methods, Persistent homology, Applied Mathematics, graph classification, extended persistent homology, spectral wavelet signatures, radial basis neural network, A priori and a posteriori, Topological data analysis, Laplacian matrix, Probabilities. Mathematical statistics, Algorithm, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

A graph's spectral wavelet signature determines a filtration, and consequently an associated set of extended persistence diagrams. We propose a framework that optimizes the choice of wavelet for a dataset of graphs, such that their associated persistence diagrams capture features of the graphs that are best suited to a given data science problem. Since the spectral wavelet signature of a graph is derived from its Laplacian, our framework encodes geometric properties of graphs in their associated persistence diagrams and can be applied to graphs without a priori node attributes. We apply our framework to graph classification problems and obtain performances competitive with other persistence-based architectures. To provide the underlying theoretical foundations, we extend the differentiability result for ordinary persistent homology to extended persistent homology.

Published
2022
Full Text
View/download PDF

41. Reliably Detecting Connectivity Using Local Graph Traits

Author

Cornejo, Alejandro, Lynch, Nancy, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Lu, Chenyang, editor, Masuzawa, Toshimitsu, editor, and Mosbah, Mohamed, editor

Published
2010
Full Text
View/download PDF

42. A Brief Introduction to Property Testing

Author

Goldreich, Oded, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Goldreich, Oded, editor

Published
2010
Full Text
View/download PDF

43. Local Graph Exploration and Fast Property Testing

Author

Czumaj, Artur, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, de Berg, Mark, editor, and Meyer, Ulrich, editor

Published
2010
Full Text
View/download PDF

44. Abstraction of Object Graphs in Program Verification

Author

Chen, Yifeng, Sanders, J. W., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bolduc, Claude, editor, Desharnais, Jules, editor, and Ktari, Béchir, editor

Published
2010
Full Text
View/download PDF

45. Minimizing Movement: Fixed-Parameter Tractability

Author

Demaine, Erik D., Hajiaghayi, MohammadTaghi, Marx, Dániel, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Fiat, Amos, editor, and Sanders, Peter, editor

Published
2009
Full Text
View/download PDF

46. A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

Author

Fellows, Michael R., Guo, Jiong, Moser, Hannes, Niedermeier, Rolf, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Královič, Rastislav, editor, and Niwiński, Damian, editor

Published
2009
Full Text
View/download PDF

47. Algorithmic Aspects of Property Testing in the Dense Graphs Model

Author

Goldreich, Oded, Ron, Dana, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dinur, Irit, editor, Jansen, Klaus, editor, Naor, Joseph, editor, and Rolim, José, editor

Published
2009
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results