pydtn agkmeans and version 1.0

Fatemeh's agkmeans, basic gui, prophet Version used for paper

pydtnsim/community.py

@@ -15,7 +15,6 @@ __all__ = [
     "KCliqueCommunity",
     "LouvainCommunity",
     "AGKmeansCommunity",
-
     "CommunityNode",
     "KCliqueNode",
     "AGKmeansNode",
@@ -30,7 +29,7 @@ __all__ = [
     "HCBFLouvainNode",
 ]
 __author__ = "Jarrod Pas <j.pas@usask.ca>"
-__author__ = 'Fatemeh zr <faz361@usask.ca>'
+__author__ = "Fatemeh zr <faz361@usask.ca>"
 
 from collections import defaultdict
 from itertools import product
@@ -174,9 +173,7 @@ class Community:
         if node not in graph:
             return 0
 
-        return len(
-            [other for other in node.community if graph.has_edge(node, other)]
-        )
+        return len([other for other in node.community if graph.has_edge(node, other)])
 
     def community_betweenness(self, node_a, node_b):
         """Return community betweenness for 2 nodes."""
@@ -202,9 +199,7 @@ class Community:
             return 0
 
         return sum(
-            graph[node_a][b]["weight"]
-            for b in community_b
-            if graph.has_edge(node_a, b)
+            graph[node_a][b]["weight"] for b in community_b if graph.has_edge(node_a, b)
         )
 
 
@@ -218,9 +213,7 @@ class KCliqueCommunity(Community):
 
     def partition(self):
         """Partition graph by k-clique communities method."""
-        return nx.algorithms.community.k_clique_communities(
-            self.graph_old, k=self.k
-        )
+        return nx.algorithms.community.k_clique_communities(self.graph_old, k=self.k)
 
 
 class AGKmeansCommunity(Community):
@@ -234,12 +227,9 @@ class AGKmeansCommunity(Community):
     def partition(self):
         """Partition graph by AGk-means communities method."""
         graph = nx.Graph()
-        nodes = {
-            id(node): node
-            for node in self.graph_old.nodes()
-        }
+        nodes = {id(node): node for node in self.graph_old.nodes()}
         graph.add_nodes_from(nodes)
-        for node_a, node_b, weight in self.graph_old.edges(data='weight'):
+        for node_a, node_b, weight in self.graph_old.edges(data="weight"):
             graph.add_edge(id(node_a), id(node_b), weight=weight)
 
         partitions = agkmeans(graph, k=self.agk)
@@ -319,9 +309,7 @@ class CommunityNode(Node):
     def in_community_neighbours(self):
         """Return nodes in my community."""
         return [
-            neighbour
-            for neighbour in self.neighbours
-            if neighbour in self.community
+            neighbour for neighbour in self.neighbours if neighbour in self.community
         ]
 
     @property
@@ -333,19 +321,20 @@ class CommunityNode(Node):
             if neighbour not in self.community
         ]
 
+
 def shared_community(context, create):
-        """
-        Check context for shared community and return a shared community.
+    """
+    Check context for shared community and return a shared community.
 
-        Use this for community detection algorithms that must have one instance
-        for a set of nodes.
-        """
-        if "shared-community" in context:
-            return context["shared-community"]
+    Use this for community detection algorithms that must have one instance
+    for a set of nodes.
+    """
+    if "shared-community" in context:
+        return context["shared-community"]
 
-        community = create()
-        context["shared-community"] = community
-        return community
+    community = create()
+    context["shared-community"] = community
+    return community
 
 
 class LouvainNode(CommunityNode):
