Relevant bibliographies by topics / Dense subgraphs

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers
  5. Reports

Academic literature on the topic 'Dense subgraphs'

Author: Grafiati
Published: 31 May 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Dense subgraphs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Dense subgraphs"

1

Wu, Bo, and Haiying Shen. "Mining connected global and local dense subgraphs for bigdata." International Journal of Modern Physics C 27, no. 07 (May 24, 2016): 1650072. http://dx.doi.org/10.1142/s0129183116500728.

Full text
Abstract:
The problem of discovering connected dense subgraphs of natural graphs is important in data analysis. Discovering dense subgraphs that do not contain denser subgraphs or are not contained in denser subgraphs (called significant dense subgraphs) is also critical for wide-ranging applications. In spite of many works on discovering dense subgraphs, there are no algorithms that can guarantee the connectivity of the returned subgraphs or discover significant dense subgraphs. Hence, in this paper, we define two subgraph discovery problems to discover connected and significant dense subgraphs, propose polynomial-time algorithms and theoretically prove their validity. We also propose an algorithm to further improve the time and space efficiency of our basic algorithm for discovering significant dense subgraphs in big data by taking advantage of the unique features of large natural graphs. In the experiments, we use massive natural graphs to evaluate our algorithms in comparison with previous algorithms. The experimental results show the effectiveness of our algorithms for the two problems and their efficiency. This work is also the first that reveals the physical significance of significant dense subgraphs in natural graphs from different domains.
APA, Harvard, Vancouver, ISO, and other styles
2

Hooi, Bryan, Kijung Shin, Hemank Lamba, and Christos Faloutsos. "TellTail: Fast Scoring and Detection of Dense Subgraphs." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 4150–57. http://dx.doi.org/10.1609/aaai.v34i04.5835.

Full text
Abstract:
Suppose you visit an e-commerce site, and see that 50 users each reviewed almost all of the same 500 products several times each: would you get suspicious? Similarly, given a Twitter follow graph, how can we design principled measures for identifying surprisingly dense subgraphs? Dense subgraphs often indicate interesting structure, such as network attacks in network traffic graphs. However, most existing dense subgraph measures either do not model normal variation, or model it using an Erdős-Renyi assumption - but this assumption has been discredited decades ago. What is the right assumption then? We propose a novel application of extreme value theory to the dense subgraph problem, which allows us to propose measures and algorithms which evaluate the surprisingness of a subgraph probabilistically, without requiring restrictive assumptions (e.g. Erdős-Renyi). We then improve the practicality of our approach by incorporating empirical observations about dense subgraph patterns in real graphs, and by proposing a fast pruning-based search algorithm. Our approach (a) provides theoretical guarantees of consistency, (b) scales quasi-linearly, and (c) outperforms baselines in synthetic and ground truth settings.
APA, Harvard, Vancouver, ISO, and other styles
3

Rozenshtein, Polina, Nikolaj Tatti, and Aristides Gionis. "Finding Dynamic Dense Subgraphs." ACM Transactions on Knowledge Discovery from Data 11, no. 3 (April 14, 2017): 1–30. http://dx.doi.org/10.1145/3046791.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Semertzidis, Konstantinos, Evaggelia Pitoura, Evimaria Terzi, and Panayiotis Tsaparas. "Finding lasting dense subgraphs." Data Mining and Knowledge Discovery 33, no. 5 (November 28, 2018): 1417–45. http://dx.doi.org/10.1007/s10618-018-0602-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Mathieu, Claire, and Michel de Rougemont. "Large very dense subgraphs in a stream of edges." Network Science 9, no. 4 (December 2021): 403–24. http://dx.doi.org/10.1017/nws.2021.17.

