2 Module : Gargantext.Core.Viz.Graph.Bridgeness
3 Description : Bridgeness filter
4 Copyright : (c) CNRS, 2017-Present
5 License : AGPL + CECILL v3
6 Maintainer : team@gargantext.org
7 Stability : experimental
10 Let be a graph Bridgeness filters inter-communities links in two ways.
11 If the partitions are known, filtering is uniform to expose the communities clearly for the beginners.
16 filters inter-communities links.
18 TODO use Map LouvainNodeId (Map LouvainNodeId)
21 {-# LANGUAGE BangPatterns #-}
23 module Gargantext.Core.Viz.Graph.Bridgeness -- (bridgeness)
26 import Gargantext.Core.Methods.Similarities (Similarity(..))
27 -- import Data.IntMap (IntMap)
28 import Data.Map (Map, fromListWith, lookup, toList, mapWithKey, elems)
29 import Data.Maybe (catMaybes)
30 import Data.Ord (Down(..))
31 import Debug.Trace (trace)
32 import Gargantext.Prelude
33 import Graph.Types (ClusterNode(..))
34 -- import qualified Data.IntMap as IntMap
35 import qualified Data.List as List
36 import qualified Data.Map as Map
37 import qualified Data.Set as Set
39 ----------------------------------------------------------------------
41 type Partitions = Map (Int, Int) Double -> IO [ClusterNode]
42 ----------------------------------------------------------------------
43 nodeId2comId :: ClusterNode -> (NodeId, CommunityId)
44 nodeId2comId (ClusterNode i1 i2) = (i1, i2)
47 type CommunityId = Int
49 ----------------------------------------------------------------------
50 ----------------------------------------------------------------------
51 data Bridgeness = Bridgeness_Basic { bridgeness_partitions :: [ClusterNode]
52 , bridgeness_filter :: Double
54 | Bridgeness_Advanced { bridgeness_similarity :: Similarity
55 , bridgness_confluence :: Confluence
58 type Confluence = Map (NodeId, NodeId) Double
61 bridgeness :: Bridgeness
62 -> Map (NodeId, NodeId) Double
63 -> Map (NodeId, NodeId) Double
64 bridgeness (Bridgeness_Advanced sim c) m = Map.fromList
65 $ map (\(ks, (v1,_v2)) -> (ks,v1))
66 $ List.take (if sim == Conditional then 2*n else 3*n)
67 $ List.sortOn (Down . (snd . snd))
69 $ trace ("bridgeness3 m c" <> show (m,c)) $ Map.intersectionWithKey (\k v1 v2 -> trace ("intersectionWithKey " <> (show (k, v1, v2))) (v1, v2)) m c
73 !n = trace ("bridgeness m size: " <> (show $ List.length m'))
75 $ (fromIntegral $ List.length m') / (log $ fromIntegral nodesNumber :: Double)
78 nodesNumber = Set.size $ Set.fromList $ as <> bs
80 (as, bs) = List.unzip $ Map.keys m
82 bridgeness (Bridgeness_Basic ns b) m = Map.fromList
86 $ groupEdges (Map.fromList $ map nodeId2comId ns) m
88 groupEdges :: (Ord a, Ord b1)
91 -> Map (a, a) [((b1, b1), b2)]
92 groupEdges m = fromListWith (<>)
96 n1n2_m = (,) <$> lookup n1 m <*> lookup n2 m
97 n1n2_d = Just [((n1,n2),d)]
98 in (,) <$> n1n2_m <*> n1n2_d
102 -- | TODO : sortOn Confluence
103 filterComs :: (Ord n1, Eq n2)
105 -> Map (n2, n2) [(a3, n1)]
106 -> Map (n2, n2) [(a3, n1)]
107 filterComs _b m = Map.filter (\n -> length n > 0) $ mapWithKey filter' m
112 | otherwise = take n $ List.sortOn (Down . snd) a
115 n = round $ 100 * a' / t
116 a'= fromIntegral $ length a
118 t = fromIntegral $ length $ List.concat $ elems m
120 --------------------------------------------------------------
123 map2intMap :: Map (Int, Int) a -> IntMap (IntMap a)
124 map2intMap m = IntMap.fromListWith (<>)
125 $ map (\((k1,k2), v) -> if k1 < k2
126 then (k1, IntMap.singleton k2 v)
127 else (k2, IntMap.singleton k1 v)
131 look :: (Int,Int) -> IntMap (IntMap a) -> Maybe a
132 look (k1,k2) m = if k1 < k2
133 then case (IntMap.lookup k1 m) of
134 Just m' -> IntMap.lookup k2 m'
140 Compute the median of a list
141 From: https://hackage.haskell.org/package/dsp-0.2.5.1/docs/src/Numeric.Statistics.Median.html
142 Compute the center of the list in a more lazy manner
143 and thus halves memory requirement.
146 median :: (Ord a, Fractional a) => [a] -> a
147 median [] = panic "medianFast: empty list has no median"
149 let recurse (x0:_) (_:[]) = x0
150 recurse (x0:x1:_) (_:_:[]) = (x0+x1)/2
151 recurse (_:xs) (_:_:ys) = recurse xs ys
153 panic "median: this error cannot occur in the way 'recurse' is called"