USING SQL TO COLOR A GRAPH

Although the case study implemented the graph coloring using special-purpose C++ code, these operations are suitable for data stored in a relational database. Assume that there are three tables: call detail, dedicated fax, and shared fax. The query for finding the numbers that call a known fax number is:

SELECT originating number FROM call detail

WHERE terminating number IN (SELECT number FROM dedicated fax)

AND duration >= 10 GROUP BY originating number;

A similar query can be used to get the calls made by a known fax number. However, this does not yet distinguish between dedicated fax lines and shared fax lines. To do this, we have to know if any calls were made to information. For efficiency reasons, it is best to keep this list in a separate table or view, voice numbers, defined by:

SELECT originating number FROM call detail

WHERE terminating number in (5551212, 411) GROUP BY originating number;

So the query to find dedicated fax lines is:

SELECT originating number FROM call detail

WHERE terminating number IN (SELECT number FROM dedicated fax) AND duration > 9

AND originating number NOT IN (SELECT number FROM voice numbers) GROUP BY originating number;

and for shared lines it is:

SELECT originating number FROM call detail

WHERE terminating number IN (SELECT number FROM dedicated fax) AND duration > 2

AND originating number IN (SELECT number FROM voice numbers) GROUP BY originating number;

These SQL queries are intended to show that finding fax machines is possible on a relational database. They are probably not the most efficient SQL statements for this purpose, depending on the layout of the data, the database engine, and the hardware it is running on. Also, if there is a significant number of calls in the database, any SQL queries for link analysis will require joins on very large tables.

Team-Fly®

Case Study: Segmenting Cellular Telephone Customers

This case study applies link analysis to cellular telephone calls for the purpose of segmenting existing customers for selling new services.1 Analyses similar to those presented here were used with a leading cellular provider. The results from the analysis were used for a direct mailing for a new product offering. On such mailings, the cellular company typically measured a response rate of 2 percent to 3 percent. With some of the ideas presented here, it increased its response rate to over 15 percent, a very significant improvement.

The Data

Cellular telephone data is similar to the call detail data seen in the previous case study for finding fax machines. There is a record for each call that includes fields such as:

Originating number

Terminating number

Location where the call was placed

Account number of the person who originated the call

Call duration

Time and date

Although the analysis did not use the account number, it plays an important role in this data because the data did not otherwise distinguish between business and residential accounts. Accounts for larger businesses have thousands of phones, while most residential accounts have only a single phone.

Analyses without Graph Theory

Prior to using link analysis, the marketing department used a single measurement for segmentation: minutes of use (MOU), which is the number of minutes each month that a customer uses on the cellular phone. MOU is a useful measure, since there is a direct correlation between MOU and the amount billed to the customer each month. This correlation is not exact, since it does not take into account discount periods and calling plans that offer free nights and weekends, but it is a good guide nonetheless.

The marketing group also had external demographic data for prospective customers. They could also distinguish between individual customers and business accounts. In addition to MOU, though, their only understanding of

1 The authors would like to thank their colleagues Alan Parker, William Crowder, and Ravi Basawi for their contributions to this section.

customer behavior was the total amount billed and whether customers paid the bills in a timely matter. They were leaving a lot of information on the table.

A Comparison of Two Customers

Figure 10.11 illustrates two customers and their calling patterns during a typical month. These two customers have similar MOU, yet the patterns are strikingly different. Johns calls generate a small, tight graph, while Janes explodes with many different calls. If Jane is happy with her wireless service, her use will likely grow and she might even influence many of her friends and colleagues to switch to the wireless provider.

Looking at these two customers more closely reveals important differences. Although John racks up 150 to 200 MOU every month on his car phone, his use of his mobile telephone consists almost exclusively of two types of calls:

On his way home from work, he calls his wife to let her know what time to expect him. Sometimes they chat for three or four minutes.

Every Wednesday morning, he has a 45-minute conference call that he takes in the car on his morning commute.

The only person who has Johns car phone number is his wife, and she rarely calls him when he is driving. In fact, John has another mobile phone that he carries with him for business purposes. When driving, he prefers his car phone to his regular portable phone, although his car phone service provider does not know this.

Figure 10.11 John and Jane have about the same minutes of use each month, but their behavior is quite different.