Full text
Abstract:
AbstractWe study the detection and the reconstruction of a large very dense subgraph in a social graph with n nodes and m edges given as a stream of edges, when the graph follows a power law degree distribution, in the regime when $m=O(n. \log n)$ . A subgraph S is very dense if it has $\Omega(|S|^2)$ edges. We uniformly sample the edges with a Reservoir of size $k=O(\sqrt{n}.\log n)$ . Our detection algorithm checks whether the Reservoir has a giant component. We show that if the graph contains a very dense subgraph of size $\Omega(\sqrt{n})$ , then the detection algorithm is almost surely correct. On the other hand, a random graph that follows a power law degree distribution almost surely has no large very dense subgraph, and the detection algorithm is almost surely correct. We define a new model of random graphs which follow a power law degree distribution and have large very dense subgraphs. We then show that on this class of random graphs we can reconstruct a good approximation of the very dense subgraph with high probability. We generalize these results to dynamic graphs defined by sliding windows in a stream of edges.
APA, Harvard, Vancouver, ISO, and other styles
6

McCarty, Rose. "Dense Induced Subgraphs of Dense Bipartite Graphs." SIAM Journal on Discrete Mathematics 35, no. 2 (January 2021): 661–67. http://dx.doi.org/10.1137/20m1370744.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Asahiro, Yuichi, Refael Hassin, and Kazuo Iwama. "Complexity of finding dense subgraphs." Discrete Applied Mathematics 121, no. 1-3 (September 2002): 15–26. http://dx.doi.org/10.1016/s0166-218x(01)00243-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Tibély, Gergely. "Criterions for locally dense subgraphs." Physica A: Statistical Mechanics and its Applications 391, no. 4 (February 2012): 1831–47. http://dx.doi.org/10.1016/j.physa.2011.09.040.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Balister, Paul, Béla Bollobás, Julian Sahasrabudhe, and Alexander Veremyev. "Dense subgraphs in random graphs." Discrete Applied Mathematics 260 (May 2019): 66–74. http://dx.doi.org/10.1016/j.dam.2019.01.032.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Pyber, L. "Regular subgraphs of dense graphs." Combinatorica 5, no. 4 (December 1985): 347–49. http://dx.doi.org/10.1007/bf02579250.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Dense subgraphs"

1

Andersen, Reid. "Local algorithms for graph partitioning and finding dense subgraphs." Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2007. http://wwwlib.umi.com/cr/ucsd/fullcit?p3259059.

Full text
Abstract:
Thesis (Ph. D.)--University of California, San Diego, 2007.
Title from first page of PDF file (viewed June 11, 2007). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references (p. 92-95).
APA, Harvard, Vancouver, ISO, and other styles
2

Mougel, Pierre-Nicolas. "Finding homogeneous collections of dense subgraphs using constraint-based data mining approaches." Thesis, Lyon, INSA, 2012. http://www.theses.fr/2012ISAL0073.

