×

Fast approximation for computing the fractional arboricity and extraction of communities of a graph. (English) Zbl 1344.05137

Summary: In this paper, we develop some algorithmic aspects of the fractional arboricity of a graph in order to study some new approaches for graph clustering. For a given undirected graph \(G(V, E)\) with \(m\) edges and \(n\) vertices, the fractional arboricity \(\gamma(G)\) measures the maximum edge density of the subgraphs of \(G(V, E)\). It is the fractional covering number of the corresponding graphic matroid. The fractional arboricity, for applications in networks reliability or the approximation of the chromatic number of the graphs, has been studied for many years. There are some algorithms in polynomial time to compute the fractional arboricity and its integer part. But, for large graphs such as the graph of the Web or graphs of social networks, the exact algorithms are not fast enough for practical use. That is why we describe a new FPTAS to compute an \(\varepsilon\)-approximation of the fractional arboricity (with \(\varepsilon > 0\) as small as desired). Our algorithm uses the principle of the multiplicative weights update method, needs a memory of size \(O(m)\) and has a complexity of \(O(m \log^2(m) \log(\frac{m}{n}) / \varepsilon^2)\). We also give a 2-approximation of \(\gamma(G)\) with computation time \(O(m)\), which is a quick preprocessing for the main algorithm. Finally, we present a fast algorithm to extract a subgraph which achieves the value of the approximation of the fractional arboricity.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C42 Density (toughness, etc.)
91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baiou, M.; Barahona, F., A linear programming approach to increasing the weight of all minimum spanning trees, Technical Report Cahier no 2005-12, Ecole Polytechnique - Laboratoire d’Econometrie (May 2005)
[2] Barabási, A. L.; Jeong, H.; Néda, Z.; Ravasza, E.; Schubertd, A.; Vicsek, T., Evolution of the social network of scientific collaborations, Physica A, 311, 3-4, 590-614 (2002) · Zbl 0996.91086
[3] Charikar, M., Greedy approximation algorithms for finding dense components in a graph, APPROX, 82, 84-95 (2000) · Zbl 0976.05062
[4] Chen, B.; Matsumoto, M.; Wang, J.; Zhang, Z., A short proof of Nash-William’s theorem for the arboricity of a graph, Graphs Combin., 10, 27-28 (1994) · Zbl 0798.05042
[5] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1992), The MIT Press
[6] Diesner, J.; Frantz, T, and; Carley, KM., Communication networks from the Enron email corpus. “it’s always about the people. Enron is no different”, Comput. Math. Organization Theory (CMOT), 11, 3, 201-228 (2005) · Zbl 1108.91346
[7] Edmonds, J., Minimum partition of matroid into independent sets, J. Res. Natl. Bur. Standard. 69B, 67-72 (1965) · Zbl 0192.09101
[8] Gabow, Harold N.; Manu, K. S., Packing algorithms for arborescences and spanning trees in capacitated graphs, Math. Program., 82, 83-109 (1998) · Zbl 0920.90122
[9] Gabow, H.; Westermann, H., Forests, frames and games: algorithms for matroid sums and applications, (Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC (1988)), 407-421
[12] Kruskal, J. B., On the shortest spanning subtree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc., 7, 1, 48-50 (1956) · Zbl 0070.18404
[15] Nanavati, A. A.; Gurumurthy, S.; Das, G.; Chakraborty, D.; Dasgupta, K.; Mukherjea, S.; Joshi, A., On the structural properties of massive telecom call graphs: findings and implications, in: CIKM’2006: Proceedings of the 15th ACM International Conference on Information and Knowledge Management, 435-444 (2006)
[16] Nash-Williams, C. S. J. A., Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc., 36, 445-450 (1961) · Zbl 0102.38805
[17] Newman, M. E.J., Fast algorithm for detecting community structure in networks, Phys. Rev. E, 69 (2004)
[18] Opsahl, Tore; Panzarasa, Pietro, Clustering in weighted networks, Social Netw., 31, 155-163 (2009)
[19] Plotkin, S.; Shmoys, D.; Tardos, E., Fast approximation algorithms for fractional packing and covering problems, (IEEE Symposium on Foundations of Computer Science (1991)), 495-504
[20] Pons, P.; Latapy, M., Computing communities in large networks using random walks, J. Graph Algorithms Appl. (JGAA), 10, 2, 191-218 (2006) · Zbl 1161.68694
[21] Schrijver, A., Combinatorial Optimization (2003), Springer · Zbl 0542.90067
[22] Tutte, W. T., On the problem of decomposing a graph into n connected factors, J. Lond. Math. Soc., 36, 221-230 (1961) · Zbl 0096.38001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.