NETWORK Procedure

The problem of finding an efficient method for covering a market (a set of entities) is important in numerous industries. For example, consider that you are an advertising company with access to data that are collected from your customers’ social networks. To keep costs at a minimum in a new promotion, you want to find a minimal set of customers to whom you need to advertise in order to reach the entire market. To do this, you could first generate all the reach networks for each customer by using PROC NETWORK. These networks could then be used in a set-covering problem, which you can solve as an integer linear program by using PROC OPTMODEL. Let N be the set of customers that you want to reach, and let the links E define the social network of those customers. If you use a one-hop reach network, you assume that if an advertisement is sent to customer i, then customer i will promote the advertisement to all his friends (those he is connected to in E). If you use two-hop reach networks, you assume that customer i’s friends will also promote the advertisement to their friends. So the question is, To which subset of customers should you advertise to reach all customers through the promotion mechanism?

This problem can be generalized as follows:

To illustrate an application of this problem, consider again the terrorist communications network from Articulation Points in a Terrorist Network. In this case, customers are alleged terrorists. Solving the covering problem here can give you a subset of people to focus on in an investigation in order to cover all members of the network.

The following macro, %GenerateReach, runs PROC NETWORK to generate the reach network for each person in the terrorist network for a variable hop limit:

%macro GenerateReach(limit=);
proc network
   outNodes         = mylib.NodeSetOut
   links            = mylib.LinkSetInTerror911;
   reach
      eachSource
      outReachNodes = mylib.ReachNode
      maxReach      = &limit;
run;
%mend GenerateReach;

The following macro, %SolverCover, runs PROC OPTMODEL to solve the set-covering problem:

%macro SolverCover();
proc optmodel;
   string      tmpLabel;
   set<num>    NODE_ID;
   set<string> NODE_LABEL init {};
   string      nodeIdToLabel{NODE_ID};
   num         nodeLabelToId{NODE_LABEL};

   set<num> REACH_SET{NODE_ID} init {};
   set<string,num> PAIRS;

   /* read data */
   read data mylib.NodeSetOut into NODE_ID=[_n_] nodeIdToLabel=node;
   read data mylib.ReachNode into PAIRS=[node reach];
   for{i in NODE_ID} do;
      tmpLabel   = nodeIdToLabel[i];
      NODE_LABEL = NODE_LABEL union {tmpLabel};
      nodeLabelToId[tmpLabel] = i;
   end;
   for{<label,i> in PAIRS} do;
      REACH_SET[i] = REACH_SET[i] union {nodeLabelToId[label]};
   end;

   /* declare decision variables */
   var x {NODE_ID} binary;

   /* declare objective */
   minimize numNodes = sum{j in NODE_ID} x[j];

   /* cover constraint */
   con cover {i in NODE_ID}:
      sum{j in REACH_SET[i]} x[j] >= 1;

   /* solve */
   solve;

   create data Solution from [label]=
      (setof{j in NODE_ID : round(x[j].sol)=1}nodeIdToLabel[j]);
quit;
%mend SolverCover;

The following statements calculate the minimal cover for the one-hop limit:

%GenerateReach(limit=1);
%SolverCover();

To cover the network, assuming a one-hop limit, the investigators would need to investigate the people listed in the data table Solution, shown in Output 2.11.1.

The following statements calculate the minimal cover for the two-hop limit:

%GenerateReach(limit=2);
%SolverCover();

If investigators assume a two-hop limit, they could focus their attention on the two people shown in Output 2.11.2. Then, by following their links (and their links’ links), they could cover the entire network.