Full text
Abstract:
Ce travail de thèse concerne la fouille de données sur des graphes attribués. Il s'agit de graphes dans lesquels des propriétés, encodées sous forme d'attributs, sont associées à chaque sommet. Notre objectif est la découverte, dans ce type de données, de sous-graphes organisés en plusieurs groupes de sommets fortement connectés et homogènes au regard des attributs. Plus précisément, nous définissons l'extraction sous contraintes d'ensembles de sous-graphes densément connectés et tels que les sommets partagent suffisamment d'attributs. Pour cela nous proposons deux familles de motifs originales ainsi que les algorithmes justes et complets permettant leur extraction efficace sous contraintes. La première famille, nommée Ensembles Maximaux de Cliques Homogènes, correspond à des motifs satisfaisant des contraintes concernant le nombre de sous-graphes denses, la taille de ces sous-graphes et le nombre d'attributs partagés. La seconde famille, nommée Collections Homogènes de k-cliques Percolées emploie quant à elle une notion de densité plus relaxée permettant d'adapter la méthode aux données avec des valeurs manquantes. Ces deux méthodes sont appliquées à l'analyse de deux types de réseaux, les réseaux de coopérations entre chercheurs et les réseaux d'interactions de protéines. Les motifs obtenus mettent en évidence des structures utiles dans un processus de prise de décision. Ainsi, dans un réseau de coopérations entre chercheurs, l'analyse de ces structures peut aider à la mise en place de collaborations scientifiques entre des groupes travaillant sur un même domaine. Dans le contexte d'un graphe de protéines, les structures exhibées permettent d'étudier les relations entre des modules de protéines intervenant dans des situations biologiques similaires. L'étude des performances en fonction de différentes caractéristiques de graphes attribués réels et synthétiques montre que les approches proposées sont utilisables sur de grands jeux de données
The work presented in this thesis deals with data mining approaches for the analysis of attributed graphs. An attributed graph is a graph where properties, encoded by means of attributes, are associated to each vertex. In such data, our objective is the discovery of subgraphs formed by several dense groups of vertices that are homogeneous with respect to the attributes. More precisely, we define the constraint-based extraction of collections of subgraphs densely connected and such that the vertices share enough attributes. To this aim, we propose two new classes of patterns along with sound and complete algorithms to compute them efficiently using constraint-based approaches. The first family of patterns, named Maximal Homogeneous Clique Set (MHCS), contains patterns satisfying constraints on the number of dense subgraphs, on the size of these subgraphs, and on the number of shared attributes. The second class of patterns, named Collection of Homogeneous k-clique Percolated components (CoHoP), is based on a relaxed notion of density in order to handle missing values. Both approaches are used for the analysis of scientific collaboration networks and protein-protein interaction networks. The extracted patterns exhibit structures useful in a decision support process. Indeed, in a scientific collaboration network, the analysis of such structures might give hints to propose new collaborations between researchers working on the same subjects. In a protein-protein interaction network, the analysis of the extracted patterns can be used to study the relationships between modules of proteins involved in similar biological situations. The analysis of the performances, on real and synthetic data, with respect to different attributed graph characteristics, shows that the proposed approaches scale well for large datasets
APA, Harvard, Vancouver, ISO, and other styles
3

Ebsen, Oliver-Andre [Verfasser]. "Homomorphism thresholds and embeddings of spanning subgraphs in dense graphs / Oliver-Andre Ebsen." Hamburg : Staats- und Universitätsbibliothek Hamburg Carl von Ossietzky, 2020. http://d-nb.info/1241249172/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Balalau, Oana. "Recherche de sous-graphes denses et d'événements dans les médias sociaux." Electronic Thesis or Diss., Paris, ENST, 2017. http://www.theses.fr/2017ENST0020.

Full text
Abstract:
La détection d’événements dans les réseaux sociaux consiste à retrouver les traces d’événements réels dans des flux d’informations en ligne. L’ambition de notre travail est double : trouver, dans un premier temps, des événements que les principaux médias ne traitent pas et, dans un second temps, étudier l’intérêt que les utilisateurs ont pour certains types d’événements. Pour résoudre notre problème nous commençons par une caractérisation des données basée sur un graphe dans lequel les noeuds sont des mots et les arêtes représentent le nombre de cooccurrences. La densité est une très bonne mesure de l’importance et de la cohésion dans les graphes. En prenant en compte les propriétés caractéristiques des réseaux du réel, nous pouvons développer des algorithmes capables de résoudre efficacement des problèmes complexes. Les contributions de cette thèse sont : concevoir des algorithmes efficaces pour calculer différents types de sous-graphes denses dans des graphes réels, et fournir un algorithme orienté graphe efficace pour la détection d’événements
Event detection in social media is the task of finding mentions of real-world events in collections of posts. The motivation behind our work is two-folded: first, finding events that are not covered by mainstream media and second, studying the interest that users show for certain types of events. In order to solve our problem, we start from a graph based characterization of the data in which nodes represent words and edges count word co-occurrences. Density is a very good measure of importance and cohesiveness in graphs. Taking into account the special properties of real-word networks, we can develop algorithms that efficiently solve hard problems. The contributions of this thesis are: devising efficient algorithms for computing different types of dense subgraphs in real-world graphs, presenting a novel dense subgraph definition and providing an efficient graph-based algorithm for event detection
APA, Harvard, Vancouver, ISO, and other styles
5

Fornshell, Caleb Joseph. "Empirical Comparison of Statistical Tests of Dense Subgraph in Network Data." Thesis, North Dakota State University, 2020. https://hdl.handle.net/10365/31845.

