The OPTGRAPH 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 some 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 solve this, you could first generate all the reach networks for each customer using PROC OPTGRAPH. These networks can then be used in a set-covering problem, which can be solved as an integer linear program using PROC OPTMODEL. Let N be the set of customers that you want to reach, and let the links A define the social network between 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 A). If you use two-hop reach networks, you assume that customer i’s friends will also promote 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 the section Articulation Points in a Terrorist Network. In this case, customers are alleged terrorists. Solving the covering problem here can tell you a subset of people to focus on in an investigation in order to cover all members of the network.

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

%macro GenerateReach(limit=);
proc optgraph
   out_nodes      = NodeSetOut
   data_links     = LinkSetInTerror911;
   reach
      each_source
      out_nodes   = 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 NodeSetOut into NODE_ID=[_n_] nodeIdToLabel=node;
   read data 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();

In order to cover the network, assuming a one-hop limit, the investigators would need to investigate the people listed in the data set Solution, shown in Output 1.14.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 to the two people shown in Output 1.14.2. Then by following their links (and their links’ links) they could cover the entire network.