@@ -396,31 +385,53 @@ class AGKmeansNode(CommunityNode):
         epoch -- how often to recalculate communities
         k -- initial community size
         """
+
         def _create():
-            return AGKmeansCommunity(options['epoch'], options['agk'])
-        options['community'] = shared_community(options['context'], _create)
+            return AGKmeansCommunity(options["epoch"], options["agk"])
+
+        options["community"] = shared_community(options["context"], _create)
         super().__init__(**options)
 
 
 def _decide(node, others, key):
-        """
-        Make a decision on which node to send to best is decided based on key.
+    """
+    Make a decision on which node to send to best is decided based on key.
 
-        If the best is better than node, return best.
-        If node is better than the best, return node.
-        If the best and node are equal, return None.
-        """
-        best = max(others, key=key)
-        best_key = key(best)
-        node_key = key(node)
+    If the best is better than node, return best.
+    If node is better than the best, return node.
+    If the best and node are equal, return None.
+    """
+    best = max(others, key=key)
+    best_key = key(best)
+    node_key = key(node)
+
+    if best_key > node_key:
+        return best
+
+    if best_key < node_key:
+        return node
+
+    return None
+
+def _tie_breaker(node, others, tiedkey, newkey):
+    """
+    Call after decide returns None to determine the best node based on a second key
+    """
+    best = max(others, key=tiedkey)
+    tied_list = [node for node in others if tiedkey(node) == tiedkey(best)]
+
+    new_best = max(tied_list, key=newkey)
+
+    best_key = tiedkey(new_best)
+    node_key = tiedkey(node)
 
-        if best_key > node_key:
-            return best
+    if best_key > node_key:
+        return best
 
-        if best_key < node_key:
-            return node
+    if best_key < node_key:
+        return node
 
-        return None
+    return None
 
 
 class BubbleNode(CommunityNode):
@@ -457,62 +468,83 @@ class BubbleNode(CommunityNode):
 class BubbleKCliqueNode(KCliqueNode, BubbleNode):
     """Bubble node with k-clique community detection."""
 
-    pass
-
 
 class BubbleAGKmeansNode(AGKmeansNode, BubbleNode):
     """Bubble node with k-clique community detection."""
 
-    pass
-
 
 class BubbleLouvainNode(LouvainNode, BubbleNode):
     """Bubble node with louvain community detection."""
 
-    pass
-
 
 class HCBFNode(CommunityNode):
     """Node with Hybrid Community Based forwarding."""
 
     def forward(self, packet):
         """Forward packet with Hybrid Community Based heuristic."""
-        # direct forwarding
+        # direct forwarding to destination node
         forward = super().forward(packet)
         if forward:
             return forward
 
         dest = packet.destination
 
+        # get the packet to the destination community
         if self.community != dest.community:
+            # transmit to the dest community if possible
+            dest_community_neighbours = [
+                neighbour
+                for neighbour in self.out_community_neighbours
+                if neighbour in dest.community
+            ]
+            if dest_community_neighbours:
+                target = _decide(
+                None,
+                dest_community_neighbours,
+                dest._community.unique_interactions,
+            )
+                if not (target is None):
+                    return {target: "dest-community-unique-interactions"}
+
+            # else, transmit to another community with better betweenness with dest
             if self.out_community_neighbours:
                 cbc = partial(self._community.community_betweenness, dest)
                 target = _decide(self, self.out_community_neighbours, cbc)
                 if not (target is None or target is self):
                     return {target: "community-betweenness"}
 
+            # else, within this community, transmit to node with higher nodal contribution with dest
             if self.in_community_neighbours:
                 ncf = partial(self._community.nodal_contribution, dest)
                 target = _decide(self, self.in_community_neighbours, ncf)
                 if not (target is None or target is self):
                     return {target: "nodal-contribution"}
 
-        if self.in_community_neighbours:
+        # the packet is in the destination community, pick the best carrier in this community
+        elif self.in_community_neighbours:
             target = _decide(
                 self,
                 self.in_community_neighbours,
                 self._community.unique_interactions,
             )
-            if not (target is None or target is self):
+
+            if target is self:      # stay here with the highest UI
+                return {}
+
+            if target is not None:  # send to highest UI
                 return {target: "unique-interactions"}
 
-            target = _decide(
-                self,
-                self.in_community_neighbours,
-                self._community.local_popularity,
-            )
-            if not (target is None or target is self):
-                return {target: "local-popularity"}
+            else:                   # use LP to break UI ties
+                target = _tie_breaker(
+                    self,
+                    self.in_community_neighbours,
+                    self._community.unique_interactions,
+                    self._community.local_popularity
+                )
+                if not (target is None or target is self):
+                    return {target: "local-popularity"}
+          
+                
 
         return {}
 
@@ -520,16 +552,10 @@ class HCBFNode(CommunityNode):
 class HCBFKCliqueNode(KCliqueNode, HCBFNode):
     """HCBF node with k-clique community detection."""
 
-    pass
-
 
 class HCBFAGKmeansNode(AGKmeansNode, HCBFNode):
     """HCBF node with k-clique community detection."""
 
-    pass
-
 
 class HCBFLouvainNode(LouvainNode, HCBFNode):
     """HCBF node with louvain community detection."""
-
-    pass