Full text
Abstract:
Network analysis is useful in modeling the structures of different phenomena. A fundamental question in the analysis of network data is whether a network contains community structure. One type of community structure of interest is a dense subgraph. Statistically deciding whether a network contains a dense subgraph can be formulated as a hypothesis test where under the null hypothesis, there is no community structure, and under the alternative hypothesis, the network contains a dense subgraph. One method in performing this hypothesis test is by counting the frequency of shapes created by all three-node subgraphs. In this study, three different test statistics based on the frequency of three-node subgraph shapes will be compared in their ability to detect a dense subgraph in simulated networks of varying size and characteristics.
APA, Harvard, Vancouver, ISO, and other styles
6

Sariyuce, Ahmet Erdem. "Fast Algorithms for Large-Scale Network Analytics." The Ohio State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=osu1429825578.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Hsu, Chia-Ming, and 許家銘. "Mining Dense Overlapping Subgraphs in Weighted Protein-Protein Interaction Networks." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/36566464250907433472.

Full text
Abstract:
碩士
國立臺灣大學
資訊管理學研究所
95
Many high throughput experiments have been used to detect protein interactions which can be used to a protein-protein interaction network. To recognize the protein complexes in a protein-protein interaction network can help us understand the mechanisms of the biological processes. In this thesis, we proposed a novel method with four phases to mine the protein complexes in the protein-protein interaction network. First, we calculate the weighted degree for each vertex in the network and pick the vertex with the highest weighted degree as the seed vertex. Second, we find a dense subgraph based on the greedy algorithm. Third, we modify the edge weights in the network and compute the weighted degree and the ratio of weighted degree for each vertex in the network. Finally, we repeat the above phases until no more dense subgraph can be found. Our proposed method does not remove any vertex and edge as a subgraph has been found. Therefore our method can mine more overlapping subgraphs than the CODENSE method. The experiment results show that our proposed method can find more protein complexes than the CODENSE method.
APA, Harvard, Vancouver, ISO, and other styles
8

Hsu, Chia-Ming. "Mining Dense Overlapping Subgraphs in Weighted Protein-Protein Interaction Networks." 2007. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0001-1807200716394500.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Dense subgraphs"

1

Asahiro, Yuichi, and Kazuo Iwama. "Finding dense subgraphs." In Algorithms and Computations, 102–11. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/bfb0015413.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Khuller, Samir, and Barna Saha. "On Finding Dense Subgraphs." In Automata, Languages and Programming, 597–608. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02927-1_50.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Chen, Xujin, Xiaodong Hu, and Changjun Wang. "Finding Connected Dense $$k$$ -Subgraphs." In Lecture Notes in Computer Science, 248–59. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-17142-5_22.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Hosseinzadeh, Mohammad Mehdi. "Dense Subgraphs in Biological Networks." In SOFSEM 2020: Theory and Practice of Computer Science, 711–19. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-38919-2_60.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Das Sarma, Atish, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan. "Dense Subgraphs on Dynamic Networks." In Lecture Notes in Computer Science, 151–65. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-33651-5_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Srivastav, Anand, and Katja Wolf. "Finding dense subgraphs with semidefinite programming." In Approximation Algorithms for Combinatiorial Optimization, 181–91. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0053974.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Jethava, Vinay, and Niko Beerenwinkel. "Finding Dense Subgraphs in Relational Graphs." In Machine Learning and Knowledge Discovery in Databases, 641–54. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-23525-7_39.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Andersen, Reid, and Kumar Chellapilla. "Finding Dense Subgraphs with Size Bounds." In Algorithms and Models for the Web-Graph, 25–37. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-540-95995-3_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Komusiewicz, Christian, and Manuel Sorge. "Finding Dense Subgraphs of Sparse Graphs." In Parameterized and Exact Computation, 242–51. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-33293-7_23.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Rozenshtein, Polina, Giulia Preti, Aristides Gionis, and Yannis Velegrakis. "Mining Dense Subgraphs with Similar Edges." In Machine Learning and Knowledge Discovery in Databases, 20–36. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-67664-3_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Dense subgraphs"

1

Srivastava, Ajitesh, Charalampos Chelmis, and Viktor K. Prasanna. "Mining Large Dense Subgraphs." In the 25th International Conference Companion. New York, New York, USA: ACM Press, 2016. http://dx.doi.org/10.1145/2872518.2889359.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Moreira, Edré, Guilherme Oliveira Campos, and Wagner Meira Jr. "Dense Hierarchy Decomposition for Bipartite Graphs." In VII Symposium on Knowledge Discovery, Mining and Learning. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/kdmile.2019.8795.

Full text
Abstract:
Dense subgraphs detection is a well known problem in Computer Science. Hierarchical organization of graphs as dense subgraphs, however, goes beyond simple clustering as it allows the analysis of the network at different scales. Despite the fact there are several works on hierarchical decomposition for unipartite graphs, only a few works for the bipartite case have been proposed. In this work we explore the problem of hierarchical decomposition of bipartite graphs. We propose an algorithm which we call weighted linking that produces denser and more compact hierarchies. The proposed algorithm is evaluated experimentally using several datasets and provided gains on most of them.
APA, Harvard, Vancouver, ISO, and other styles
3

Pinto, Patricio, Nataly Cruces, and Cecilia Hernandez. "Listing Dense Subgraphs in Small Memory." In 2014 9th Latin American Web Congress (LA-WEB). IEEE, 2014. http://dx.doi.org/10.1109/laweb.2014.16.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Ma, Shuai, Renjun Hu, Luoshu Wang, Xuelian Lin, and Jinpeng Huai. "Fast Computation of Dense Temporal Subgraphs." In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 2017. http://dx.doi.org/10.1109/icde.2017.95.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Chlamtac, Eden, Michael Dinitz, and Robert Krauthgamer. "Everywhere-Sparse Spanners via Dense Subgraphs." In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2012. http://dx.doi.org/10.1109/focs.2012.61.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Cadena, Jose, Anil Kumar Vullikanti, and Charu C. Aggarwal. "On Dense Subgraphs in Signed Network Streams." In 2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE, 2016. http://dx.doi.org/10.1109/icdm.2016.0016.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Khan, Kifayat Ullah, Waqas Nawaz, and Young-Koo Lee. "Lossless graph summarization using dense subgraphs discovery." In IMCOM '15: The 9th International Conference on Ubiquitous Information Management and Communication. New York, NY, USA: ACM, 2015. http://dx.doi.org/10.1145/2701126.2701157.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Wu, Yubao, Ruoming Jin, Xiaofeng Zhu, and Xiang Zhang. "Finding dense and connected subgraphs in dual networks." In 2015 IEEE 31st International Conference on Data Engineering (ICDE). IEEE, 2015. http://dx.doi.org/10.1109/icde.2015.7113344.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Li, Min, Jianxin Wang, Jian'er Chen, and Bin Hu. "Greedily Mining l-dense Subgraphs in Protein Interaction Networks." In 2008 9th International Conference for Young Computer Scientists (ICYCS). IEEE, 2008. http://dx.doi.org/10.1109/icycs.2008.96.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Sariyuce, Ahmet Erdem, C. Seshadhri, Ali Pinar, and Umit V. Catalyurek. "Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions." In WWW '15: 24th International World Wide Web Conference. Republic and Canton of Geneva, Switzerland: International World Wide Web Conferences Steering Committee, 2015. http://dx.doi.org/10.1145/2736277.2741640.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Dense subgraphs"

1

Seshadhri, Comandur, Ali Pinar, Ahmet Erdem Sariyuce, and Umit Catalyurek. Finding Hierarchical and Overlapping Dense Subgraphs using Nucleus Decompositions. Office of Scientific and Technical Information (OSTI), November 2014. http://dx.doi.org/10.2172/1172917.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Sariyuce, Ahmet Erdem, and Ali Pinar. Understanding the Hierarchy of Dense Subgraphs in Stationary and Temporally Varying Setting. Office of Scientific and Technical Information (OSTI), September 2017. http://dx.doi.org/10.2172/1527314.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Dense subgraphs' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography